GEOS
3.9.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 realworld data, these properties eliminate a large number of segment comparisons, producing substantial speed gains.