Line segment intersection
- 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 self-balancing binary search trees.
References
* 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.
See also
* Bentley-Ottmann algorithm
* Shamos-Hoey algorithm
External links
* Robert Pless. [http://www.cs.wustl.edu/~pless/506/l4.html Lecture 4 notes] . Washington University in St. Louis, CS 506: Computational Geometry.
* A [http://www.lupinho.de/gishur/html/Sweeps.html Java applet] demonstrating the sweep line algorithm for the problem.
* [http://www.cgal.org/Manual/3.2/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.]
* A sample implementation of a computer algorithm to find the points that minimize distance between two line segments: [http://www.geometryalgorithms.com/Archive/algorithm_0106/algorithm_0106.htm http://www.geometryalgorithms.com/Archive/algorithm_0106/algorithm_0106.htm]
Wikimedia Foundation.
2010.
Look at other dictionaries:
Line segment — The geometric definition of a line segment … Wikipedia
Intersection — has various meanings in different contexts: *In mathematics and geometry **Intersection (set theory), the set of elements common to some collection of sets. **Line line intersection **Line plane intersection **Line–sphere intersection… … Wikipedia
Line-line intersection — In Euclidean geometry, the intersection of a line and a line can be the empty set, a point, or a line. Distinguishing these cases, and finding the intersection point have use, for example, in computer graphics, motion planning, and collision… … Wikipedia
Sweep line algorithm — In computational geometry, a sweep line algorithm or plane sweep algorithm is a type of algorithm that uses a conceptual sweep line or sweep surface to solve various problems in Euclidean space. It is one of the key techniques in computational… … Wikipedia
Green Line (Washington Metro) — Green Line … Wikipedia
Philo line — In geometry, the Philo line is a line segment defined from an angle and a point. The Philo line for a point P that lies inside an angle with edges d and e is the shortest line segment that passes through P and has its endpoints on d and e . Also… … Wikipedia
LACMTA Expo Line — The Metro Expo Line of the Los Angeles County Metro Rail is a light rail line currently under construction in Los Angeles County, California, USA, which will run from Downtown Los Angeles to Culver City and eventually to Santa Monica. Its route… … Wikipedia
Montclair-Boonton Line — Montclair Boonton Line … Wikipedia
Secant line — A secant line of a curve is a line that (locally) intersects two points on the curve. The word secant comes from the Latin secare , for to cut .It can be used to approximate the tangent to a curve, at some point P . If the secant to a curve is… … Wikipedia
Belt Line Road (Texas) — Belt Line Road is a loop road that traverses convert|92|mi|km|0|lk=on through 16 cities in Dallas County, Texas. Belt Line Road is the outer complete loop which encircles Dallas, in contrast with Interstate 635 which forms an inner loop. Belt… … Wikipedia
