redbluesweep.hpp File Reference

Bichromatic (red-blue) boundary contact by one combined plane sweep. More...

#include "algorithm/intersections.hpp"
#include <algorithm>
#include <cstddef>
#include <ranges>
#include <set>
#include <type_traits>
#include <utility>
#include <vector>

Go to the source code of this file.

Classes
struct	pgl::SweepContact
	Both boundariesCross and boundariesMeet, from one sweep. More...

Namespaces
namespace	pgl

Macros
#define	PGL_BOUNDARY_STRATEGY   0
	Overrides the dispatch, for benchmarking one strategy in isolation.

Enumerations
enum class	pgl::BoundaryContact { pgl::Disjoint , pgl::Touching , pgl::Crossing }
	How two edge sets meet, as classified by redBlueSweep. More...

Functions
template<class RedRange, class BlueRange>
BoundaryContact	pgl::redBlueSweep (const RedRange &red, const BlueRange &blue)
	Classifies how two edge sets meet, in one combined left-to-right sweep.
template<class RedRange, class BlueRange>
bool	pgl::boundariesCross (const RedRange &red, const BlueRange &blue)
	True exactly when some red edge properly crosses some blue edge.
template<class RedRange, class BlueRange>
bool	pgl::boundariesMeet (const RedRange &red, const BlueRange &blue)
	True exactly when some red edge meets some blue edge, crossing or not.
template<class RedRange, class BlueRange>
SweepContact	pgl::boundaryContactBits (const RedRange &red, const BlueRange &blue)
template<class RedShape, class BlueShape>
constexpr bool	pgl::preferSweep (const RedShape &red, const BlueShape &blue)
	Whether red against blue is a job for redBlueSweep rather than for a pairwise test of their monotone boundary chains.
template<PolygonConcept OuterPolygon, PolygonConcept InnerPolygon>
bool	pgl::sweepContains (const OuterPolygon &outer, const InnerPolygon &inner)
	Sweep-based counterpart of Polygon::contains(Polygon).

Detailed Description

Bichromatic (red-blue) boundary contact by one combined plane sweep.

Two closed edge sequences — typically the boundaries of two simple polygons — are swept together left to right in a single pass. The sweep answers the two booleans a containment test needs, and nothing more:

• does some red edge properly cross some blue edge, and
• do the two boundaries meet at all?

Only red-blue pairs are ever tested: each input is assumed non-self-crossing (the simple-polygon contract), so same-colour pairs cannot contribute an intersection that the other colour does not already witness. That is what makes a single status structure enough, and what keeps the whole thing at O((n + m) log(n + m)) no matter how the boundaries wiggle — unlike a decomposition into lexicographically monotone chains, whose cost is the product of the two chain counts and therefore degrades to quadratic on jagged, comb-like or star-shaped input.