General Line Segment Intersection Algorithm

Background Information

The Bentley-Ottmann General Line Segment Intersection Algorithm takes O(nlogn + klogn) time to report all k pairwise intersections in a set of n line segments in two-dimensions. In addition, it uses O(n+k) space. This is a marked improvement over the brute force method which takes O(n^2) time.

The algorithm makes use of two main data structures. They are as follows:

sweep schedule Q: This is a priority queue of sweep events where the key of the priority queue is the x-coordinate of the points. The possible event points are the left and right endpoints of lines and the intersection points between lines.

sweep status D: This is a balanced search tree that maintains the linear ordering of line segments that are intersecting the sweep line.

The Bentley-Ottmann Line Segment Intersection Algorithm

Q := the 2n segment end-points
D := {}
while Q <> {} do begin
     p := DELETEMIN(Q);

     if p is the left end-point of si then begin
          INSERT(si,D);
          A := ABOVE(si,D);
          B := BELOW(si,D);
          INSERT (in Q) A intersect si and B intersect si if they exist and are to the right of p
     end

     if p is the right end-point of si then begin
          A := ABOVE(si,D);
          B := BELOW(si,D);
          DELETE(si,D);
          INSERT (in Q) A intersect B if it exists and if it is to the right of p
     end

     if p := si intersect sj then begin
          {suppose si := ABOVE(sj)}
          INTERCHANGE(si,sj,D);
          A := ABOVE(sj,D);
          B := BELOW(si,D);
          INSERT (in Q) A intersect sj and B intersect si if they exist and are to the right of p
          REPORT(p);
     end

end

References

Andranik Mirzaian - Computational Geometry (CSE 6114) Class Notes on Intersections
Mark de Berg et al. - "Computational Geometry - Algorithms and Applications", Springer-Verlag, 2000.
Bentley, Ottmann - "Algorithms for reporting and counting geometric intersections", IEEE Trans. Comput., 1979

Back to the General Line Segment Intersection Applet