Lecture 3: Line Segment Intersection

Geometric intersections: One of the most basic problems in computational geometry is that of
computing intersections. It has numerous applications.

ˆ In solid modeling complex shapes are constructed by applying various boolean operations
(intersection, union, and difference) to simple primitive shapes. The process is called
constructive solid geometry (CSG). Computing intersections of model surfaces is an
essential part of the process.
ˆ In robotics and motion planning it is important to know when two objects intersect for
collision detection and collision avoidance.
ˆ In geographic information systems it is often useful to overlay two subdivisions (e.g. a
road network and county boundaries to determine where road maintenance responsibili-
ties lie). Since these networks are formed from collections of line segments, this generates
a problem of determining intersections of line segments.

Lecture Notes 25
 ˆ In computer graphics, ray shooting is a classical method for rendering scenes. The
computationally most intensive part of ray shooting is determining the intersection of
the ray with other objects.

In this lecture, we will focus the basic primitive of computing line segment intersections in
the plane.

Line-Segment intersection: We are given a set S = {s1 , . . . , sn } of n line segments in the plane.
Let’s assume that each is represented by its two endpoints si = pi qi . We will consider the
problem of reporting pairs of line segments that intersect (see Fig. 23(a)).

General-position assumptions
no duplicate x-coordinates
no vertical segments
no 3-way intersections
no endpoint lies on another segment

(a) (b)

Fig. 23: Line segment intersection.

To simplify the presentation, we will make the usual general-position assumptions. In partic-
ular, we will rule out the following (see Fig. 23(b)):

ˆ No duplicate x-coordinates among endpoints or intersection points (which implies no

vertical line segments or multiple intersections)
ˆ No segment endpoint lies on another segment

All these special cases are relatively easy to cope with, but the algorithms are more complex
because they need to deal with various special cases. One common exception to the above is
to allow multiple segments to share a common endpoint, since this occurs when dealing with
polygons and spatial subdivision.

Output Sensitivity: Observe that n line segments can intersect in as few as zero and as many
n
as 2 = O(n ) different intersection points. We could settle for an O(n2 ) time algorithm,
2

claiming that it is worst-case asymptotically optimal, but it would not be very useful in prac-
tice, since in many instances of intersection problems intersections may be rare. Therefore,
we will focus on output sensitive algorithms, meaning that the running time depends not only
on the number of segments, but also the number of intersecting pairs.
Given a set S of n line segments, let m = m(S) denote the number of intersections. We will
express the running time of our algorithm in terms of both n and m. As usual, we will assume
that the line segments are in general position.

Utility Data Structures: Our algorithm will make use of two standard dynamic data structures
(see CLRS for details).

Lecture Notes 26
 Ordered Dictionary: Stores a set of objects each associated with a key from an totally
ordered domain. Supports the operations insert, delete, find, predecessor, successor,
get-kth (which returns the item at some given rank) and swap (which swaps two given
adjacent entries) all in O(log n) time and O(n) space, where n is the current number of
objects. (This is typically implemented using balanced binary trees, such as red-black
trees, or skip lists. Note that because of the predecessor, successor, and swap operations,
we cannot used unordered dictionaries like hashing.)
Priority Queue: Stores a set of objects, where each object is associated with a priority value.
Supports the operations insert, delete, and extract-min (which accesses and removes the
object with the smallest priority value). We also assume that the insert operation returns
a special reference to the inserted object, which allows us to efficiently delete this item.
These operations are supported in O(log n) time and O(n) space, where n is the current
number of objects. (This is typically implemented as a binary heap.)

Plane Sweep: Let us now consider a natural approach for reporting the segment intersections.
The method, called plane sweep, is a fundamental technique in planar computational geome-
try. We solve a 2-dimensional problem by simulating the process of sweeping a 1-dimensional
line across the plane. The intersections of the sweep line with the segments defines a collection
of points along the sweep line.
Although we might visualize the sweeping process as a continuous one, there is a discrete set
of event points where important things happen. As the line sweeps from left to right, points
are inserted, deleted, and may swap order along the sweep line. Thus, we reduce a static
2-dimensional problem to a dynamic 1-dimensional problem.
In any algorithm based on plane sweep there are three basic elements that need to be main-
tained (see Fig. 24). Let ℓ denote the current sweep line.

(1) the partial solution that has already been constructed to the left of ℓ (in our case, the
discovered intersection points lying to the left of the sweep line),
(2) the sweep-line status, that is, the set of objects intersecting ℓ (in our case, the sorted
segments intersecting the sweep line), and
(3) a subset of the future events lying to right of ℓ that are scheduled to be processed (in
our case, a subset of the intersection points to the right of the sweep line).

sweep line

discovered intersection point

future endpoint event

future intersection point event

(only some will be stored)

ℓ
Fig. 24: Plane sweep.

Lecture Notes 27
 The key to designing an efficient plane-sweep algorithm is determining how to efficiently store
and update these three elements as each new event is process. Let’s consider each of these
elements in greater detail in the context of line-segment intersection.

Sweep line status and above-below comparisons: We will simulate the sweeping of a vertical
line ℓ from left to right. The sweep-line status consists of the line segments that intersect the
sweep line sorted, say, from top to bottom. In order to maintain this set dynamically, we will
store them in an ordered dictionary.
But hey! How can we possibly do this efficiently? Every time we move the sweep line even
a tiny distance, all the y-coordinates of the intersection points change as well! Clearly, we
cannot store the y-coordinates explicitly, for otherwise we would be doomed to O(n) time per
event, which would lead to an overall running time that is at least quadratic.
The key is that we do not need store the actual y-coordinates in the dictionary. Instead,
we implement a function that compares two line segments at a given the x-coordinate. This
function determines which segment intersects the sweep line above the other. Let’s call this
a dynamic comparator. (A more detailed description is provided at the end of the lecture
notes.)
Observe that between consecutive event points (intersection points or segment endpoints) the
relative vertical order of segments is constant (see Fig. 25(a)). For each segment, we can
compute the associated line equation, and evaluate this function at x0 to determine which
segment lies on top. The ordered dictionary does not need actual numbers. It just needs a
way of comparing objects (see Fig. 25(b)).

Consistency of vertical order

x = x0
si si
yi(x0) = aix0 + bi

sj sj yj (x0) = aj x0 + bj

(a) (b)

Fig. 25: The dictionary does not need to store absolute y-coordinates, just the ability to make
above-below comparisons for any location of the sweep line.

Events and Detecting Intersections: It suffices to process events only when there is a change in
the combinatorial structure of the sweep-line status. As mentioned above, these x-coordinates
are called event points. For our application, we have three types of event points, corresponding
to when the sweep line encounters: (1) the left endpoint of a segment, (2) the right endpoint
of a segment, and (3) an intersection point between two segments.
Note that endpoint events ((1) and (2)) can be presorted before the sweep runs. In contrast,
intersection events (3) will be discovered dynamically as the sweep executes. It is important
that each event be detected before the actual event occurs. Since each pair of segments along
the sweep line might intersect, there are O(n2 ) potential intersection events to consider, which

Lecture Notes 28
 again would doom us to at least quadratic running time. How can we limit the number of
potential intersection points to a manageable number?
Our strategy will be as follows. Whenever two line segments become adjacent along the
sweep line (one immediately above the other), we will check whether they have an intersection
occurring to the right of the sweep line. If so, we will add this new event to a priority queue
of future events. This priority queue will be sorted in left-to-right order by x-coordinates.
We call this the adjacent-segment rule.
A natural question is whether this strategy of scheduling intersections between adjacent pairs
is correct. In particular, might it be that two line segments intersect, but just prior to this
intersection, they were not adjacent in the sweep-line status? If so, we would miss this event.
Happily, this is not the case, but it requires a proof. (If you think it is trivial, note that
it would fail to hold if the objects being intersected were general algebraic curves, not line
segments.)

Lemma: Consider a set S of line segments in general position, and consider two segments
si , sj ∈ S that intersect in some point p. Then si and sj are adjacent along the sweep
line just after the event that immediately precedes p in the sweep.
Proof: By our general position assumptions, no three lines intersect in a common point.
Therefore if we consider a placement of the sweep line that is infinitesimally to the left
of the intersection point, the line segments si and sj will be adjacent along this sweep
line. Consider the event point q with the largest x-coordinate that is strictly less than
px . Since there are no events between qx and px , there can be no segment intersections
within the vertical slab bounded by q on the left and p on the right (the shaded region
of Fig. 25), and therefore the order of lines along the sweep line after processing q will
be identical the order of the lines along the sweep line just prior p. Therefore, si and sj
are adjacent immediately after processing event q and remain so just prior to processing
p.

q
si

adjacent p

sj
ℓ
Fig. 26: Correctness of the adjacent-segment rule.

When two formerly adjacent segments cease to be adjacent (e.g., because a new segment is
discovered between them), we will delete the event from the queue. While this is not formally
necessary, it keeps us from inserting the same event point repeatedly and it guarantees that
the total number of events can never exceed O(n).

Data Structures: As mentioned above the segments that intersect the sweep line will be main-
tained in an ordered dictionary, sorted vertically from top to bottom. The future event
points (segment endpoints and impending intersection points) will be stored in a priority
queue, which will be ordered from left to right by x-coordinates.

Lecture Notes 29
 Here are the operations assumed to be supported by the ordered dictionary, which stores the
sweep-line status:

ˆ r ← insert(s): Insert s (represented symbolically) and return a reference r to its location

in the data structure.
ˆ delete(r): Delete the entry associated with reference r.
ˆ r′ ← predecessor(r): Return a reference r′ to the segment lying immediately above r (or
null if r is the topmost segment).
ˆ r′ ← successor(r): Return a reference r′ to the segment lying immediately below r (or
null if r is the bottommost segment).
ˆ r′ ← swap(r): Swap r and its immediate successor, returning a reference to r’s new
location.

Next, here are the operations assumed to be supported by the priority queue, which stores
the future events sorted by the x-coordinates:

ˆ r ← insert(e, x): Insert event e with “priority” x and return a reference r to its location
in the data structure.
ˆ delete(r): Delete the entry associated with reference r.
ˆ (e, x) ← extract-min(): Extract and return the event from the queue with the smallest
priority x.

As mentioned earlier, all of these operations can be performed in O(log n′ ) and O(n′ ) space,
where n′ is the current number of entries in the data structure.

The Final Algorithm: All that remains is explaining how to process the events. This is presented
in the code block below, and the various cases are illustrated in Fig. 26. (Further details can
be found in the 4M’s.)

Correctness: The correctness of the algorithm essentially follows from our extensive derivation to
the algorithm itself. Formally, the correctness proof is based on an induction proof showing
that immediately after processing each event: (a) the sweep-line status contains the line
segments intersecting the sweep line in sorted order and (b) the event queue contains exactly
all the events demanded by the adjacent-segment rule.

Analysis: Altogether, there are 2n + m events processed (two endpoints per segment and m inter-
sections). Each event involves a constant amount of work and a constant number of accesses
to our data structures. As mentioned above, each access to either of the data structures takes
O(log n) time. Therefore, the total running time is O((2n + m) log n) = O(n log n + m log n).
Note that if we output each intersection point without storing it, the total storage require-
ments never exceed O(n). In summary, we have:

Theorem: Given a set of n line segments S in the plane (subject to our general-position
assumptions), the above algorithm correctly reports all the m intersections between
these segments in time O((n + m) log n) time and O(n) space.

Lecture Notes 30
 Line Segment Intersection Reporting
(1) Insert all of the endpoints of the line segments of S into the event queue. The initial sweep-line status
is empty.
(2) While the event queue is nonempty, extract the next event in the queue. There are three cases,
depending on the type of event:
Left endpoint: (see Fig. 27(a))
(a) Insert this line segment s into the sweep-line status, based on the y-coordinate of its left
endpoint.
(b) Let s+ and s− be the segments immediately above and below s on the sweep line. If there is
an event associated with this pair, remove it from the event queue.
(c) Test for an intersection between s and s+ , and if so, add it to the event queue. Do the same
for s and s− .
Right endpoint: (see Fig. 27(b))
(a) Let s+ and s− be the segments immediately above and below s on the sweep line.
(b) Delete segment s from the sweep-line status.
(c) Test for an intersection between s+ and s− to the right of the sweep line, and if so, add the
corresponding event to the event queue.
Intersection: (see Fig. 27(c))
(a) Let s+ and s− be the two segments involved (with s+ above just prior to the intersection).
Report this intersection.
(b) Let s++ and s−− be the segments immediately above and below the intersection. Remove
any event involving the pair (s+ , s++ ) and the pair (s− , s−− ).
(c) Swap s+ and s− in the sweep-line status (they must be adjacent to each other).
(d) Test for an intersection between s− and s++ to the right of the sweep line, and if so, add it
to the event queue. Do the same for s+ and s−− .

left-endpoint event right-endpoint event intersection event

s5 s5 s5
s4 s4 s4 swap s3, s4
delete event
s3 insert s3 s3 s3
s2 s2
s2 add events delete s1
s1 s1
s0 ℓ s0 ℓ add event s0 ℓ
   
  s5 s5      
s5  s4   s4  s5 s5 s5
 s4       s4   s4   s3 
   s3   s3       
 s2       s3   s3   s4 
   s2   s2       
 s1       s2   s2   s2 
 s1   s1 
s0 s0 s0 s0
s0 s0
(a) (b) (c)

Fig. 27: Plane-sweep algorithm event processing.

Lecture Notes 31
Lower Bound: Is this the best possible? No. There is a faster algorithm (which we may discuss
later in the semester) that runs in time O(n log n + m). This latter algorithm is actually
optimal. Clearly Ω(m) time is needed to output the intersections. The lower bound of
Ω(n log n) results from a reduction from a problem called element uniqueness. In this problem,
we are give a list of n numbers X = ⟨x1 , . . . , xn ⟩ and we are asked whether there are any
duplicates (or all are distinct). Element uniqueness is known to have a lower bound of
Ω(n log n) in the algebraic decision-tree model of computation. (It can be solved in O(n)
time using hashing, but the algebraic decision-tree model does not allow integer division,
which is needed by hashing.)
The reduction involves converting each xi into a line segment si that passes through the
point (xi , 0), but otherwise there are no other intersections. (A little cleverness is needed to
guarantee that the general-position assumptions are satisfied.) Clearly, two segments si and
sj intersect if and only if two elements xi and xj of the list are identical. So, determining
whether there is even a single intersection requires at least Ω(n log n) time.

Dynamic Comparator: (Optional) Let’s consider how to design a function that compares two
line segments relative to the current sweep line. We are given the sweep line x = x0 and two
segments si and sj . Assuming each segment is nonvertical and has endpoints pi = (pi,x , pi,y )
and qi = (qi,x , qi,y ), we can compute the associated line equations ℓi : y = ai x + bi and
ℓj : y = aj x + bj , by solving the simultaneous equations

pi,y = ai pi,x + bi qi,y = ai qi,x + bi ,

which yields
pi,y − qi,y pi,x qi,y − pi,y qi,x
ai = bi = .
pi,x − qi,x pi,x − qi,x
By our general-position assumption, the segment is nonvertical, and the denominator is
nonzero.
Given that the sweep line is at x = x0 , we can define our dynamic comparator to be:

compare(si , sj ; x0 ) = sign((aj x0 + bj ) − (ai x0 + bi )),

which returns +1 if sj is above si , 0 if they coincide, and −1 if sj is below si .

This is the sign of a rationally-valued function, but we can multiply out the denominator to
obtain an algebraic function of degree-3 in the segment coordinates. Thus, if the coordinates
are expressed as integers, we can determine the sign using at most triple-precision arithmetic.

Computing Intersection Points: (Optional) We have assumed that the primitive of computing
the intersection point of two line segments can be performed exactly in O(1) time. Let us
see how we might do this. Let ab and cd be two line segments in the plane, given by their
endpoints, for example a = (ax , ay ). First observe that it is possible to determine whether
these line segments intersect, simply by applying an appropriate combination of orientation
tests. (We will leave this as an exercise.) However, this alone is not sufficient for the plane-
sweep algorithm.
One way to determine the point at which the segments intersect is to use a parametric
representation of the segments. Any point on the line segment ab can be written as a convex
combination involving a real parameter s:

p(s) = (1 − s)a + sb, for 0 ≤ s ≤ 1,

Lecture Notes 32
 and similarly for cd we may introduce a parameter t:

q(t) = (1 − t)c + td, for 0 ≤ t ≤ 1

(see Fig. 28).

c q(t) b
p(s) d
a
p(s) = q(t)

Fig. 28: Plane-sweep algorithm event processing.

An intersection occurs if and only if we can find s and t in the desired ranges such that
p(s) = q(t). Thus we obtain the two equations:

(1 − s)ax + sbx = (1 − t)cx + tdx and (1 − s)ay + sby = (1 − t)cy + tdy .

The coordinates of the points are all known, so it is just a simple exercise in linear algebra to
solve for s and t as functions of the coordinates of a, b, c, and d. (A solution may generally
not exist, but this means that the segments are parallel. By our assumption that no segments
are collinear, this implies that the segments do not intersect.) Once s and t are known, it
remains to just check with 0 ≤ s, t ≤ 1, to confirm that the intersection point occurs within
the line segment (and not in the extended infinite line).
As in our earlier example of determining the order of segments along the sweep line, if all
the coordinates are integers, this yields formulas for s and t as rational numbers, and hence
the coordinates of the intersection point are themselves rational numbers. If it is needed to
perform exact computations on these coordinates, rather than converting them to floating
point, it is possible to save the numerator and denominator of each coordinate as a pair of
(multiple precision) integers.

Lecture Notes 33