com.vividsolutions.jts.geomgraph.index
Class MonotoneChainIndexer
java.lang.Object
com.vividsolutions.jts.geomgraph.index.MonotoneChainIndexer
public class MonotoneChainIndexer
- extends java.lang.Object
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:
- the segments within a monotone chain will never intersect each other
- 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.
- Version:
- 1.7
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
MonotoneChainIndexer
public MonotoneChainIndexer()
toIntArray
public static int[] toIntArray(java.util.List list)
getChainStartIndices
public int[] getChainStartIndices(Coordinate[] pts)