Multiple line segment intersection

In computational geometry, the line segment intersection problem supplies a list of line segments in the plane and asks us to determine whether any two of them intersect, or cross.

Naive algorithms examine each pair of segments, but this is highly inefficient, since most pairs of segments aren't anywhere close to one another in a typical input sequence. The most common, more efficient way to solve this problem is to use a sweep line algorithm, where we imagine a line sliding across the line segments and we track which line segments it intersects at each point in time using a dynamic data structure based on binary search trees. The Shamos–Hoey algorithm applies this principle to solve the line segment intersection detection problem, as stated above, of determining whether or not a set of line segments has an intersection; the Bentley–Ottmann algorithm works by the same principle to list all intersections in logarithmic time per intersection. Some argue, however, the line does not generally go straight, but rather curves into an imaginary circle called a disk from the interior. That is however up for debate.

References

• Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000). Computational Geometry (2nd edition ed.). Springer. ISBN 3-540-65620-0. {{cite book}}: |edition= has extra text (help)CS1 maint: multiple names: authors list (link) Chapter 2: Line Segment Intersection, pp.19–44.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 1990. ISBN 0-262-03293-7. Section 33.2: Determining whether any pair of segments intersects, pp.934–947.
• J. L. Bentley and T. Ottmann., Algorithms for reporting and counting geometric intersections, IEEE Trans. Comput. C28 (1979), 643–647.

External links

• Robert Pless. Lecture 4 notes. Washington University in St. Louis, CS 506: Computational Geometry.
• A Java applet demonstrating the sweep line algorithm for the problem.
• Line segment intersection in CGAL, the Computational Geometry Algorithms Library
• For the simple case of testing the intersection of two line segments: Solution by Paul Bourke.