Multiple line segment intersection: Difference between revisions
article failed to state under which conditions the naive approach is inefficient. that's bad science. |
Update URL to latest release |
||
Line 16: | Line 16: | ||
* http://softsurfer.com/Archive/algorithm_0108/algorithm_0108.htm#Pseudo-Code:%20B-O |
* http://softsurfer.com/Archive/algorithm_0108/algorithm_0108.htm#Pseudo-Code:%20B-O |
||
* Robert Pless. [http://www.cs.wustl.edu/~pless/506/l4.html Lecture 4 notes]. [[Washington University in St. Louis]], CS 506: Computational Geometry. |
* Robert Pless. [http://www.cs.wustl.edu/~pless/506/l4.html Lecture 4 notes]. [[Washington University in St. Louis]], CS 506: Computational Geometry. |
||
* [http://www.cgal.org/Manual/ |
* [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 |
||
* For the simple case of testing the intersection of two line segments: [http://astronomy.swin.edu.au/~pbourke/geometry/lineline2d/ Solution by Paul Bourke.] |
* For the simple case of testing the intersection of two line segments: [http://astronomy.swin.edu.au/~pbourke/geometry/lineline2d/ Solution by Paul Bourke.] |
||
* [http://compgeom.cs.uiuc.edu/~jeffe/teaching/373/notes/x06-sweepline.pdf "Line Segment Intersection"] lecture notes by Jeff Erickson. |
* [http://compgeom.cs.uiuc.edu/~jeffe/teaching/373/notes/x06-sweepline.pdf "Line Segment Intersection"] lecture notes by Jeff Erickson. |
Revision as of 07:18, 19 October 2011
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 for a high number of possibly intersecting segments this becomes increasingly 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 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 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
- 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
- http://softsurfer.com/Archive/algorithm_0108/algorithm_0108.htm#Pseudo-Code:%20B-O
- Robert Pless. Lecture 4 notes. Washington University in St. Louis, CS 506: Computational Geometry.
- 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.
- "Line Segment Intersection" lecture notes by Jeff Erickson.
- Line-Line Intersection Method With C Code Sample Darel Rex Finley