com.vividsolutions.jts.geomgraph.index

Class 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.

    • Constructor Detail

      • SimpleMCSweepLineIntersector

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

    • Method Detail

      • 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.