Class MonotoneChainEdge

java.lang.Object
org.locationtech.jts.geomgraph.index.MonotoneChainEdge

public class MonotoneChainEdge extends 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
  • Field Details

  • Constructor Details

    • MonotoneChainEdge

      public MonotoneChainEdge(Edge e)
  • Method Details

    • getCoordinates

      public Coordinate[] getCoordinates()
    • getStartIndexes

      public int[] getStartIndexes()
    • getMinX

      public double getMinX(int chainIndex)
    • getMaxX

      public double getMaxX(int chainIndex)
    • computeIntersects

      public void computeIntersects(MonotoneChainEdge mce, SegmentIntersector si)
    • computeIntersectsForChain

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

      private void computeIntersectsForChain(int start0, int end0, MonotoneChainEdge mce, int start1, int end1, SegmentIntersector ei)
    • overlaps

      private boolean overlaps(int start0, int end0, MonotoneChainEdge mce, int start1, int end1)
      Tests whether the envelopes of two chain sections overlap (intersect).
      Parameters:
      start0 -
      end0 -
      mce -
      start1 -
      end1 -
      Returns:
      true if the section envelopes overlap