Line Segment Intersections
The line segment intersection problem is a basic geometric
problem. It asks to compute the set of intersections of a set
of line segments in the plane.
Two segments s1 and s2
intersect if they have at least one point in common. They
overlap if they have more than one point in common. There
is a proper intersection if the two segments share exactly
one point and this point lies in the interior of both segments .
A trivial segment is a segment of length 0.
On the right you see a set of 50 segments in the plane, the intesections
are drawn in red. The picture is a screenshot from the example
of line segment intersectionl.
of line segment intersection
void SEGMENT_INTERSECTION (const list<SEGMENT>& S,list<POINT>& P)
computes the intersections between the segments in S and returns all
proper intersections in P.
We use the notation
POINT (SEGMENT) to indicate that the
algorithm works both for
points (segments) and
(rat_segments) . See also Writing
Kernel Independent Code.
Remark: LEDA provides several variants for computing intersections
between line segments using different algorithms and satisfying different
output requirements. See the Manual
Page of Geometry Algorithms and the LEDA
Book for details.
- computer aided design (CAD)
- geographic information systems (GIS)
Different applications have different output requirements, e.g., return
number of intersections, trigger an action for every pair of intersecting
segments, compute graph induced by segments, compute trapezoid decomposition
induced by the set of segments.
Representation of Intersecting Line Segments
The set of segments
S induces an undirected graph
as follows: Vertices of
U(S) are all endpoints of segments
S and all proper intersection points between segments in
S. Edges of
U are the maximal relatively
open and connected subsets of segments in
S that contain no
U(S) contains parallel edges if
S contains segments that overlap.
U(S) by a directed
graph G as follows.
U have the same set of nodes.
Each node is labeled by its position in the plane.
- The edges of
G correspond to the edges in
- If the algorithm does not compute an embedding (
there is exactly one edge in
G for each edge of
The edge is labeled by the segment in
it and inherits the direction from the segment.
- If the algorithm computes an embedding (
G is a planar
map. For each edge of
U there are two edges in
G that are reversals of each other. For each node
G the cyclic list
of edges out of
v is counter-clockwise ordered.
Data Types for 2-D Geometry
Windows and Panels
Writing Kernel Independent Code
Page of Geometry Algorithms