Line segment intersection
Encyclopedia
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 tree
s. 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.
Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
, 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
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...
, 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 tree
Binary search tree
In computer science, a binary search tree , which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structurewhich has the following properties:...
s. 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.
External links
- http://softsurfer.com/Archive/algorithm_0108/algorithm_0108.htm#Pseudo-Code:%20B-O
- Robert Pless. Lecture 4 notes. Washington University in St. LouisWashington University in St. LouisWashington University in St. Louis is a private research university located in suburban St. Louis, Missouri. Founded in 1853, and named for George Washington, the university has students and faculty from all fifty U.S. states and more than 110 nations...
, CS 506: Computational Geometry. - Line segment intersection in CGALCGALThe Computational Geometry Algorithms Library is a software library that aims to provide easy access to efficient and reliable algorithms in computational geometry. While primarily written in C++, Python and Scilab bindings are also available....
, 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