Figure 19: Planar straight line subdivision.
Planar subdivisions will form the basic objects of many different
structures that we will discuss later this semester (triangulations
and Voronoi diagrams in particular) so this is a good time to consider
them in greater detail. The first question is how should we represent
such structures so that they are easy to manipulate and reason
about. For example, at a minimum we would like to be able to list the
edges that bound each face of the subdivision in cyclic order, and we
would like to be able to list the edges that surround each vertex.
Planar graphs: There are a number of important facts about planar
graphs that we should discuss. Generally speaking, an (undirected)
graph is just a finite set of vertices, and collection of unordered
pairs of distinct vertices called edges. A graph is planar if it can
be drawn in the plane (the edges need not be straight lines) so that
no two distinct edges cross each other. An embedding of a planar graph
is any such drawing. In fact, in specifying an embedding it is
sufficient just to specify the counterclockwise cyclic list of the
edges that are incident to each vertex. Since we are interested in
geometric graphs, our embeddings will contain complete geometric
information (coordinates of vertices in particular). There is an
important relationship between the number of vertices, edges, and
faces in a planar graph (or more generally an embedding of any graph
on a topological 2 manifold, but we will stick to the plane). Let V
denote the number of vertices, E the number of edgs, F the number of
faces in a connected planar graph.
Euler's formula states that
V - E + F = 2:
If we allow the graph to be disconnected, and let C denote the number
of connected compo nents, then we have the more general formula
V - E + F - C = 1:
In our example above we have V = 13, E = 12, F = 4 and C = 4, which
clearly satisfies this formula. An important fact about planar graphs
follows from this.
Theorem: A planar graph with V vertices has at most 3(V - 2) edges and
at most 2(V - 2) faces.
Proof: We assume (as is typical for graphs) that there are no multiple
edges between the same pair of vertices and no self loop edges. We
begin by triangulating the graph. For each face that is bounded by
more than three edges (or whose boundary is not connected) we
repeatedly insert new edges until every face in the graph is bounded
by exactly three edges. An example is shown in the figure below in
which the original graph edges are shown as solid lines.
Figure 20: Triangulating a planar graph.
Let E' >= E and F' >= F denote the number edges and faces in the
modified graph. The resulting graph has the property that it has one
connected component, every face is bounded by exactly three edges, and
each edge has a different face on either side of it. (The last claim
may involve a little thought.) If we count the number of faces and
multiply by 3, then every edge will be counted exactly twice, once by
the face on either side of the edge. Thus, 3F' = 2E' , that is E' =
3F' =2.
Euler's formula states that V + E' - F' = 2, and hence
V - 3F'/2 + F' = 2, so F <= F' = 2(V - 2);
and using the fact that F' = 2E' / 3 we have
V - E' + 2E'/3 = 2, so E <= E' = 3(V - 2):
This completes the proof.
There are a number of reasonable representations that are used in
practice. The most widely used on is the winged edge data
structure. Unfortunately, it is probably also the messiest. There is
another called the quad edge data structure which is quite elegant,
and has the nice property of being self dual. (We will discuss duality
later in the semester.) We discuss a simple and relatively elegant
data structure called a doubly connected edge list (or DCEL).
Doubly connected Edge List: Like most representations for PSLGs, the
DCEL is an edge based representation, but vertex and face information
is also included for whatever geometric application is using the data
structure. There are three sets of records one for each element in the
PSLG: vertex records, a edge records, and face records. For the
purposes of unambiguously defining left and right, each undirected
edge is represented by two directed half edges.
We will make a simplifying assumption that faces do not have holes
inside of them. This assumption can be satisfied by introducing some
number of dummy edges joining each hole either to the outer boundary
of the face, or to some other hole that has been connected to the
outer boundary in this way. With this assumption, it may be assumed
that the edges bounding each face form a single cyclic list.
Vertex: Each vertex stores its coordinates, along with a pointer to
any incident directed edgethat has this vertex as its origin, v.inc
edge.
Edge: Each undirected edge is represented as two directed edges. Each
edge has a pointer to the oppositely directed edge, called its
twin. Each directed edge has an origin and destination vertex. Each
directed edge is associate with two faces, one to its left and one to
its right.
We store a pointer to the origin vertex e.org. (We do not need to
define the destination, e.dest, since it may be defined to be
e.twin.org.) We store a pointer to the face to the left of the edge
e.left (we can access the face to the right from the twin edge). This
is called the incident face. We also store the next and previous
directed edges in counterclockwise order about the incident face,
e.next and e.prev, respectively.
Face: Each face f stores a pointer to a single edge for which this
face is the incident face, f.inc edge. (See the text for the more
general case of dealing with holes.) The figure shows two ways of
visualizing the DCEL. One is in terms of a collection of doubled up
directed edges. An alternative way of viewing the data structure that
gives a better sense of the connectivity structure is based on
covering each edge with a two element block, one for e and the other
for its twin. The next and prev pointers provide links around each
face of the polygon. The next pointers are directed counterclockwise
around each face and the prev pointers are directed clockwise. Of
course, in addition the data structure may be enhanced with whatever
application data is relevant.
In some applications, it is not necessary to know either the face or
vertex information (or both) at all, and if so these records may be
deleted. See the book for a complete example.
Figure 21: Doubly connected edge list.
Merging subdivisions: Let us return to the applications problem that
lead to the segment inter section problem. Suppose that we have two
planar subdivisions, S 1 and S 2 , and we want to compute their
overlay. In particular, this is a subdivision whose vertices are the
union of the vertices of each subdivision and the points of
intersection of the line segments in the subdivision. (Because we
assume that each subdivision is a planar graph, the only new vertices
that could arise will arise from the intersection of two edges, one
from S 1 and the other from S 2 .) Suppose that each subdivision is
represented using a DCEL. Can we adapt the plane sweep algorithm to
generate the DCEL of the overlaid subdivision?
The answer is yes. The algorithm will destroy the original
subdivisions, so it may be desirable to copy them before beginning
this process. The first part of the process is straightforward, but
perhaps a little tedious. This part consists of building the edge and
vertex records for the new subdivision. The second part involves
building the face records. It is more complicated because it is
generally not possible to know the face structure at the moment that
the sweep is advancing, without looking ``into the future'' of the
sweep to see whether regions will merge. (You might try to convince
yourself of this.) The entire subdivision is built first, and then the
face information is constructed and added later. We will skip the part
of updating the face information (see the text).
For the first part, the most illustrative case arises when the sweep
is processing an intersection event. In this case the two segments
arise as two edges a 1 and b 1 from the two subdivisions. We will
assume that we select the half edges that are directed from left to
right across the sweep line. The process is described below (and is
illustrated in the figure below).
It makes use of two auxiliary procedures.
Split(a 1 ; a 2 ) splits an edge a 1 at its midpoint into two
consecutive edges a 1 followed by a 2 , and links a 2 into the
structure.
Splice(a 1 ; a 2 ; b 1 ; b 2 ) takes two such split edges and links
them all together.
Merge two edges into a common subdivision
Merge(a1 ; b1 ) :
(1) Create a new vertex v at the intersection point.
(2) Split each of the two intersecting edges, by adding a vertex at
the common intersection point. Let a2 and b2 be the new edge
pieces. They are created by the calls a2 = Split(a1 ) and b2 =
Split(b1 ) given below.
(3) Link the four edges together by invoking Splice(a1 ; a2 ; b1 ; b2),
given below. The splitting procedure creates the new edge, links
it into place. After this the edges have been split, but they are not
linked to each other. The edge constructor is given the origin and
destination of the new edge and creates a new edge and its twin. The
procedure below initializes all the other fields. Also note that the
destination of a 1 , that is the origin of a 1 's twin must be
updated, which we have omitted. The splice procedure interlinks four
edges around a common vertex in the counterclockwise order a 1
(entering), b 1 (entering), a 2 (leaving), b 2 (leaving).
Split an edge into two edges
Split(edge &a1, edge &a2) -- // a2 is returned
a2 = new edge(v, a1.dest()); // create edge (v,a1.dest)
a2.next = a1.next; a1.next.prev = a2;
a1.next = a2; a2.prev = a1;
a1t = a1.twin; a2t = a2.twin; // the twins
a2t.prev = a1t.prev; a1t.prev.next = a2t;
a1t.prev = a2t; a2t.next = a1t;
Splice four edges together
Splice(edge &a1, edge &a2, edge &b1, edge &b2) --
a1t = a1.twin; a2t = a2.twin; // get the twins
b1t = b1.twin; b2t = b2.twin;
a1.next = b2; b2.prev = a1; // link the edges together
b2t.next = a2; a2.prev = b2t;
a2t.next = b1t; b1t.prev = a2t;
b1.next = a1t; a1t.prev = b1;
Figure 22: Updating the DCEL.
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.