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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”