Map overlay

Introduction

The purpose of this chapter is to show how to store data on a computer that allows
us to draw maps and work with them, and how to create new data describing the
overlapping of two maps from the data describing these two maps. What is a map
overlay is shown in the following figure, where we have two maps, red and blue, and
their overlay, which is black.

Figure 3.1
The overlay of the red map and the blue map creates the black map.
Description of maps - planar subdivisions
The map will be a planar subdivision consisting of a finite number of distinguished
points, line segments which connect these points and do not intersect in the inner
points, and connected areas that are bounded by these segments. The plane
subdivisions will be described by means of the so-called double-connected edge lists.

Such a list consists of three tables that describe the vertices, edges, and faces.
Given a planar subdivision vertices are its significant points. Edges are line segments
of the planar subdivision together with an orientation. The vertex from which the
edge emerges is called the origin. To every edge there is an edge defined by the
same line segment but with the opposite orientation. We call it the twin of a given
edge. The third term in the description of planar subdivisions is the face. It is a
connected area bounded by line segments. The face lying to the left of a given edge
(what is left and what is right is determined by the edge orientation) is
called adjacent to the edge. This term allows us to define for a given edge e𝑒 its
successor next(e)next⁡(𝑒) and its predecessor prev(e)prev⁡(𝑒). The next edge
comes from the end of the edge e𝑒, has the same adjacent face as e𝑒, and there
are no other edges with these properties between it and the edge e𝑒. The previous
edge is the edge that ends at the origin of the edge e𝑒, it also has the same
adjacent region, and there are no other edges with the previous two properties
between it and the edge e𝑒. All these concepts are demonstrated in the following
pictures.
The edge e1𝑒1 emerges from the vertex v1𝑣1, the edge e2𝑒2 is the twin of the
Figure 3.2

edge e1𝑒1, the face f1𝑓1 is adjacent to the edges e1𝑒1, e3𝑒3 and e6𝑒6. The next
edge to the edge e1𝑒1 is e3𝑒3, not e6𝑒6. The previous edge to e2𝑒2 is e7𝑒7.

Another term we will use is the notion of a cycle. It is the sequence of edges e1,e2,
…,en,en+1𝑒1,𝑒2,…,𝑒𝑛,𝑒𝑛+1 such that ei+1𝑒𝑖+1 is
of ei𝑒𝑖 and en+1=e1𝑒𝑛+1=𝑒1. Each limited face is bounded by an outer
the successor

boundary, which may be described as a cycle of edges that have a given face as
adjacent. We talk about the outer cycle. Some faces are also bounded by one or
more cycles from inside. We take the orientation of the edges so that the face is
adjacent to them. We call these cycles as inner.
The sequence of the edges e1,e2,e3,e4,e5,e6,e7𝑒1,𝑒2,𝑒3,𝑒4,𝑒5,𝑒6,𝑒7 is an outer
Figure 3.3

sequence e8,e9,e10𝑒8,𝑒9,𝑒10 and e11,e12,e13,e14𝑒11,𝑒12,𝑒13,𝑒14 are

cycle of the face f𝑓, the
inner
cycles of f𝑓.

Now we can describe the double-connected edge list tables in more detail.

Vertices. In the table there is one row for each vertex. This row contains the name
of the vertex, its coordinates, and the pointer to an edge coming from the vertex.
Edges. The row in the edge table shows the name of the edge, a pointer to its origin
(the point at which it begins), a pointer to its twin, a pointer to the adjacent area, a
pointer to the next edge, and a pointer to the previous edge.
Faces. The row in the face table contains the name of the face, a pointer to one
edge from the outer boundary cycle (if an outer boundary exists), a pointer to one
edge of each internal boundary cycle (if an internal boundary exists).

An example of a simple planar subdivision and its description using a double-

connected edge list can be found in Figure 3.4 and in Table 3.1.
 Figure 3.4
An example of a simple (although a bit atypical) planar subdivision.

v1𝑣1 e1,1𝑒1,1
Vertex Coordinates Edge coming from the vertex

v2𝑣2 e4,2𝑒4,2
(0,4)(0,4)

v3𝑣3 e3,1𝑒3,1
(2,4)(2,4)

v4𝑣4 e2,2𝑒2,2
(2,2)(2,2)
(1,1)(1,1)

e1,1𝑒1,1 v1𝑣1 e1,2𝑒1,2 e4,2𝑒4,2 e3,1𝑒3,1 f1𝑓1

Edge Origin Twin Next Prev Adjacent face

e1,2𝑒1,2 v2𝑣2 e1,1𝑒1,1 e3,2𝑒3,2 e4,1𝑒4,1 f2𝑓2

e2,1𝑒2,1 v3𝑣3 e2,2𝑒2,2 e2,2𝑒2,2 e4,2𝑒4,2 f1𝑓1
e2,2𝑒2,2 v4𝑣4 e2,1𝑒2,1 e3,1𝑒3,1 e2,1𝑒2,1 f1𝑓1
e3,1𝑒3,1 v3𝑣3 e3,2𝑒3,2 e1,1𝑒1,1 e2,2𝑒2,2 f1𝑓1
e3,2𝑒3,2 v1𝑣1 e3,1𝑒3,1 e4,1𝑒4,1 e1,2𝑒1,2 f2𝑓2
e4,1𝑒4,1 v3𝑣3 e4,2𝑒4,2 e1,2𝑒1,2 e3,2𝑒3,2 f2𝑓2
e4,2𝑒4,2 v2𝑣2 e4,1𝑒4,1 e2,1𝑒2,1 e1,1𝑒1,1 f1𝑓1

f1𝑓1 e3,1𝑒3,1
Face Outer cycle Inner cycles

f2𝑓2 e1,2𝑒1,2
-
-
Table 3.1
Doubly connected edge list for the subdivision from Figure 3.4
The description using a double-connected edge list can be understood as a minimal
description of a planar subdivision, from which we can algorithmically obtain all other
data in time O(n)𝑂(𝑛), where n𝑛 is the amount of data required. For example, if we
want to find all the edges of the outer cycle of a face f𝑓, we take the edge of the
outer cycle given in the row for f𝑓 in the face table, find the successor, find the
successor to the successor, and do so until we reach the original edge. Because we
use pointers, the successor search can be considered as a step of running
time O(1)𝑂(1), so the running time for finding all the edges of the outer cycle
equals to O(n)𝑂(𝑛), where n𝑛 is the number of edges in this cycle . In a similar way
one can solve the following tasks as simple exercises:
 Find all the edges coming out of a given vertex v𝑣 and list them in the
anticlockwise direction.
 Find all the faces that are adjacent to a given vertex v𝑣 and list them in
the anticlockwise direction. (Beware, some faces may repeat.)

Algorithm for map overlay

We are given two planar subdivisions S1𝑆1 and S2𝑆2, described by the double-
connected edge lists D(S1)𝐷(𝑆1) and D(S2)𝐷(𝑆2). The goal of our algorithm is to
create a double-connected edge list D𝐷 for the overlay O(S1,S2)𝑂(𝑆1,𝑆2) of
maps S1𝑆1 and S2𝑆2. In addition, for each new face f𝑓 in the map overlay, we
want to find original faces in S1𝑆1 and S2𝑆2 in which f𝑓 lies.

For simplicity, we will talk about the planar subdivision S1𝑆1 as about a red map
and about the subdivision S2𝑆2 as about a blue map. This will correspond to our
pictures. The algorithm starts by creating a new list D𝐷 by joining the tables for
vertices and edges of double-connected edge lists of both maps. Editing the
list D𝐷 into a double-connected edge list of the resulting overlay has two steps. In
the first one, we add and modify records in D𝐷 for vertices and edges to match the
overlay. In the second part, we create a table for faces.

Vertices and edges

The procedure for creating tables of vertices and edges of the overlay is based on
the sweep algorithm which finds the intersections of line segments and was
described in detail in the previous chapter. However, this is a relatively laborious
modification, so in this chapter we will only describe the algorithm verbally and
demonstrate it in the examples. Pseudocode description would be too long. Readers
are referred to pseudocodes 4 - 10 in the diploma thesis of Dominik Janků

https://is.muni.cz/auth/th/359588/fi_m/diplomka.pdf

We start by creating a list of line segments specified by the red and blue edges and
the list of their endpoints. For the sake of simplicity, let's assume that the
intersection of a red segment and a blue segment is either a point or an empty set or
the two lines are identical. In the latter case, we consider both segment to be the
only segment that is the wearer of both colours. We
assign L(p)𝐿(𝑝) and U(p)𝑈(𝑝) to each vertex p𝑝 with the same meaning as in the
previous chapter, while we remember the colours of segments. We activate the
event queue Q𝑄 to include all vertices, and a binary balanced tree that will be blank
at the beginning. Just as in the previous chapter, we start the sweep line method.
We describe the algorithm when passing an event p𝑝. If the set C(p)𝐶(𝑝) of
segments, for which p𝑝 is an inner point, is empty, and the union
of L(p)∪U(p)𝐿(𝑝)∪𝑈(𝑝) contains only segments of one colour, we do not execute
any changes in the list D𝐷. If C(p)𝐶(𝑝) is not empty (i.e. it contains at least one
red and one blue segment), each segment of C(p)𝐶(𝑝) is divided into two
segments with the end point p𝑝 and these new segments are put
into L(p)𝐿(𝑝) or U(p)𝑈(𝑝). We assign edges to these segments - to those that end
in p𝑝 we assign the original edges, to those starting at p𝑝 we assign a new edge,
see the following picture.
Figure 3.5
Original and new notation of segments and edges.

We now make these changes in the list D𝐷. In the table for vertices we add a row
for the vertex p𝑝, in the table for edges we modify the rows for the original edges
corresponding to the segments containing the vertex p𝑝, and we add rows for the
new edges. To determine the new successors and predecessors of these edges, we
first arrange the segments from L(p)𝐿(𝑝) (using the binary tree for the position of
the sweep line over the event p𝑝) and then we arrange the segments
from U(p)𝑈(𝑝) (using the binary tree in the sweep line position under the
event p𝑝). This will give the segments of L(p)𝐿(𝑝) and U(p)𝑈(𝑝) around the
vertex p𝑝 an arrangement in the clockwise direction. Concrete implementation of

The order of segments from L(p)𝐿(𝑝) is su<s′u𝑠𝑢<𝑠𝑢′. The order of segments

this idea is shown in the example from Figure 3.5

from U(p)𝑈(𝑝) is s′l<sl𝑠𝑙′<𝑠𝑙. This gives the order of the segments around the
vertex p𝑝 in the clockwise direction: su,s′u,sl,s′l𝑠𝑢,𝑠𝑢′,𝑠𝑙,𝑠𝑙′. From this order we

edge e1𝑒1 is e8𝑒8 and the predecessor of e5𝑒5 is e3𝑒3. The new row for the
deduce successors and predecessors, for example the successor of the
 vertex p𝑝, the modified row for the edge e1𝑒1, and the new row for e5𝑒5 will look
like this:

e5𝑒5
Vertex Coordinates Edge coming from the vertex
p𝑝 (1,2)(1,2)
Tabulka 3.2

e1𝑒1 v1𝑣1 e5𝑒5 e8𝑒8

Edge Origin Twin Next Prev Adjacent face

e5𝑒5 p𝑝 e1𝑒1 the same as for e2𝑒2 e3𝑒3 the same as for e2𝑒2
we leave the original we leave the original

Tabulka 3.3

(see the row for e1𝑒1 in the previous table) or refers to the original map according
In the table for edges the item regarding the adjacent face is either left unchanged

to the colour of the edge (see the row for e5𝑒5). This procedure gives us complete
information about the relationship between vertices and edges of the overlay in the
list D𝐷.

Faces
Each limited face of the overlay is determined by its outer boundary represented by
an outer cycle. Therefore, to identify the overlay faces, we need to find all the cycles
and to identify those that are outer ones.

To determine cycles, information about successors that are already captured in the
list D𝐷 is sufficient. We take an edge e𝑒, find its successor, another successor, and
so on until we get back to the edge e𝑒. Then we take an edge that is not run in this
cycle. By the same procedure, we will get another cycle. This is how we get all the
cycles.
Now we will show how to distinguish outer and inner cycles. In a given cycle, we take
the vertex v𝑣, which is leftmost (the smallest in the lexicographic arrangement from
the previous chapter). Let the edge e1𝑒1 come into the vertex v𝑣 and let the
edge e2𝑒2 come out of v𝑣. If the angle from e1𝑒1 to e2𝑒2 measured over the
adjacent area is less than 180o180𝑜, it is an outer cycle. If this angle is greater
than 180o180𝑜, the cycle is inner.
The cycle c1𝑐1 with the angle α<180o𝛼<180𝑜 is outer, the cycle c2𝑐2 with the
Figure 3.6

angle β>180o𝛽>180𝑜 is inner.

Computationally, we decide on this by the sign of the determinant

det(e1x e1ye2x e2y),det(𝑒1𝑥 𝑒1𝑦𝑒2𝑥 𝑒2𝑦),

where we take e1𝑒1 and e2𝑒2 as vectors with coordinates (eix,eiy)(𝑒𝑖𝑥,𝑒𝑖𝑦). If
the sign of the determinant is positive, the cycle is outer, if negative, the cycle is
inner.

introduce a fictional cycle c∞𝑐∞ as the outer cycle of this face. Now every outer
So we know all outer and inner cycles for the overlap. For an unrestricted face, let's

cycle defines just one face. To assign internal cycles to faces, we construct the
following graph G𝐺. It is a graph in the sense of the theory of graphs, whose

We take an inner cycle c1𝑐1. Let p𝑝 be its most left vertex. Let s𝑠 be the segment
vertexes are all cycles. We create the edges of this graph as follows:

closest to the left of p𝑝 (The information on the nearest left segment is found out in
the first step of the algorithm for each event when using the sweep line). The
segment s𝑠 determines an edge e𝑒 with the same adjacent face as the internal
cycle c1𝑐1 has. This edge further determines a cycle c2𝑐2, which can be inner or
outer. If there is no segment to the left of p𝑝, we take the fictional outer
cycle c∞𝑐∞ as the cycle c2𝑐2. We join the cycles c1𝑐1 and c2𝑐2 by an edge in the
graph G𝐺.
In the graph G𝐺 the inner cycle c1𝑐1 is connected by an edge with the inner
Figure 3.7

cycle c2𝑐2 and this is connected by an edge with the outer cycle c3𝑐3.

In the graph G𝐺 we determine the components of connectivity. There is just one

outer cycle in each component, which determines one face of the overlay. Therefore,
there is a clear correspondence between the components of the graph and the faces.
The inner cycles in a given component of the graph are the inner cycles of the
corresponding face. With knowledge of the outer cycle and all inner cycles of each
region, we can now fill in the table for faces in the list D𝐷. Further, to each edge we
find the cycle in which it lies, and to this cycle we look out its face. This is the
adjacent face to this edge. This completes the last item in the edge table.
Figure 3.8

components of connectivity correspond to the faces f1𝑓1, f2𝑓2, f4𝑓4, f5𝑓5, f∞𝑓∞,
The cycles in a planar subdivision and the graph G𝐺 which they determine. The

respectively.

Identification of original faces

We still have to find for each face f𝑓 of the overlay a face f1𝑓1 of the red map and a
face f2𝑓2 of the blue map in which f𝑓 lies. There are two possibilities. If there are
edges of both colours in the boundary cycles of the face f𝑓, then the adjacent face
to a red edge is f1𝑓1, and the adjacent face to a blue edge is f2𝑓2.
Specification of the original faces f1𝑓1 and f2𝑓2 for the face f𝑓 of the overlay.
Figure 3.9

If all boundary cycles of the face f𝑓 are single colour, let us say red, we
determine f1𝑓1 as in the previous case. If f𝑓 is unlimited, f2𝑓2 is the unlimited face
in the blue map. For the bounded face f𝑓, we specify the face f2𝑓2 as follows: Take
the most left vertex of the outer cycle of the face f𝑓. We find the closest segment to
the left of this vertex. This segment determines the inner or outer cycle of a face f′𝑓
′ which is adjacent to f𝑓. If at least one edge of the cycles of the face f′𝑓′ is blue, we
specify f2𝑓2 as the face adjacent to this edge in the blue map. If f′𝑓′ is unlimited,
the face f2𝑓2 is the unlimited face in the blue map. If f′𝑓′ is bounded and if all edges
of its cycles are red, let us proceed with the same procedure, only f𝑓 is now
replaced f′𝑓′. The appropriate blue face for f′𝑓′ is f2𝑓2 for the original face f𝑓.

Určení původních oblastí f1𝑓1 a f2𝑓2 pro novou oblast f𝑓.

Figure 3.10

Intersections and unions of polygons

The previous map overlay algorithm can be used to find the intersection, the union,
or the difference of two generally non-convex polygons. A simply connected polygon
is such a polygon that is connected and does not have "holes" in its interior, i.e. each
closed curve can be shrunk continuously without breaking into a point inside the
polygon. A simply connected polygon thus determines a planar subdivision with two
faces, internal and external. The intersection of two polygons consists of those faces
of the overlay of their planar subdivisions, which lie in the internal faces of both
subdivisions. Likewise, the union of polygons is made up of all faces of the overlay
which are bounded. See the following pictures.

The intersection of the red and blue polygons is the union of the faces f2𝑓2 a f4𝑓4.
Figure 3.11

The union of polygons is described as the union of the faces f0𝑓0 to f10𝑓10.

Pseudocodes of the algorithm, its

implementation and running time
The algorithm can be briefly summarized as follows:

Algorithm MAPOVERLAY(S1,S2𝑆1,𝑆2)
Input. Two planar subdivisions S1𝑆1 and S2𝑆2 stored in doubly-connected edge

Output. The overlay of S1𝑆1 and S2𝑆2 stored in doubly-connected edge list D𝐷.
lists.

1. Copy the doubly-connected edge lists for S1𝑆1 and S2𝑆2 to a new
doubly-connected edge list D𝐷
 2. Compute all intersections between edges from S1𝑆1 and S2𝑆2 with the
plane sweep algorithm of Section 2.1. In addition to the actions
on T𝑇 and Q𝑄 required at the event points, do the following:

both S1𝑆1 and S2𝑆2. (This was explained for the case where an edge
o Update D𝐷 as explained above if the event involves edges of

of S1𝑆1 passes through a vertex of S2𝑆2)

o Store the edge immediately to the left of the event point at the vertex
in D𝐷 representing it.
3. (* Now D𝐷 is the doubly-connected edge list for O(S1,S2)𝑂(𝑆1,𝑆2),
except that the information about the faces has not been computed yet.
*)
4. Determine the boundary cycles in O(S1,S2)𝑂(𝑆1,𝑆2) by
traversing D𝐷.
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
determine the arcs of G𝐺 has been computed in line 2, second item.)
6. for each connected component in G𝐺
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 edge of C𝐶, and construct
the list InnerComponents(f𝑓) consisting of pointers to one edge in
each hole cycle in the component. Let the InnerFace() pointers of all
edges in the cycles point to the face record of f𝑓.

of S1𝑆1 and S2𝑆2 containing it, as explained above.

8. Label each face of O(S1,S2)𝑂(𝑆1,𝑆2) with the names of the faces

Detailed pseudocodes can be found in the diploma thesis Map Overlay written by
Dominik Janků (in Czech)

https://is.muni.cz/auth/th/359588/fi_m/diplomka.pdf

Lines 1 a 2 of the given pseudocode are realized by Pseudocodes 4 to 10 of the

diploma thesis. The search of cycles in line 4 is described by Pseudocode 13, inner
and outer cycles are found using Pseudocodes 11 and 12. Components of
connectivity of the graph G𝐺 in line 5 are constructed using Pseudocode 14, lines 6
and 7 of our pseudocode are in detail described by Pseudocode 16 and line 8 by
Pseudocode 15.
A part of the diploma thesis is also an implementation of the algorithm. Its
description is in the last chapter of the thesis, the necessary files are compressed in
the cdrom.zip file.

https://is.muni.cz/auth/th/359588/fi_m/

The complexity of the algorithm is characterized by the following theorem, which we

give without proof.

Let S1𝑆1 be a planar subdivision of complexity n1𝑛1 and let S2𝑆2 be a planar
Theorem 3.1

subdivision of complexity n2𝑛2. Let n=n1+n2𝑛=𝑛1+𝑛2. Then the running time of

subdivisions isO((n+k)logn)𝑂((𝑛+𝑘)log⁡𝑛)where k𝑘 is the complexity of the

the algorithm that builds a double-connected edge list for the overlay of these

overlay.

doc. RNDr. Martin Čadek, CSc.

Ústav matematiky a statistiky – Přírodovědecká fakulta Masarykovy univerzity Masarykovy
univerzity
Technical cooperation:
Service Center for E-learning, Faculty of Informatics, Masaryk University, 2018

© 2018 Masaryk University Statement of Accessibility