com.vividsolutions.jts.geomgraph.index
Class MonotoneChainIndexer

java.lang.Object
  extended bycom.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. They have the following 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.

Version:
1.7

Constructor Summary
MonotoneChainIndexer()
           
 
Method Summary
 int[] getChainStartIndices(Coordinate[] pts)
           
static int[] toIntArray(java.util.List list)
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

MonotoneChainIndexer

public MonotoneChainIndexer()
Method Detail

toIntArray

public static int[] toIntArray(java.util.List list)

getChainStartIndices

public int[] getChainStartIndices(Coordinate[] pts)