Class SimpleSweepLineIntersector

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

public class SimpleSweepLineIntersector extends EdgeSetIntersector
Finds all intersections in one or two sets of edges, using a simple x-axis sweepline algorithm. While still O(n^2) in the worst case, this algorithm drastically improves the average-case time.
Version:
1.7
  • Field Details

    • events

      List events
    • nOverlaps

      int nOverlaps
  • Constructor Details

    • SimpleSweepLineIntersector

      public SimpleSweepLineIntersector()
  • 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
    • add

      private void add(List edges)
    • add

      private void add(List edges, Object edgeSet)
    • add

      private void add(Edge edge, Object edgeSet)
    • prepareEvents

      private void prepareEvents()
      Because DELETE events have a link to their corresponding INSERT event, it is possible to compute exactly the range of events which must be compared to a given INSERT event object.
    • computeIntersections

      private void computeIntersections(SegmentIntersector si)
    • processOverlaps

      private void processOverlaps(int start, int end, SweepLineEvent ev0, SegmentIntersector si)