com.vividsolutions.jts.geomgraph.index

Class MonotoneChainEdge


public class MonotoneChainEdge
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.6

Constructor Summary

MonotoneChainEdge(Edge e)

Method Summary

void
computeIntersects(MonotoneChainEdge mce, SegmentIntersector si)
void
computeIntersectsForChain(int chainIndex0, MonotoneChainEdge mce, int chainIndex1, SegmentIntersector si)
Coordinate[]
getCoordinates()
double
getMaxX(int chainIndex)
double
getMinX(int chainIndex)
int[]
getStartIndexes()

Constructor Details

MonotoneChainEdge

public MonotoneChainEdge(Edge e)

Method Details

computeIntersects

public void computeIntersects(MonotoneChainEdge mce,
                              SegmentIntersector si)

computeIntersectsForChain

public void computeIntersectsForChain(int chainIndex0,
                                      MonotoneChainEdge mce,
                                      int chainIndex1,
                                      SegmentIntersector si)

getCoordinates

public Coordinate[] getCoordinates()

getMaxX

public double getMaxX(int chainIndex)

getMinX

public double getMinX(int chainIndex)

getStartIndexes

public int[] getStartIndexes()