Area-preserving C-oriented schematization

Citation for published version (APA):

Buchin, K., Meulemans, W., & Speckmann, B. (2011). Area-preserving C-oriented schematization. 163-166.
Abstract from 27th European Workshop on Computational Geometry (EuroCG 2011), Morschach, Switzerland.

Document status and date:

Published: 01/01/2011

Document Version:
Publisher’s PDF, also known as Version of Record (includes final page, issue and volume numbers)

Please check the document version of this publication:

• A submitted manuscript is the version of the article upon submission and before peer-review. There can be
important differences between the submitted version and the official published version of record. People
interested in the research are advised to contact the author for the final version of the publication, or visit the
DOI to the publisher's website.
• The final author version and the galley proof are versions of the publication after peer review.
• The final published version features the final layout of the paper including the volume, issue and page
numbers.
Link to publication

General rights
Copyright and moral rights for the publications made accessible in the public portal are retained by the authors and/or other copyright owners
and it is a condition of accessing publications that users recognise and abide by the legal requirements associated with these rights.

• Users may download and print one copy of any publication from the public portal for the purpose of private study or research.
• You may not further distribute the material or use it for any profit-making activity or commercial gain
• You may freely distribute the URL identifying the publication in the public portal.

If the publication is distributed under the terms of Article 25fa of the Dutch Copyright Act, indicated by the “Taverne” license above, please
follow below link for the End User Agreement:
www.tue.nl/taverne

Take down policy

If you believe that this document breaches copyright please contact us at:
openaccess@tue.nl
providing details and we will investigate your claim.

Download date: 23. may. 2021

 EuroCG 2011, Morschach, Switzerland, March 28–30, 2011

Area-Preserving C-Oriented Schematization∗

Kevin Buchin† Wouter Meulemans† Bettina Speckmann†

Abstract

We define an edge-move operation for polygons and

prove that every simple non-convex polygon P has
a non-conflicting pair of complementary edge-moves
that reduces the number of edges of P while pre-
serving its area. We use this result to generate area-
preserving C-oriented schematizations of polygons.

1 Introduction

A schematic map displays a set of nodes and their

connections—for example, highway, train, or metro
networks—in a highly simplified form to communicate Figure 2: Hexagonal Great Britain using 50 edges;
the connectivity information as effectively as possible. octagonal Vietnam using 15 edges.
Connections are usually drawn as polygonal paths us-
ing few links and few orientations. The set of permis- Results. We introduce an edge-move operation that
sible orientations often contains only the two axis- moves an edge of a polygon inward or outward with-
parallel or the four main orientations. The most gen- out changing its orientation. This does change the
eral setting is C-oriented schematization where every length of its adjacent edges and potentially itself. A
link has to use one of a set C of specified orientations. contraction is an edge-move that reduces at least one
A substantial part of previous efforts concentrates edge to length zero, hereby reducing the number of
on the schematization of networks, but it is also often edges in the polygon. Since we desire area preserva-
desirable to schematize the boundaries of regions or tion, we apply this operation in non-conflicting com-
even complete subdivisions. Whenever exact bound- plementary pairs (Figure 1). Theorem 1, our main
aries are not needed it is preferable to replace them result, is an immediate consequence of Lemma 6:
by schematic ones, to reduce visual clutter and to in-
dicate that the map is not a topographic map. Theorem 1 Every simple non-convex polygon has
The schematized output should visually resemble a non-conflicting pair of complementary edge-moves,
the input. But it is not clear how to quantify what one of which is a contraction.
the most recognizable schematization of a given input
is. Optimization based on standard distance metrics As edge-moves do not introduce new orientations, we
can produce undesirable output for certain input poly- can also use edge-moves to create area-preserving C-
gons [8]. Hence we focus on area-preserving schema- oriented schematizations of polygons. Note that a
tization, that is, the area of the input polygon and its simple polygon can be converted into a simple C-
schematization are equivalent. While we do not prove oriented polygon of equal area based on the method
any guarantees on the resulting shapes, experimental presented by Meulemans et al. [8].
results are quite promising and visually pleasing.
Corollary 2 Given a simple C-oriented polygon P
and an integer k with 2|C| ≤ k, an area-preserving
C-oriented schematization of P with at most k edges
can be generated using only non-conflicting pairs of
complementary edge-moves.
Figure 1: Complementary edge-moves.
The results in Figure 2 were obtained by repeat-
∗ W.Meulemans and B. Speckmann are supported by the edly executing a non-conflicting pair of complemen-
Netherlands Organisation for Scientific Research (NWO) under tary edge-moves such that the contraction minimizes
project no. 639.022.707.
† Department of Mathematics and Computer Science, the area change and the compensating edge-move is as
TU Eindhoven, The Netherlands. k.a.buchin@tue.nl, close by as possible. This method can also be used for
w.meulemans@tue.nl, and speckman@win.tue.nl. simple subdivisions restricted to edge-moves that do

163
27th European Workshop on Computational Geometry, 2011

not change the topology. Our algorithm then ensures

that each face preserves its area and that adjacencies
are correct. In this case we cannot give any guarantees
on the reduction in the number of edges. Preliminary Figure 3: A positive and negative exterior angle.
experiments suggest that the reduction is significant.

Related work. There is an ample body of work on s1 and sm are the outer edges of S, the other edges
map schematization and metro map construction, see are its inner edges. Likewise, u1 and um+1 are outer
the surveys by Swan et al. [10] and Wolff [11] for an vertices, the other vertices inner vertices. By α(S),
overview. Of particular interest is the work by Mer- we denote the sum of the exterior angles of the inner
rick and Gudmundsson [7] who describe an algorithm vertices of S. A lid is an open line segment between a
to generate C-oriented metro map layouts. Methods point on s1 and a point on sm and is fully contained
for map schematization can be used to schematize in the interior of P . If S has any lid, it is a closable
subdivisions, but they usually do not take criteria chain. If the open line segment (u1 , um+1 ) is a lid,
such as shape and size preservation into account. S is a proper chain. For a closable chain S and a lid
The generalization of urban data, specifically build- l, we denote by Rl (S) the region enclosed by S and
ing generalization, is closely related to our work. In l. For a proper chain, R(S) denotes this region us-
particular, algorithms for building wall squaring [6] ing the lid (u1 , um+1 ) implicitly. Due to the lid, we
and outline simplification [5] can be used for polygon know that for every closable chain, any point on the
schematization and vice versa. boundary of P that is inside Rl (S) must be part of S.
Line simplification has been a prominent topic in For any closable chain, α(S) > 0 holds. A (not neces-
the GIS literature for many years. Of particular rele- sarily closable) chain with exactly 3 edges is called a
vance are the work of Delling et al. [3] and Neyer [9] configuration G, its edges denoted by g1 , g2 , and g3 .
dealing with C-oriented schematization of routes or The outer edges of a configuration G define two
lines and the work of Bose et al. [1] on area-preserving tracks, infinite lines through the edges. An edge-move
line simplification. However, it is generally not advis- on G moves g2 such that its orientation is preserved
able to schematize each chain in a subdivision sepa- and its vertices are on the tracks, making the outer
rately. There are some approaches, developed in com- edges longer or shorter. An edge-move is valid if at
putational geometry, that preserve the topology of the least one of its vertices remains on its original outer
input subdivision. For example, De Berg et al. [2] de- edge and g2 remains on the same side of or on the
scribe a method that simplifies a polygonal subdivi- intersection point of the tracks (if any). An edge-move
sion without introducing intersections or passing over which causes one of the edges of G to reach length
special input points. Unfortunately many subdivision zero, is a contraction. Contractions are extremal edge-
simplification problems that minimize the number of moves. An edge-move is positive if it adds area to P
edges in the output are NP-complete [4]. and negative if it removes area.
A configuration supports edge-moves, either posi-
tive, negative or both. Let g2+ denote the extremal
2 Edge-moves and configurations position of g2 after any valid positive edge-move, i.e.
the position after a positive contraction. The positive
Definitions and notation. We are given a simple poly-
contraction region of a positive configuration, R+ (G),
gon P with vertices v1 , . . . , vn . We treat the vertices
is the region enclosed by g2 , g2+ , and the tracks. A fea-
modulo n, e.g. vn+1 = v1 . The edges are denoted
sible positive configuration is a configuration for which
by e1 , . . . , en , again treated circularly. The directed
R+ (G) is empty except for G. Similarly, we define the
edge ei starts at vertex vi and ends at vertex vi+1 . A
negative contraction region R− (G) and a feasible neg-
vertex is called convex if the angle inside the polygon
ative configuration. If a positive or negative configu-
between its two adjacent edges is at most π, and it
ration is feasible, then any valid positive or negative
is called reflex otherwise. We call an edge convex or
edge-move respectively is feasible. If a positive config-
reflex if both its vertices are convex or reflex respec-
uration is infeasible, then there is some point on δP in
tively. The exterior angle of a vertex is defined as
R+ (G)\G. A point in δP ∩R+ (G)\G that is closest to
the angle between one edge and the extension of the
other. The exterior angle is sometimes also referred
to as turning angle. The angle is negative if and only
if the vertex is reflex. The sum of all exterior angles
R−
of a simple polygon is always equal to 2π. R+
We define a chain S as a set of at least three consec-
utive edges of P . Its edges are denoted by s1 , . . . , sm
with m ≤ n. Its vertices are denoted by u1 , . . . , um+1
and edge si is directed from ui to ui+1 . The edges Figure 4: A valid positive edge-move.

164
 EuroCG 2011, Morschach, Switzerland, March 28–30, 2011

configuration. Examples 1, 3 and 5 in Figure 6 show

p p
p closable chains, the other examples do not.
G For induction, assume that this lemma holds for
G G
any closable chain with less than m edges and with
Figure 5: Configurations G and blocking points p. a reflex first inner vertex. Let G� = si−1 si si+1 be
the first configuration with α(G� ) > 0 where ui is
reflex. If G� is feasible, we are done. If G� is not fea-
the line through g2 is called a positive blocking point. sible, let p denote the corresponding blocking point.
Analogously, G can have a negative blocking point. If Note that p must be part of S as R− (G� ) ⊆ Rl (S) for
the inner edge of an infeasible G is convex or reflex, any lid l. Moreover, p must come after si+1 on S as
there is always a blocking point that is a vertex of P . otherwise G� cannot be the first. The closable chain
Since we desire an approach that preserves the area S � = si+1 , . . . , p (that is, until the edge containing p if
of the polygon, we combine two complementary fea- p is not a vertex) has less edges than S and thus has
sible configurations, one positive and one negative, a feasible negative configuration by induction. �
executing an edge-move on both simultaneously. The
one with the smaller contraction region is contracted, Lemma 4 If a proper chain S has a convex inner
while the other is moved just far enough to compen- edge, then S has a feasible negative configuration G
sate for the area change. Two configurations conflict with R− (G) ⊆ R(S) and α(G) > 0. Also, g2 is convex
when they share an edge, unless they share only outer or starts at a reflex vertex or g2 �= sm−1 .
edges and one of these has a convex and a reflex ver-
tex. In this special case the two edge-moves both ei- Proof. We prove this lemma by induction on m. If
ther shorten or lengthen the shared edge. We call two m = 3, S is a feasible negative configuration, since S is
non-conflicting complementary feasible configurations a proper chain and s2 is a convex edge. For induction,
a proper configuration pair. assume that this lemma holds for any suitable chain
with less than m edges. Let si be a convex inner edge.
Completeness. We now prove that any non-convex Hence, G� = si−1 si si+1 is a negative configuration. If
polygon has a proper configuration pair. First we dis- G� is feasible, we are done as a convex edge implies
cuss some properties of a closable or proper chain. α(G� ) > 0. If G� is not feasible, then let uj denote the
blocking vertex and assume without loss of generality
that i + 1 < j. Note that uj must be a vertex of the
Lemma 3 If S is a closable chain without a convex
chain as R− (G� ) ⊆ R(S). Consider the proper chain
inner edge and s2 is reflex, then S has a feasible neg-
S � = si , . . . , sj−1 . If S � has a convex inner edge, it
ative configuration G with a reflex first inner vertex,
must have a feasible negative configuration by induc-
α(G) > 0 and R− (G) ⊆ Rl (S) for any lid l of S.
tion. However, if it does not, S �� = si+1 , . . . , sj−1 is a
Proof. As α(S) > 0 and there are no convex inner closable chain in which s�2 is reflex. Note that the di-
edges, there must a configuration G� in S with a reflex rection of S �� is reversed when j < i−1. By Lemma 3,
first inner vertex and α(G� ) > 0 (implying that the S �� has a feasible negative configuration G�� . By the
second inner vertex is convex). Let G� be the first such lemma, the first inner vertex of G�� is reflex in the di-
configuration. A configuration G�� with α(G�� ) > 0 rection of S �� . If S �� was reversed, then sm ∈ / S �� , thus
and a convex first inner vertex may occur multiple sm−1 cannot be the inner edge of G . ��
�
times before G� , but it must always be preceded by an
Lemma 5 Every simple non-convex polygon P has a
edge g0�� with α({g0�� }∪G�� ) < 0 for the chain {g0�� }∪G��
feasible positive configuration G with α(G) < 0 or all
as otherwise G� is not the first of its kind along S.
positive configurations are feasible.

Proof. If P has a reflex edge, then let G be a config-

uration with a reflex inner edge. If G is feasible, we
are done as α(G) < 0. If it is not, we can define a
chain S that is inverted: the interior of S is in fact the
Figure 6: Configurations with α > 0 and a reflex first exterior of the polygon. Using Lemma 3 or Lemma 4,
inner vertex. we can now find a feasible negative configuration G−
with α(G− ) > 0 in S. This corresponds to a feasible
We prove this lemma by induction. Assume that positive configuration G+ in P with α(G+ ) < 0.
m = 3. Chain S is a configuration G� with a reflex If P has no reflex edge, then let G be an infeasible
first inner vertex. Any lid l of S must be on one side of positive configuration. If none exists, all positive con-
the line through s1 , whereas this track enforces a tri- figurations are feasible. Otherwise we can define an
angular contraction region on the other side. Hence, inverted chain using G. Thus, by Lemma 3, P has a
R− (G� ) ⊆ Rl (S) holds and G� is a feasible negative feasible positive configuration G� with α(G� ) < 0. �

165
27th European Workshop on Computational Geometry, 2011

Lemma 6 Every simple non-convex polygon P has a S � = et , et+1 , . . . , eb−1 does not contain edge ei . De-
proper configuration pair. pending on the convexity of vertex vt+2 , Lemma 3 or
Lemma 4 shows that there is a feasible negative con-
Proof. By Lemma 5, polygon P has a feasible posi-
figuration G�� in S � . We now argue why G�� cannot
tive configuration G+ = ei−1 ei ei+1 . Assume without
conflict with G+ . The only way to have a conflict is
loss of generality that the second inner vertex of G+ ,
when vb = vi . Since vi is then reflex, the only way to
vi+1 , is reflex. Let vj denote the first convex vertex
obtain a conflict is when vi−1 is reflex as well and vi−2
after vi+1 . Configuration G− = ej−1 ej ej+1 of which
is convex, such that ei−3 ei−2 ei−1 is a negative config-
vj is the first inner vertex, is negative. We distinguish
uration. However, ei−2 is the before-last edge in S �
two cases.
and starts at a convex vertex. Hence, Lemma 3 and
Assume that G− is feasible. If no edge is shared or
Lemma 4 guarantee to find another feasible negative
if edge ei+1 = ej−1 is shared (having a convex and a
configuration instead. �
reflex vertex), we have a proper configuration pair. If
ei−1 = ej+1 is shared but the other outer edge is not,
then vj , vj+1 = vi−1 , vi are the only convex vertices References
in P and there is at least one edge in between ei and [1] P. Bose, S. Cabello, O. Cheong, J. Gudmundsson,
ej−1 . This edge is the inner edge of a feasible positive M. van Kreveld, and B. Speckmann. Area-preserving
configuration, one that does not conflict with G− . approximations of polygonal paths. Journal of Dis-
crete Algorithms, 4(4):554–566, 2006.
ei ej ei ej ei ej [2] M. de Berg, M. van Kreveld, and S. Schirra. Topo-
logically correct subdivision simplification using the
bandwidth criterion. Cartography and Geographic In-
formation Science, 25(4):243–257, 1998.
Figure 7: Three cases if G− is feasible.
[3] D. Delling, A. Gemsa, M. Nöllenburg, and T. Pajor.
−
Now, assume that G is not feasible. The block- Path schematization for route sketches. In Proc. 12th
Scandinavian Workshop on Algorithm Theory, LNCS
ing point cannot be in between vi and vj+1 . If G− is
6139, pages 285–296, 2010.
blocked by a vertex vh , then, depending on the con-
vexity of vj+1 and vj+2 , either Lemma 3 or Lemma 4 [4] L. Guibas, J. Hershberger, J. Mitchell, and
J. Snoeyink. Approximating polygons and subdivi-
shows that there is a (non-conflicting) feasible nega-
sions with minimum-link paths. International Jour-
tive configuration. If G− is blocked by an edge eh ,
nal of Computational Geometry and Applications,
vj+1 must be reflex. We distinguish two cases on the 3:383–415, 1993.
closable chain S = ej , . . . , eh .
[5] J. Haunert and A. Wolff. Optimal and topologically
If S does not have a convex inner edge, then we refer
safe simplification of building footprints. In Proc.
to Lemma 3 to find a feasible negative configuration 18th International Conference on Advances in GIS,
G� . If G� does not conflict with G+ , we are done. If pages 192–201, 2010.
G� does conflict with G+ , we know that eh = ei−1
[6] H. Mayer. Scale-spaces for generalization of 3d build-
holds and that eh−1 is the inner edge of G� . More- ings. International Journal of Geographical Informa-
over, it must now hold that α(G+ ) > 0 and thus, by tion Science, 19:975–997, 2005.
Lemma 5, we need to consider this case only when all
[7] D. Merrick and J. Gudmundsson. Path simplification
positive configurations are feasible. Hence, the pos- for metro map layout. In Proc. 14th International
itive configuration ei ei+1 ei+2 is feasible and it does Symposium on Graph Drawing, LNCS 4372, pages
not conflict with G� . 258–269, 2006.
ej ei ej [8] W. Meulemans, A. van Renssen, and B. Speckmann.
ei G� Area-preserving subdivision schematization. In Proc.
eh 6th International Conference on GIScience, LNCS
eh G�
6292, pages 160–174, 2010.
Figure 8: Two cases if G− is not feasible and S has [9] G. Neyer. Line simplification with restricted orienta-
no convex inner edge. G� may conflict with G+ . tions. In Proc. 6th International Workshop on Algo-
rithms and Data Structures, LNCS 1663, pages 13–
If S has a convex inner edge et , then let G� denote 24, 1999.
the negative configuration et−1 et et+1 . If G� is feasi- [10] J. Swan, S. Anand, M. Ware, and M. Jackson. Au-
ble and not conflicting with G+ , we are done. If G� tomated schematization for web service applications.
is feasible but conflicting with G+ , we can argue as In Web and Wireless Geographical Information Sys-
tems, LNCS 4857, pages 216–226, 2007.
above: ei ei+1 ei+2 is a feasible positive configuration
and it does not conflict with G� . If G� is not feasible, [11] A. Wolff. Drawing subway maps: A survey.
then it must be blocked by some vertex vb . With- Informatik-Forschung und Entwicklung, 22(1):23–44,
2007.
out loss of generality, assume that the proper chain

166