xysweep.hpp File Reference

Bounding-box sweep over pairs of segments. More...

#include "algorithm/intervaltree.hpp"
#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <stdexcept>
#include <type_traits>
#include <utility>
#include <vector>

Go to the source code of this file.

Namespaces
namespace	pgl

Functions
template<class Rational = pgl::Rational<pgl::BigInt>, class Container>
auto	pgl::xyCrossings (const Container &segments)
	Finds all crossing segment pairs with a bounding-box sweep.
template<class Rational = pgl::Rational<pgl::BigInt>, class Container>
auto	pgl::xyIntersections (const Container &segments)
	Finds all intersecting segment pairs with a bounding-box sweep.

Detailed Description

Bounding-box sweep over pairs of segments.

A vertical line sweeps the bounding-box abscissas of the input while an IntervalTree over the y-extents holds the segments the line currently meets. A segment entering the sweep is queried against that active set, so the only pairs ever examined are those whose bounding boxes overlap. The pair-reporting algorithms built on it (xyCrossings and xyIntersections) report what the brute-force scans report, and the simplicity tests of Polygon and Polyline use it for the coordinate types the exact sweep line cannot take.