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

      Fields 
      Modifier and Type Field Description
      (package private) java.util.List events  
      (package private) int nOverlaps  
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private void add​(java.util.List edges)  
      private void add​(java.util.List edges, java.lang.Object edgeSet)  
      private void add​(Edge edge, java.lang.Object edgeSet)  
      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.
      private void computeIntersections​(SegmentIntersector si)  
      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.
      private void processOverlaps​(int start, int end, SweepLineEvent ev0, SegmentIntersector si)  
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • events

        java.util.List events
      • nOverlaps

        int nOverlaps
    • Constructor Detail

      • SimpleSweepLineIntersector

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

        private void add​(java.util.List edges)
      • add

        private void add​(java.util.List edges,
                         java.lang.Object edgeSet)
      • add

        private void add​(Edge edge,
                         java.lang.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.