Computational_Geometry

s.
We did not talk about the new face records yet. The information for these
records is more difficult to compute, so we leave this for later. We first de-
scribe in a little more detail how the vertex and half-edge records of the doubly-
connected edge list for O(Sl, S2) are computed.
Our algorithm is based on the plane sweep algorithm of Section 2.1 for com-
puting the intersections in a set of line segments. We run this algorithm on the
set of segments that is the union of the sets of edges of the two subdivisions
S1 and Sz. Here we consider the edges to be closed. Recall that the algorithm
is supported by two data structures: an event queue Q, which stores the event
points, and the status structure I, which is a balanced binary search tree stor-
ing the segments intersecting the sweep line, ordered from left to right. We
now also maintain a doubly-connected edge list 1). Initially, 2) contains a copy
of the doubly-connected edge list for S1 and a copy of the doubly-connected
edge list for S2. During the plane sweep we shall transform 'D to a correct
doubly-connected edge list for O(S1,S2). That is to say, as far as the vertex
and half-edge records are concerned; the face information will be computed
later. We keep cross pointers between the edges in the status structure I and
the half-edge records in I) that correspond to them. This way we can access the
part of fD that needs to be changed when we encounter an intersection point.
The invariant that we maintain is that at any time during the sweep, the part of Section 2.3
the overlay above the sweep line has been computed correctly. COMPUTING THE OVERLAY OF TWI
Now, let's consider what we must do when we reach an event point. First SUBDIVISIONS
of all, we update I and Q as in the line segment intersection algorithm. If
the event involves only edges from one of the two subdivisions, this is all; the
event point is a vertex that can be re-used. If the event involves edges from both
subdivisions, we must make local changes to I) to link the doubly-connected
edge lists of the two original subdivisions at the intersection point. This is
tedious but not difficult.
the geometric situation and the
two doubly-connected edge lists the doubly-connected edge list
before handling the intersection after handling the intersection
We describe thE details for one of the possible cases, namely when an edge
e of S1 passes through a vertex v of S2, see Figure 2.5. The edge e must be
replaced by two edges denoted e' and el1. In the doubly-connected edge list, the
two half-edges for e must become four. We create two new half-edge records,
both with v as the origin. The two existing half-edges for e keep the endpoints
of e as their origin, as shown in Figure 2.5. Then we pair up the existing
half-edges with the new half-edges by setting their Twin() pointers. So el is
represented by one new and one existing half-edge, and the same holds for el1.
Now we must set a number of Prev() and Next() pointers. We first deal with
the situation around the endpoints of e; later we'll worry about the situation
around v. The Next() pointers of the two new half-edges each copy the Next()
pointer of the old half-edge that is not its twin. The half-edges to which these
pointers point must also update their Prev() pointer and set it to the new half-
edges. The correctness of this step can be verified best by looking at a figure.
It remains to correct the situation around vertex v. We must set the Next()
and Prev() pointers of the four half-edges representing e' and el1, and of the
four half-edges incident from 5 to v. We locate these four half-edges from S2
by testing where el and e" should be in the cyclic order of the edges around
vertex v. There are four pairs of half-edges that become linked by a Next()
pointer from the one and a Prev() pointer from the other. Consider the half-
edge for e' that has v as its destination. It must be linked to the first half-edge,
seen clockwise from e', with v as its origin. The half-edge for e' with v as
first clockwise half-edge
its origin must be linked to the first counterclockwise half-edge with v as its
from e' with v as its origin
destination. The same statements hold?& el1.
Most of the steps in the description above take only constant time. Only
locating where e' and e" appear in the cyclic order around v may take longer: 35
Chapter2
it will take time linear in the degree of v. The other cases that can arise-
LINE SEGMENT INTERSECTION crossings of two edges from different maps, and coinciding vertices-are not
more difficult than the case we just discussed. These cases also take time O(m),
where m is the number of edges incident to the event point. This means that
updating 9 does not increase the running time of the line segment intersection
algorithm asymptotically. Notice that every intersection that we find is a vertex
of the overlay. It follows that the vertex records and the half-edge records of
the doubly-connected edge list for O(S1 ,SZ) can be computed in O(n1ogn -t
klogn) time, where n denotes the sum of the complexities of Sl and S2, and k
is the complexity of the overlay.
After the fields involving vertex and half-edge records have been set, it remains
to compute the information about the faces of O(S1, &) . More precisely, we
have to create a face record for each face f in O(S1,S2), we have to make
OuterComponent(f) point to a half-edge on the outer boundary of f, and
we have to make a list InnerComponents(f) of pointers to half-edges on the
boundaries of the holes inside f. Furthermore, we must set the IncidentFace()
fields of the half-edges on the boundary off so that they point to the face
record off. Finally, each of the new faces must be labeled with the names of
the faces in the old subdivisions that contain it.
How many face records will there be? Well, except for the unbounded face,
every face has a unique outer boundary, so the number of face records we have
to create is equal to the number of outer boundaries plus one. From the part
of the doubly-connected edge list we have constructed so far we can easily
extract all boundary cycles. But how do we know whether a cycle is an outer
boundary or the boundary of a hole in a face? This can be decided by looking at
the leftmost vertex v of the cycle, or, in case of ties, at the lowest of the leftmost
ones. Recall that half-edges are directed in such a way that their incident face
locally lies to the left. Consider the two half-edges of the cycle that are incident
to v. Because we know that the incident face lies to the left, we can compute
the angle these two half-edges make inside the incident face. If this angle is
smaller than 180" then the cycle is an outer boundary, and otherwise it is the
boundary of a hole. This property holds for the leftrnost vertex of a cycle, but
not necessarily for other vertices of that cycle.
To decide which boundary cycles bound the same face we construct a
graph 9. For every boundary cycle-inner and outer-there is a node in 9.
There is also one node for the imaginary outer boundary of the unbounded
face. There is an arc between two cycles if and only if one of the cycles is the
boundary of a hole and the other cycle has a half-edge immediately to the left
of the leftmost vertex of that hole cycle. If there is no half-edge to the left of
the leftmost vertex of a cycle, then the node representing the cycle is linked to
the node of the unbounded face. Figure 2.6 gives an example. The dotted seg-
ments in the figure indicate the linking of the hole cycles to other cycles. The
graph corresponding to the subdivision is also shown in the figure. The hole
cycles are shown as single circles, and the outer boundary cycles are shown as
double circles. Observe that C3 and Ctj are in the same connected component
as C2. This indicates that C3 and 6 are hole cycles in the face whose outer
Section 2.3
COMPUTING THE OVERLAY OF T'
1
SUBDIVISIONS
boundary is C2. If there is only one hole in a face f, then the graph 9 links
the boundary cycle of the hole to the outer boundary off. In general this need
not be the case: a hole can also be linked to another hole, as you can see in
Figure 2.6. This hole, which lies in the same face f, may be linked to the outer
boundary off, or it may be linked to yet another hole. But eventually we must
end up linking a hole to the outer boundary, as the next lemma shows.
Lemma 2.5 Each connected component of the graph corresponds exactly
to the set of cycles incident to one face.
i
A subdivision and the corresponding
graph G \
1
Prooj Consider a cycle C bounding a hole in a face f. Because f lies locally
to the left of the leftrnost vertex of C, C must be linked to another cycle that
also bounds f. It follows that cycles in the same connected component of F
bound the same face.
To finish the proof, we show that every cycle bounding a hole in f is in
the same connected component as the outer boundary of f. Suppose there is
a cycle for which this is not the case. Let C be the leftmost such cycle, that
is, the one whose the leftmost vertex is leftmost. By definition there is an arc
between the C and another cycle C' that lies partly to the left of the leftmost
vertex of C. Hence, C' is in the same connected component as C, which is
not the component of the outer boundary off. This contradicts the definition
of C. . el
Lemma 2.5 shows that once we have the graph G, we can create a face record
for every component. Then we can set the IncidentFace() pointers of the half-
Chapter 2
edges that bound each face f, and we can construct the list InnerComponents( f)
1 LINE SEGMENT INTERSECTION and the set OuterComponent(f). How can we construct ij? Recall that in the
1
plane sweep algorithm for line segment intersection we always looked for the
segments immediately to the left of an event point. (They had to be tested for
intersection against the leftmost edge through the event point.) Hence, the in-
formation we need to construct G is determined during the plane sweep. So,
to construct 9, we first make a node for every cycle. To find the arcs of ij,
we consider the leftmost vertex v of every cycle bounding a hole. If e' is the
half-edge immediately left of v, then we add an arc between the two nodes in
G representing the cycle containing e' and the hole cycle of which v is the left-
most vertex. To find these nodes in efficiently we need pointers from every
half-edge record to the node in G representing the cycle it is in. So the face
information of the doubly-connected edge list can be set in O(n + k) additional
time, after the plane sweep.
One thing remains: each face f in the overlay must be labeled with the names
of the faces in the old subdivisions that contained it. To find these faces, con-
sider an arbitrary vertex v off. If v is the intersection of an edge el from S1
and an edge e2 from S2 then we can decide which faces of Sl and S2 contain f
by looking at the IncidentFace() pointer of the appropriate half-edges corre-
sponding to el and e2. If v is not an intersection but a vertex of, say, Sl, then
we only know the face of S1 containing f. To find the face of S2 containing
f, we have to do some more work: we have to determine the face of S2 that
contains v. In other words, if we knew for each vertex of Sl in which face of
S;! it lay, and vice versa, then we could label the faces of O(SL ,S2) correctly.
How can we compute this information? The solution is to apply the paradigm
that has been introduced in this chapter, plane sweep, once more. However, we
won't explain this final step here. It is a good exercise to test your understand-
ing of the plane sweep approach to design the algorithm yourself. (In fact, it
is not necessary to compute this information in a separate plane sweep. It can
also be done in the sweep that computes the intersections.)
I
Putting everything together we get the following algorithm.
Algorithm MAPOVERLAY(S~, S2)
Input. Two planar subdivisions S1 and S2 stored in doubly-connected edge lists.
'Gt. The overlay of Sl and & stored in a doubly-connected edge list 9.
1. Copy the doubly-connected edge lists for S1 and S2 to a new doubly-
connected edge list 9.
2. Compute all intersections between edges from S1 and 5 with the plane
sweep algorithm of Section 2.1. In addition to the actions on I and Q
required at the event points, do the following:
m Update 9 as explained above if the event involves edges of both Sl
and Sz. (This was explained for the case where an edge of S1 passes
through a vertex of S2.)
m Store the half-edge immediately to the left of the event point at the
vertex in D representing it.
3. (* Now 2) is the doubly-connected edge list for O(Sl, S2), except that the
Section 2.4
information about the faces has not been computed yet. *)
BOOLEAN OPERATIONS
4. Determine the boundary cycles in O(Sl, 52) by traversing 2).
5. Construct the graph G whose nodes correspond to boundary cycles and
whose arcs connect each hole cycle to the cycle to the left of its leftmost
vertex, and compute its connected components. (The information to de-
termine the arcs of ij has been computed in line 2, second item.)
6. for each connected component in
7. do Let C be the unique outer boundary cycle in the component and let
f denote the face bounded by the cycle. Create a face record for f,
set OuterComponent( f) to some half-edge of C, and construct the
list InnerComponents( f) consisting of pointers to one half-edge in
each hole cycle in the component. Let the IncidentFace() pointers
of all half-edges in the cycles point to the face record off.
8. Label each face of O(Sl,&) with the names of the faces of S1 and S2
containing it, as explained above.
Theorem 2.6 Let Sl be a planar subdivision of complexity nl, let be a sub-
division of comp nl + n2. The overlay of Sl and S2 can
be constructed in time, where k is the complexity of the
overlay.
ProoJ: Copying the doubly-connected edge lists in line 1 takes O(n) time, and
the plane sweep of line 2 takes O(nlogn+ klogn) time by Lemma 2.3. Steps 4-
7, where we fill in the face records, takes time linear in the complexity of
O(S1 ,&). (The connected components of a graph can be determined in linear
time by a simple depth first search.) Finally, labeling each face in the resulting
subdivision with the faces of the original subdivisions that contain it can be
done in O(n logn + klogn) time. e]
2.4 Boolean Operations
i
The map overlay algorithm is a powerful instrument that can be used for var-
I
ious other applications. One particular useful one is performing the Boolean
operations union, intersection, and difference on two polygons Tl and T2. See
Figure 2.7 for an example. Note that the output of the operations might no
longer be a polygon. It can consist of a number of polygonal regions, some
with holes.
To perform the Boolean operation we regard the polygons as planar maps
whose bounded faces are labeled Tl and T2, respectively. We compute the
overlay of these maps, and we extract the faces in the overlay whose labels
correspond to the particular Boolean operation we want to perform. If we want
to compute the intersection Tl "1 T2, we extract the faces in the overlay that are
labeled with Pl and T2. If we want to compute the union Pl U T2, we extract the
faces in the overlay that are labeled with Tl or T2. And if we want to compute
Chapter 2
LINE SEGMENT INTERSECTION
union
- -
- - -1 _----I
I I
I I
I I
1 9'2 19
Figure 2.7
I I
I I
J
The Boolean operations union, _ - - ..- + I
I ---
intersection and difference on two
I_--
polygons TI and T2 intersection
I ----
I-*-
difference
the difference Tl \ T2, we extract the faces in the overlay that are labeled with
TI and not with T2.
Because every intersection point of an edge of Tl and an edge of T2 is
a vertex of Tl n T2, the running time of the algorithm is O(n logn + klog n),
where n is the total number of vertices in Tl and T2, and k is the complexity of
TI n T2. The same holds for the other Boolean operations: every intersection
of two edges is a vertex of the final result, no matter which operation we want
to perform. We immediately get the following result.
Corollary 2.7 Let Tl be a polygon with nl vertices and T2 a polygon with n2
vertices, and let n := nl + n2. Then TI n T2, TI U T2, and TI \ T2 can each be
computed in O(n logn + klogn) time, where k is the complexity of the output.
2.5 Notes and Comments
The line segment intersection problem is one of the fundamental problems in
computational geometry. The O(n1ogn + klogn) solution presented in this
chapter was given by Bentley and Ottmann [35] in 1979. (A few years earlier,
Shamos and Hoey [312] had solved the detection problem, where one is only
interested in deciding whether there is at least one intersection, in O(n1ogn)
time.) The method for reducing the working storage from O(n + k) to O(n)
described in this chapter is taken from Pach and Sharir [276]. Brown [56]
describes an alternative method to achieve the reduction.
The lower bound for the problem of reporting all Iine segment intersec-
tions is R(n1ogn + k), so the plane sweep algorithm described in this chapter
is not optimal when k is large. A first step towards an optimal algorithm was
taken by Chazelle [67], who gave an algorithm with 0(nlo2 n/ loglogn + k)
running time. In 1988 Chazelle and Edelsbrunner [78, 791 presented the first
O(n log n + k) time algorithm. Unfortunately, it requires O(n + k) storage. Later Section 2.5
Clarkson and Shor [l 1 11 and Mulmuley [254] gave randomized incremental al- NOTES AND COMMENTS
i
gorithms whose expected running time is also O(n log n + k). (See Chapter 4 1
for an explanation of randomized algorithms.) The working storage of these al-
gorithms is O(n) and O(n + k), respectively. Unlike the algorithm of Chazelle
and Edelsbrunner, these randomized algorithms also work for computing in-
i
tersections in a set of curves. Recently Balaban [23] gave a new determin-
1
istic algorithm for the segment intersection problem. His algorithm works in
t
O(n1ogn + k) time and it uses O(n) space. Hence, it is the first deterministic
algorithm that is optimal both with respect to time and with respect to storage.
i
It also works for curves.
There are cases of the line segment intersection problem that are easier than
i
the general case. One such case is where we have two sets of segments, say
red segments and blue segments, such that no two segments from the same set
I
intersect each other. (This is, in fact, exactly the network overlay problem.
I
In the solution described in this chapter, however, the fact that the segments
came from two sets of non-intersecting segments was not used.) This so-called
1
red-blue Iine segment intersection problem was solved in O(n1ogn + k) time
and O(n) storage by Mairson and Stolfi [226] before the general problem was
solved optimally. Other optimal red-blue intersection algorithms were given
1 i
by Chazelle et al. [80] and by Palazzi and Snoeyink [278]. If the two sets of
segments form connected subdivisions then the situation is even better: in this
case the overlay can be computed in O(n + k) time, as has been shown by Finke
and Hinrichs [145]. Their result generalizes and improves previous results on
1
map overlay by Nievergelt and Preparata [258], Guibas and Seidel [168], and
Mairson and Stolfi [226].
In this chapter we described a data structure for storing subdivisions: the
doubly-connected edge list. This structure, or in fact a variant of it, was de-
scribed by Muller and Preparata [252]. There are also other data structures for
storing subdivisions, such as the winged edge structure by Baumgart [28] and
Plane sweep is one of the most important paradigms for designing geomet-
ric algorithms. The first algorithms in computational geometry based on this
paradigm are by Shamos and Hoey [312], Lee and Preparata [215], and Bent-
ley and Ottmann [35]. Plane sweep algorithms are especially suited for finding
\
intersections in sets of objects, but they can also be used for solving many other
problems. In Chapter 3 plane sweep solves part of the polygon triangulation
1
problem, and in Chapter 7 we will see a plane sweep algorithm to compute the
so-called Voronoi diagram of a set of points. The algorithm presented in the
t
current chapter sweeps a horizontal line downwards over the plane. For some
1
problems it is more convenient to sweep the plane in another way. For instance,
i
i
we can sweep the plane with a rotating line-see Chapter 15 for an example-
or with a pseudo-line (a line that need not be straight, but otherwise behaves
more or less as a line) [130]. The plane sweep technique can also be used in
higher dimensions: here we sweep the space with a hyperplane [180,275,287].
Such algorithms are called space sweep algorithms.
2.9 Suppose that a doubly-connected edge list of a connected subdivision is
given. Give pseudocode to list all faces with vertices that appear on the
outer boundary.
Chapter 2
the quad edge structure by Guibas and Stolfi [17 11. The difference between all
LINE SEGMENT INTERSECTION these structures is small. They all have more or less the same functionality, but
Section 2.6
EXERCISES