Lecture 4: Line Segment Intersection

Reading: Chapter 2 in the 4M's.

Geometric intersections: One of the most basic problems in
computational geometry is that of computing
intersections. Intersection computation in 2 and 3 space is basic to
many different application areas.  

  -- In solid modeling people often build up complex shapes by
applying various boolean operations (intersection, union, and
difference) to simple primitive shapes. The process in called
constructive solid geometry (CSG). In order to perform these
operations, the most basic step is determining the points where the
boundaries of the two objects intersect.

  -- 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 responsibilities lie). Since these
networks are formed from collections of line segments, this generates
a problem of determining intersections of line segments.

  -- In computer graphics, ray shooting is an important method for
rendering scenes. The computationally most intensive part of ray
shooting is determining the intersection of the ray with other
objects.

Most complex intersection problems are broken down to successively
simpler and simpler inter section problems. Today, we will discuss the
most basic algorithm, upon which most complex algorithms are based.

Line segment intersection: The problem that we will consider is, given
n line segments in the plane, report all points where a pair of line
segments intersect. We assume that each line segment is represented by
giving the coordinates of its two endpoints.  Observe that n line
segments can intersect in as few as 0 and as many as (n choose 2) =
O(n^2) different intersection points.

We could settle for an O(n^2) algorithm, claiming that it is worst
case asymptotically optimal, but it would not be very useful in
practice, since in many instances of intersection problems
intersections may be rare. Therefore it seems reasonable to look for
an output sensitive algorithm, that is, one whose running time should
be efficient both with respect to input and output size.

Let I denote the number of intersections. We will assume that the line
segments are in general position, and so we will not be concerned with
the issue of whether three or more lines intersect in a single
point. However, generalizing the algorithm to handle such degeneracies
efficiently is an interesting exercise. See our book for more
discussion of this.  Complexity: We claim that best worst case running
time that one might hope for is O(n log n+ I) time algorithm. Clearly
we need O(I) time to output the intersection points. What is not so
obvious is that O(n log n) time is needed. This results from the fact
that the following problem is known to require O( n log n) time in the
algebraic decision tree model of computation.


Element uniqueness: Given a list of n real numbers, are all of these
numbers distinct?  (That is, are there no duplicates.)

REDUCTION:

Given a list of n numbers, (x1, x2, ..., xn ), in O(n) time we
can construct a set of n vertical line segments, all having the same y
coordinates. Observe that if the numbers are distinct, then there are
no intersections and otherwise there is at least one
intersection. Thus, if we could detect intersections in o(n log n)
time (meaning strictly faster than Theta(n log n) time) then we could
solve element uniqueness in faster than o(n log n) time. However, this
would contradict the lower bound on element uniqueness.  We will
present a (not quite optimal) O(n log n + I log n) time algorithm for
the line segment intersection problem. A natural question is whether
this is optimal. Later in the semester we will discuss an optimal
radomized O(n log n + I) time algorithm for this problem.

* Note, this lower bound result assumes the algebraic decision tree
model of computation, in which all decisions are made by comparisons
made based on exact algebraic operations, (+,-,/,*) applied to numeric
inputs.  Althought this includes most "normal" geometric operations,
there are alternative models... by taking mods, floors or ceilings,
you can implement a hashing function which can check for element
uniqueness in expected O(n) time.  Even in this model, however, no-one
knows an algorithm better than 0(n log n + I).

Line segment intersection: In rather typical computational geometry
fashion, our book does not discuss the issue of how to determine the
intersection point of two line segments. Let ab and cd be two line
segments, given by their endpoints. It is an easy exercise to
determine whether these line segments intersect, simply by applying an
appropriate combination of orientation tests.  To determine the
coordinates of the intersect point involves solving a small system of
equations.  The most natural way to set up this computation is to
introduce the notion of a parametric representation of the line
segment. Recall that 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:

Similarly for cd we may introduct a parameter t:
q(t) = (1 - t)c + td for 0 <= s <= 1:

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 get the two equations:

(1 - s)ax + s bx = (1 - t) cx + t dx
(1 - s)ay + s by = (1 - t) cy + t dy 

The coordinates of the points are all known, so it is just a simple
exercise in linear algebra to solve for s and t. The computation of s
and t will involve a division. If the divisor is 0, this corresponds
to the case where the line segments are parallel (and possibly
collinear).  These special cases should be dealt with carefully. If
the divisor is nonzero, then we get values for s and t as rational
numbers (the ratio of two integers). We can approximate them as
floating point numbers, or if we want to perform exact computations it
is possible to simulate rational number algebra exactly using high
precision integers (and multiplying through by least common
multiples). Once the values of s and t have been computed all that is
needed is to check that both are in the interval [0; 1].

Plane Sweep Algorithm: Let S = (s1, s2, ..., sn) denote the line
segments whose intersections we wish to compute. The method is called
plane sweep. Here are the main elements of any plane sweep algorithm,
and how we will apply them to this problem: 

Sweep line: We will simulate the sweeping of a vertical line L, called
the sweep line from left to right. (Our text uses a horizontal line,
but there is obviously no significant difference.)  We will maintain
the line segments that intersect the sweep line in sorted order (say
from top to bottom).

Events: Although we might think of the sweep line as moving
continuously, we only need to update data structures at points of some
significant change in the sweep line contents, called event points.
Different applications of plane sweep will have different notions of
what event points are.

For this application, event points will correspond to the following:

Endpoint events: where the sweep line encounters an endpoint of a line
segment, and 

Intersection events: where the sweep line encounters an intersection
point of two line segments.

Note that endpoint events can be presorted before the sweep runs. In
contrast, intersection events will be discovered as the sweep
executes.

Event updates: When an event is encountered, we must update the data
structures associated with the event. It is a good idea to be careful
in specifying exactly what invariants you intend to maintain. For
example, when we encounter an intersection point, we must interchange
the order of the intersecting line segments along the sweep line.
There are a great number of nasty special cases that complicate the
algorithm and obscure the main points. We will make a number of
simplifying assumptions. They can be overcome through a more careful
handling of these cases.

(1) No line segment is vertical.

(2) If two segments intersect, then they intersect in a single point
                              (that is, they are not collinear).

(3) No three lines intersect in a common point.


Detecting intersections: We mentioned that endpoint events are all
known in advance. But how do we detect intersection events. It is
important that each event be detected before the actual intersection
event occurs. Our strategy will be as follows. Whenever two line
segments become adjacent along the sweep line, we will check whether
they have an intersection occuring to the right of the sweep line. If
so, we will add this new event (assuming that it has not already been
added).  A natural question is whether this is sufficient. In
particular, if two line segments do intersect, is there necessarily
some prior placement of the sweep line such that they are
adjacent. Happily, this is the case, but it requires a proof.


Figure 17: Plane sweep.

Lemma: Given two segments si and sj , which intersect in a single
point p (and assuming no other line segment passes through this point)
there is a placement of the sweep line prior to this event, such that
si and sj are adjacent along the sweep line (and hence will be
tested for intersection).  

Proof: From our general position assumption it follows that no three
lines intersect in a com mon point. Therefore if we consider a
placement of the sweep line that is infinitessimally to the left of
the intersection point, lines si and sj will be adjacent along this
sweepline.  Consider the event point q with the largest x coordinate
that is strictly less than px . The order of lines along the sweep
line after processing q will be identical the the order of the lines
along the sweep line just prior p, and hence si and sj will be
adjacent at this point.


Figure 18: Correctness of plane sweep.


Data structures: In order to perform the sweep we will need two data
structures.

Event queue: This holds the set of future events, sorted according to
increasing x coordinate.  Each event contains the auxiliary
information of what type of event this is (segment endpoint or
intersection) and which segment(s) are involved. The operations that
this data structure should support are inserting an event (if it is
not already present in the queue) and extracting the minimum event.
It seems like a heap data structure would be ideal for this, since it
supports insertions and extract min in O(log M ) time, where M is the
number of entries in the queue. (See Cormen, Leiserson, and Rivest for
details). However, a heap cannot support the operation of checking for
duplicate events.  There are two ways to handle this. One is to use a
more sophisticated data structure, such as a balanced binary tree or
skip list. This adds a small constant factor, but can check that there
are no duplicates easily. The second is use the heap, but when an
extraction is performed, you may have to perform many extractions to
deal with multiple instances of the same event. Our book recommends
the prior solution.  If events have the same x coordinate, then we can
handle this by sorting points lexico graphically by (x, y). (This
results in events be processed from bottom to top along the sweep
line, and has the same geometric effect as imagining that the sweep
line is rotated infinitesimally counterclockwise.)


Sweep line status: To store the sweep line status, we maintain a
balanced binary tree or perhaps a skiplist whose entries are pointers
to the line segments, stored in decreasing order of y coordinate along
the current sweep line.  Normally when storing items in a tree, the
key values are constants. Since the sweep line varies, we need
``variable'' keys. To do this, let us assume that each line segment
computes a line equation y = mx + b as part of its representation. The
``key'' value in each node of the tree is a pointer to a line
segment. To compute the y coordinate of some segment at the location
of the current sweep line, we simply take the current x coordinate of
the sweep line and plug it into the line equation for this line.  The
operations that we need to support are those of deleting a line
segment, inserting a line segment, swapping the position of two line
segments, and determining the immediate predecessor and successor of
any item. Assuming any balanced binary tree or a skiplist, these
operations can be performed in O(log n) time each.


The Complete Algorithm: We can now present the complete plane sweep algorithm.

Plane Sweep Algorithm for Line Segment Intersection

Intersect(S) :

(1) Initially, we insert all of the endpoints of the line segments of
S into the event queue. The initial sweep 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:

Segment left endpoint: Insert this line segment into the sweep line
status, based on the y coordinate of this endpoint and the y
coordinates of the other segments currently along the sweep line. Test
for intersections with the segment immediately above and below.

Segment right endpoint: Delete this line segment from the sweep line
status. For the entries immediately preceding and succeeding this
entry, test them for intersections.

Intersection point: Swap the two line segments in order along the
sweep line. For the new upper segment, test it against its predecessor
for an intersection. For the new lower segment, test it against its
successor for an intersection.

Analysis: The work done by the algorithm is dominated by the time
spent updating the various data structures (since otherwise we spend
only constant time per sweep event). We need to count two things: the
number of operations applied to each data structure and the amount of
time needed to process each operation.  For the sweep line status,
there are at most n elements intersecting the sweep line at any time,
and therefore the time needed to perform any single operation is
O(logn), from standard results on balanced binary trees.  Since we do
not allow duplicate events to exist in the event queue, the total
number of elements in the queue at any time is at most 2n + I. Since
we use a balanced binary tree to store the event queue, each operation
takes time at most logarithmic in the size of the queue, which is

O(log(2n + I)). Since I <= n^2 , this is at most 

O(log(n^2) ) = O(2 log n) = O(log n) time.

Each event involves a constant number of accesses or operations to the
sweep status or the event queue, and since each such operation takes
O(log n) time from the previous paragraph, it follows that the total
time spent processing all the events from the sweep line is

O((2n + I) log n) = O((n + I) log n) = O(n log n + I log n):

Thus, this is the total running time of the plane sweep algorithm.


This course is modeled on the Computational Geometry Course taught by Dave Mount, at the University of Maryland. These notes are modifications of his Lecture Notes, which are copyrighted as follows: Copyright, David M. Mount, 2000, Dept. of Computer Science, University of Maryland, College Park, MD, 20742. These lecture notes were prepared by David Mount for the course CMSC 754, Computational Geometry, at the University of Maryland, College Park. Permission to use, copy, modify, and distribute these notes for educational purposes and without fee is hereby granted, provided that this copyright notice appear in all copies.