Line Segment Intersections
The line segment intersection problem is a basic geometric
problem. It asks to compute the set of intersections of a set S
of line segments in the plane.
Two segments s_{1} and s_{2}
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.


Example
of line segment intersection
The function
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_points
(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.
Applications
 computer aided design (CAD)
 geographic information systems (GIS)
 cartography
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 U(S)
as follows: Vertices of U(S) are all endpoints of segments
in 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
vertex of U(S) . U(S) contains parallel edges if
S contains segments that overlap.
LEDA represents U(S) by a directed
graph G as follows.
G and 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 U .
 If the algorithm does not compute an embedding (
embed==false )
there is exactly one edge in G for each edge of U .
The edge is labeled by the segment in S containing
it and inherits the direction from the segment.
 If the algorithm computes an embedding (
embed==true )
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 v
of G the cyclic list
of edges out of v is counterclockwise ordered.

See also:
Data Types for 2D Geometry
Graphs
Parameterized Graphs
Linear Lists
Windows and Panels
Writing Kernel Independent Code
Geometry Algorithms
Geometry
GeoWin
Number Types
Manual Entries
Manual
Page of Geometry Algorithms
