Class SimpleMCSweepLineIntersector

java.lang.Object
org.locationtech.jts.geomgraph.index.EdgeSetIntersector
org.locationtech.jts.geomgraph.index.SimpleMCSweepLineIntersector

public class SimpleMCSweepLineIntersector extends EdgeSetIntersector
Finds all intersections in one or two sets of edges, using an x-axis sweepline algorithm in conjunction with Monotone Chains. While still O(n^2) in the worst case, this algorithm drastically improves the average-case time. The use of MonotoneChains as the items in the index seems to offer an improvement in performance over a sweep-line alone.
Version:
1.7
  • Constructor Details

    • SimpleMCSweepLineIntersector

      public SimpleMCSweepLineIntersector()
      A SimpleMCSweepLineIntersector creates monotone chains from the edges and compares them using a simple sweep-line along the x-axis.
  • Method Details

    • computeIntersections

      public void computeIntersections(List edges, SegmentIntersector si, boolean testAllSegments)
      Description copied from class: EdgeSetIntersector
      Computes all self-intersections between edges in a set of edges, allowing client to choose whether self-intersections are computed.
      Specified by:
      computeIntersections in class EdgeSetIntersector
      Parameters:
      edges - a list of edges to test for intersections
      si - the SegmentIntersector to use
      testAllSegments - true if self-intersections are to be tested as well
    • computeIntersections

      public void computeIntersections(List edges0, List edges1, SegmentIntersector si)
      Description copied from class: EdgeSetIntersector
      Computes all mutual intersections between two sets of edges.
      Specified by:
      computeIntersections in class EdgeSetIntersector
      Parameters:
      edges0 - set of edges
      edges1 - set of edges
      si - segment intersector