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.
    Version:
    1.7
    • Constructor Summary

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

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void computeIntersections​(java.util.List edges0, java.util.List edges1, SegmentIntersector si)
      Computes all mutual intersections between two sets of edges.
      void computeIntersections​(java.util.List edges, SegmentIntersector si, boolean testAllSegments)
      Computes all self-intersections between edges in a set of edges, allowing client to choose whether self-intersections are computed.
      • Methods inherited from class java.lang.Object

        equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • 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​(java.util.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