GEOS
3.14.0dev
|
MonotoneChains are a way of partitioning the segments of an edge to allow for fast searching of intersections. More...
#include <MonotoneChainIndexer.h>
Public Member Functions | |
void | getChainStartIndices (const geom::CoordinateSequence *, std::vector< std::size_t > &) |
MonotoneChains are a way of partitioning the segments of an edge to allow for fast searching of intersections.
Specifically, a sequence of contiguous line segments is a monotone chain iff all the vectors defined by the oriented segments lies in the same quadrant.
Monotone Chains have the following useful properties:
Property 1 means that there is no need to test pairs of segments from within the same monotone chain for intersection. Property 2 allows binary search to be used to find the intersection points of two monotone chains. For many types of real-world data, these properties eliminate a large number of segment comparisons, producing substantial speed gains.