Computational_Geometry

ts lying to the right of the current
event ~oint. Hence. the ~rocedure FINDNEWEVENT is defined as follows.
, L
low the sweep line, or on it and to the right of the
q~
current event point p, and the intersection is not yet present as an
then Insert the i
What about the correctness of our algorithm? It is clear that FINDINTERSEC-
I
TIONS only reports true intersection points, but does it find all of them? The
next lemma states that this is indeed the case.
Lemma 2.2 Algorithm FINDINTERSECTIONS computes all intersection points
ments are stored with the event point p. (For horizontal segments, the
and the segments that contain it correctly.
S(p) of all segments that contain p; they are adja- Pro05 Recall that the priority of an event is given by its y-coordinate, and that
cent in I. Let L(p) C S(p) be the set of segments whose lower endpoint
is p, and let C(p) C S(p) be the set of segments that contain p in their
interior.
3. contains more than one segment
4. intersection, together with L(p): U(p), and C(p).
Delete the segments in L(p) U C(p) from I.
Insert the segments in U(p) U C(p) into I. The order of the segments in
I should correspond to the order in which they are intersected by a sweep
line just below p. If there is a horizontal segment, it comes last among all
-
segments containing p.
(* Deleting and re-inserting the segments of C(p) reverses their order. *)
if U (p) U C(p) = 0
then Let sl and s, be the left and right neighbors of p in I.
FINDNEWEVENT(S[, s,, p)
else Let s' be the leftmost segment of U(p) U C(p) in I.
Let sl be the left neighbor of s' in I.
FINDNEWEVENT(S[, d, p)
Let s" be the rightmost segment of U(p) U C(p) in I.
Let s, be the right neighbor of s" in I.
FINDNEWEVENT(S'~, s,,P)
when two events have the same y-coordinate the one with smaller x-coordinate
is given higher priority. We shall prove the lemma by induction on the priority
of the event points.
Let p be an intersection point and assume that all intersection points q with
a higher priority have been computed correctly. We shall prove that p and
1
the segments that contain p are computed correctly. Let U(p) be the set of
I
segments that have p as their upper endpoint (or, for horizontal segments, their
8
left endpoint), let L(p) be the set of segments having p as their lower endpoint
(or, for horizontal segments, their right endpoint), and let C(p) be.the set of
segments having p in their interior.
,
First, assume that p is an endpoint of one or more of the segments. In
I
that case p is stored in the event queue Q at the start of the algorithm. The
-
segments from U(p) are stored with p, so they will be found. The segments
from L(p) and C(p) are stored in I when p is handled, so they will be found in
line 2 of HANDLEEVENTPOINT. Hence, p and all the segments involved are
determined correctly when p is an endpoint of one or more of the segments.
Now assume that p is not an endpoint of a segment. All we need to show is
that p will be inserted into Q at some moment. Note that all segments that are
involved have p in their interior. Order these segments by angle around p, and
I let si and sj be two neighboring segments. Following the proof of Lemma 2.1
Chapter 2
we see that there is an event point with a higher priority than p such that si and
LINE SEGMENT INTERSECTION sj become adjacent when q is passed. In Lemma 2.1 we assumed for simplicity
that si and sj are non-horizontal, but it is straightforward to adapt the proof for
horizontal segments. By induction, the event point q was handled correctly,
which means that p is detected and stored into Q. e]
So we have a correct algorithm. But did we succeed in developing an output-
sensitive algorithm? The answer is yes: the running time of the algorithm is
O((n + k) logn), where k is the size of the output. The following lemma states
an even stronger result: the running time is O((n + I)logn), where I is the
number of intersections. This is stronger, because for one intersection point
the output can consist of a large number of segments, namely in the case where
many segments intersect in a common point.
Lemma 2.3 The running time of Algorithm FINDINTERSECTIONS for a set S
of n line segments in the plane is O(n log n + Ilogn), where I is the number of
intersection points of segments in S.
Pro05 The algorithm starts by constructing the event queue on the segment
j
endpoints. Because we implemented the event queue as a balanced binary
search tree, this takes O(n1ogn) time. Initializing the status structure takes
constant time. Then the plane sweep starts and all the events are handled. To
handle an event we perform three operations on the event queue Q. the event
itself is deleted from Qin line 4 of FINDINTERSECTIONS, and there can be one
or two calls to FINDNEWEVENT, which may cause at most two new events to
be inserted into Q. Deletions and insertions on Q take O(1og n) time each. We
also perform operations-insertions, deletions, and neighbor finding---on the
status structure I, which take O(1ogn) time each. The number of operations
is linear in the number m(p) := card(L(p) U U(p) U C(p)) of segments that are
involved in the event. If we denote the sum of all m(p), over all event points p,
by m, the running time of the algorithm is O(m log n).
I
It is clear that m = O(n + k), where k is the size of the output; after all,
whenever m(p) > 1 we report all segments involved in the event, and the only
events involving one segment are the endpoints of segments. But we want
to prove that m = O(n +I), where I is the number of intersection points. To
show this, we will interpret the set of segments as a planar graph embedded in
1
the plane. (If you are not familiar with planar graph terminology, you should
I
read the first paragraphs of Section 2.2 first.) Its vertices are the endpoints of
segments and intersection points of segments, and its edges are the pieces of
the segments connecting vertices. Consider an event point p. It is a vertex of
the graph, and m(p) is bounded by the degree of the vertex. Consequently, m is
!
bounded by the sum of the degrees of all vertices of our graph. Every edge of
the graph contributes one to the degree of exactly two vertices (its endpoints), I
so m is bounded by 2ne, where n, is the number of edges of the graph. Let's
I
bound n, in terms of n and I. By definition, n,, the number of vertices, is at
most 2n + I. It is well known that in planar graphs n, = O(n,), which proves
our claim. But, for completeness, let us give the argument here. Every face I
of the planar graph is bounded by at least three edges-provided that there are
at least three segments-and an edge can bound at most two different faces.
Therefore nj, the number of faces, is at most 2ne/3. We now use Euler's
formula, which states that for any planar graph with n, vertices, n, edges, and
nf faces, the following relation holds:
,'?
Equality holds if and only if the graph is connected. Plugging the bounds on
n, and nf into this formula, we get
So n, < 6n + 31 - 6, and m < 12n + 61 - 12, and the bound on the running time
follows. €!I
We still have to analyze the other complexity aspect, the amount of storage
used by the algorithm. The tree I stores a segment at most once, so it uses
O(n) storage. The size of Q can be larger, however. The algorithm inserts
intersection points in Q when they are detected and it removes them when they
are handled. When it takes a long time before intersections are handled, it
could happen that Q gets very large. Of course its size is always bounded by
O(n +I), but it would be better if the working storage were always linear.
There is a relatively simple way to achieve this: only store intersection
points of pairs of segments that are currently adjacent on the sweep line. The
algorithm given above also stores intersection points of segments that have
been horizontally adjacent, but aren't anymore. By storing only intersections
among adjacent segments, the number of event points in Q is never more than
linear. The modification required in the algorithm is that the intersection point
of two segments must be deleted when they stop being adjacent. These seg-
ments must become adjacent again before the intersection point is reached, so
the intersection point will still be reported correctly. The total time taken by
the algorithm remains O(n1ogn + Ilogn). We obtain the following theorem:
Theorem 2.4 Let S be a set of n line segments in the plane. A11 intersection
points in S, with for each intersection point the segments involved in it, can be
reported in O(n1ogn + Ilogn) time and O(n) space, where I is the number of
intersection points.
2.2 The Doubly-Connected Edge List
We have solved the easiest case of the map overlay problem, where the two
maps are networks represented as collections of line segments. In general,
maps have a more complicated structure: they are subdivisions of the plane into
labeled regions. A thematic map of forests in Canada, for instance, would be
Section 2.2
THE DOUBLY-CONNECTED EDG
LIST
- I Chapter 2
/ LINE SEGMENT INTERSECTION
I
1
I
i
I
1 Figure 2.3
/ Typs of forest in Canada
a subdivision of Canada into regions with labels such as "pine", "deciduous",
"birch", and "mixed".
Before we can give an algorithm for computing the overlay of two subdi-
visions, we must develop a suitable representation for a subdivision. Storing a
subdivision as a collection of line segments is not such a good idea. Operations
like reporting the boundary of a region would be rather complicated. It is bet-
ter to incorporate structural, topological information: which segments bound a
given region, which regions are adjacent, and so on.
1
The maps we consider are planar subdivisions induced by planar embeddings
I
of graphs. Such a subdivision is connected if the underlying graph is con-
nected. The embedding of a node of the graph is called a-vertex, and the em-
bedding of an arc is called an edge. We only consider embeddings where every
edge is a straight line segment. In principle, edges in a subdivision need not
be straight. A subdivision need not even be a planar embedding of a graph,
as it may have unbounded edges. In this section, however, we don't consider
such more general subdivisions. We consider an edge to be open, that is', its
endpoints-which are vertices of the subdivision-are not part of it. A face of
the subdivision is a maximal connected subset of the plane that doesn't contain
face
a point on an edge or a vertex. Thus a face is an open polygonal region whose
boundary is formed by edges and vertices from the subdivision. The complex-
ity of a subdivision is defined as the sum of the number of vertices, the number
of edges, and the number of faces it consists of. If a vertex is the endpoint of
an edge, then we say that the vertex and the edge are incident. Similarly, a
face and an edge on its boundary are incident, and a face and a vertex of its
boundary are incident.
1
What should we require from a representation of a subdivision? An oper-
ation one could ask for is to determine the face containing a given point. This
is definitely useful in some applications-indeed, in a later chapter we shall
, 30
design a data structure for this-but it is a bit too much to ask from a basic
representation. The things we can ask for should be more local. For example,
it is reasonable to require that we can walk around the boundary of a given
face, or that we can access one face from an adjacent one if we are given a
common edge. Another operation that could be useful is to visit all the edges
around a given vertex. The representation that we shall discuss supports these
operations. It is called the doubly-connected edge list.
A doubly-connected edge list contains a record for each face, edge, and vertex
of the subdivision. Besides the geometric and topological information-to be
described shortly-each record may also store additional information. For in-
stance, if the subdivision represents a thematic map for vegetation, the doubly-
connected edge list would store in each face record the type of vegetation of
the corresponding region. The additional information is also called attribute
information. The geometric and topological information stored in the doubly-
connected edge list should enable us to perform the basic operations mentioned
earlier. To be able to walk around a face in counterclockwise order we store a
pointer from each edge to the next. It can also come in handy to walk around
a face the other way, so we also store a pointer to the previous edge. An edge
usually bounds two faces, so we need two pairs of pointers for it. It is conve-
nient to view the different sides of an edge as two distinct half-edges, so that
we have a unique next half-edge and previous half-edge for every half-edge.
This also means that a half-edge bounds only one face. The two half-edges we
get for a given edge are called twins. Defining the next half-edge of a given
half-edge with respect to a counterclockwise traversal of a face induces an ori-
entation on each half-edge: it is oriented such that the face that it bounds lies to
its left for an observer walking along the edge. Because half-edges are oriented
we can speak of the origin and the destination of a half-edge. If a half-edge e'
has v as its origin and w as its destination, then its twin Twin(e') has w as its
origin and v as its destination. To reach the boundary of a face we just need to
store one pointer in the face record to an arbitrary half-edge bounding the face.
Starting from that half-edge, we can step from each half-edge to the next and
walk around the face.
What we just said does not quite hold for the boundaries of holes in a face:
if they are traversed in counterclockwise order then the face lies to the right.
It will be convenient to orient half-edges such that their face always lies to the
same side, so we change the direction of traversal for the boundary of a hole to
clockwise. Now a face always lies to the left of any half-edge on its boundary.
Another consequence is that twin half-edges always have opposite orientations.
The presence of holes in a face also means that one pointer from the face to an
arbitrary half-edge on its boundary is not enough to visit the whole boundary:
we need a pointer to a half-edge in every boundary component. If a face has
isolated vertices that don't have any incident edge, we can store pointers to
them as well. For simplicity we'll ignore this case.
Let's summarize. The doubly-connected edge list consists of three collections
of records: one for the vertices, one for the faces, and one for the half-edges.
These records store the following geometric and topological information:
0
Section 2.2
THE DOUBLY-CONNECTED EDGE
LIST
Chapter 2 @ The vertex record of a vertex v stores the coordinates ofoin a field called
LINE SEGMENT INTERSECTION Coordinates(v). It also stores a to an arbitrary
half-edge that has v as its origin.
@ The face record of a face f stores a pointer 0- to some
half-edge on its outer boundary. For the unbounded face this pointer is nil.
Origin(Z) It also stores a list InnerComponents(f), which contains for each hole in
\
Twin(Z) 1
the face a pointer to some half-edge on-the boundary of the hole.
@ The half-edge record of a half-edge Z stores a pointer Origin(Z) to its ori-
gin, a pointer Twin(Z) to its twin half-edge, and a pointer IncidentFace(.?)
to the face that it bounds. We don't need to store the destination of an
edge, because it is equal to Origin(Twin(.?)). The origin is chosen such
that IncidentFace(Z) lies to the left of Z when it is traversed from origin to
destination. The half-edge record also stores pointers Next(.?) and Prev(e')
to the next and previous edge on the boundary of IncidentFace(.?). Thus
Next(.?) is the unique half-edge on the boundary of IncidentFace(Z) that
has the destination of 2 as its origin, and Prev(Z) is the unique half-edge on
ZncidentFace(i?)
the boundary of IncidentFace(Z) that has Origin(?) as its destination.
A constant amount of information is used for each vertex and edge. A face may
require more storage, since the list InnerComponents( f) has as many elements
as there are holes in the face. Because any half-edge is pointed to at most once
from all InnerComponents(f) lists together, we conclude that the amount of
storage is linear in the complexity of the subdivision. An example of a doubly-
connected edge list for a simple subdivision is given below. The two half-edges
corresponding to an edge ei are labeled e'i,l and Gj2.
0 1 Face 1 OuterComponent ( Innercomponents
JI , I Zl,l r;,q
I f? I ZA 1 nil
a
l fi l nil I
0 I Half-edge I Origin I Twin I IncidentFace I Next I Prev 1
The information stored in the doubly-connected edge list is enough to per- Section 2.3 I
form the basic operations. For example, we can walk around the outer bound-
COMPUTING THE OVERLAY OF T 11
ary of a given face f by following Next(.?) pointers, starting from the half-edge SUBDIVISIONS
I
OuterComponent(f). We can also visit all edges incident to a vertex v. It is a
good exercise to figure out for yourself how to do this.
We described a fairly general version of the doubly-connected edge list. In
i
i
applications where the vertices carry no attribute information we could store
their coordinates directly in the Origin() field of the edge; there is no strict
need for a separate type of vertex record. Even more important is to realize that
I
in many applications the faces of the subdivision carry no interesting meaning
i
I
(think of the network of rivers or roads that we looked at before). If that is the
i
case, we can completely forget about the face records, and the IncidentFaceO
field of half-edges. As we will see, the algorithm of the next section doesn't
need these fields (and is actually simpler to implement if we don't need to
1
update them). Some implementations of doubly-connected edge lists may also
i
insist that the graph formed by the vertices and edges of the subdivision be
connected. This can always be achieved by introducing dummy edges, and
has two advantages. Firstly, a simple graph transversal can be used to visit all
half-edges, and secondly, the ZnnerComponents() list for faces is not necessary.
IncidentEdge
e'l 1
Vertex
VI
2.3 Computing-the Overlay of Two Subdivisions
Coordinates
(0.4)
Now that we have designed a good representation of a subdivision, we can
tackle the general map overlay problem. We define the overlay of two subdi-
visions Sl and & to be the subdivision O(Sl ,S2) such that there is a face f in
O(Sl, 52) if and only if there are faces fl in Sl and f2 in S2 such that f is a
maximal connected subset of fi n f2. This sounds more complicated than it
is: what it means is that the overlay is the subdivision of the plane induced by
the edges from Sl and &. Figure 2.4 illustrates this. The general map over-
lay problem is to compute a doubly-connected edge list for O(S1 ,S2), given
the doubly-connected edge lists of Sl and S2. We require that each face in
O(Sl ,S2) be labeled with the labels of the faces in Sl and S2 that contain it.
This way we have access to the attribute information stored for these faces. In
Figure 2.4
Overlaying two subdivisions
Chapter 2
an overlay of a vegetation map and a precipitation map this would mean that
I LINE SEGMENT INTERSECTION we know for each region in the overlay the type of vegetation and the amount
of precipitation.
Let's first see how much information from the doubly-connected edge lists
for S1 and S2 we can re-use in the doubly-connected edge list for O(SI, S2).
Consider the network of edges and vertices of S1. This network is cut into
pieces by the edges of S2. These pieces are for a large part re-usable; only
the edges that have been cut by the edges of S2 should be renewed. But does
this also hold for the half-edge records in the doubly-connected edge list that
correspond to the pieces? If the orientation of a half-edge would change, we
would still have to change the information in these records. Fortunately, this is
not the case. The half-edges are oriented such that the face that they bound lies
to the left; the shape of the face may change in the overlay, but it will remain
to the same side of the half-edge. Hence, we can re-use half-edge records
corresponding to edges that are not intersected by edges from the other map.
Stated differently, the only half-edge records in the doubly-connected edge list
for O(S1, S2) that we cannot borrow from Sl or S2 are the ones that are incident
to an intersection between edges from different maps.
This suggest the following approach. First, copy the doubly-connected
edge lists of S1 and S2 into one new doubly-connected edge list. The new
doubly-connected edge list is not a valid doubly-connected edge list, of course,
in the sense that it does not yet represent a planar subdivision. This is the task
of the overlay algorithm: it must transform the doubly-connected edge list into
a valid doubly-connected edge list for O(Sl , A) by computing the intersections
between the two networks of edges, and linking together the appropriate parts
of the two doubly-connected edge list