Sweep-versus-chains dispatch

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

Functions
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.

Detailed Description

Two ways to find out how two polygon boundaries meet, with opposite cost profiles, and the single rule that picks between them.

redBlueSweep is O((n + m) log(n + m)) come what may. Testing the two boundaries' maximal lexicographically monotone chains against each other pairwise (see Polygon::BoundaryChains) is not: it runs one merge per chain pair, so it costs the product of the two chain counts — two chains a side for a convex polygon, up to n for a comb or a star. Neither dominates:

• The chain test wins on near-convex input, where the product is tiny and the merges are seeded by binary search, and it wins again whenever the answer comes early, since it produces chains lazily and stops at the first hit. The sweep cannot stop early in the same sense: it builds and sorts every event before it looks at anything.
• The sweep wins once the chain counts climb, by margins that reach two orders of magnitude on a 4096-vertex star.

Absolute size matters as much as the ratio does. The sweep allocates edge and event vectors and drives a std::set; on a pair of 32-gons that fixed overhead swamps the handful of orientation tests either method needs, and the chain test wins however jagged the two are. The crossover therefore moves with how expensive one orientation test is: for BigInt or a rational built on it, a single predicate costs more than the sweep's whole bookkeeping, so the method doing fewer of them pulls ahead at a much smaller size than it does for int or double.

Macro Definition Documentation

PGL_BOUNDARY_STRATEGY

#define PGL_BOUNDARY_STRATEGY   0

Overrides the dispatch, for benchmarking one strategy in isolation.

Define to 1 to force the chain-pair tests everywhere, 2 to force the sweep. Left at its default of 0, preferSweep decides per call. Only the default is a supported configuration; the other two exist so a benchmark can time the two strategies over the same inputs (see tests/benchmark/extra).

Function Documentation

preferSweep()

template<class RedShape, class BlueShape>

bool pgl::preferSweep ( const RedShape & red, const BlueShape & blue )

constexpr

Whether red against blue is a job for redBlueSweep rather than for a pairwise test of their monotone boundary chains.

The one place the library decides between the two boundary strategies, so the heuristic is tuned once and every predicate built on it — Polygon::contains, intersects, interiorContains, interiorsIntersect, and PolygonWithHoles/PolygonSet containment through them — moves together. Both operands may be a Polygon or a PolygonWithHoles.

Reading the two chain counts is O(n + m) and allocation-free (see Polygon::chainCount), which both strategies are dominated by anyway.

Parameters

red	First boundary.
blue	Second boundary.

Returns

true to sweep, false to compare chains.