Class: MonotoneChainIndexer

jsts.geomgraph.index.MonotoneChainIndexer

new MonotoneChainIndexer()

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:

  1. the segments within a monotone chain will never intersect each other
  2. the envelope of any contiguous subset of the segments in a monotone chain is simply the envelope of the endpoints of the subset.
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.
Source:

Methods

(static) toIntArray(list) → {Array.<int>}

Parameters:
Name Type Description
list javascript.util.List
Source:
Returns:
Type
Array.<int>

findChainEnd(pts, start) → {int}

return the index of the last point in the monotone chain
Parameters:
Name Type Description
pts Array.<Coordinate>
start int
Source:
Returns:
Type
int

getChainStartIndices(pts) → {Array.<int>}

Parameters:
Name Type Description
pts Array.<Coordinate>
Source:
Returns:
Type
Array.<int>