Multiple line segment intersection
{{for multi|two segments|Line segment intersection|infinite lines|Line-line intersection}}
In computational geometry, the multiple line segment intersection problem supplies a list of line segments in the Euclidean plane and asks whether any two of them intersect (cross).
Simple algorithms examine each pair of segments. However, if a large number of possibly intersecting segments are to be checked, this becomes increasingly inefficient since most pairs of segments are not close to one another in a typical input sequence. The most common, and more efficient, way to solve this problem for a high number of segments 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{{Cite journal | doi = 10.1109/SFCS.1976.16| url = http://euro.ecom.cmu.edu/people/faculty/mshamos/1976GeometricIntersection.pdf
| title = 17th Annual Symposium on Foundations of Computer Science (sfcs 1976)
| pages = 208| year = 1976| last1 = Shamos | first1 = M. I.| last2 = Hoey | first2 = D.| s2cid = 124804
}} Chapter: "Geometric intersection problems" 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.
See also
References
{{Reflist}}
Further reading
- {{cite book |author1=Mark de Berg |author2=Marc van Kreveld |author3=Mark Overmars |author4=and Otfried Schwarzkopf |year=2000 |title=Computational Geometry |publisher=Springer |edition=2nd |isbn=3-540-65620-0 |url-access=registration |url=https://archive.org/details/computationalgeo00berg }} 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
- {{usurped|1=[https://web.archive.org/web/20130109225152/http://geomalgorithms.com/a05-_intersect-1.html Intersections of Lines and Planes]}} Algorithms and sample code by Dan Sunday
- Robert Pless. [https://web.archive.org/web/20160707015648/http://www.cs.wustl.edu/~pless/506/l4.html Lecture 4 notes]. Washington University in St. Louis, CS 506: Computational Geometry ([https://web.archive.org/web/20171020091733/http://www.cs.wustl.edu/~pless/546/ cached copy]).
- [http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Sweep_line_2/Chapter_main.html Line segment intersection] in CGAL, the Computational Geometry Algorithms Library
- [https://web.archive.org/web/20050601132020/http://compgeom.cs.uiuc.edu/~jeffe/teaching/373/notes/x06-sweepline.pdf "Line Segment Intersection"] lecture notes by Jeff Erickson.
- [http://alienryderflex.com/intersect/ Line-Line Intersection Method With C Code Sample] Darel Rex Finley
Category:Geometric intersection
Category:Computational geometry
{{algorithm-stub}}