research-article

Area-Preserving Simplification and Schematization of Polygonal Subdivisions

Authors:

Wouter Meulemans,

André Van Renssen,

Bettina SpeckmannAuthors Info & Claims

ACM Transactions on Spatial Algorithms and Systems (TSAS), Volume 2, Issue 1

Article No.: 2, Pages 1 - 36

https://doi.org/10.1145/2818373

Published: 08 April 2016 Publication History

Abstract

In this article, we study automated simplification and schematization of territorial outlines. We present a quadratic-time simplification algorithm based on an operation called edge-move. We prove that the number of edges of any nonconvex simple polygon can be reduced with this operation. Moreover, edge-moves preserve area and topology and do not introduce new orientations. The latter property in particular makes the algorithm highly suitable for schematization in which all resulting lines are required to be parallel to one of a given set of lines (orientations). To obtain such a result, we need only to preprocess the input to use only lines that are parallel to one of the given set. We present an algorithm to enforce such orientation restrictions, again without changing area or topology. Experiments show that our algorithms obtain results of high visual quality.

References

[1]

M. A. Abam, S. Daneshpajouh, L. Deleuran, S. Ehsani, and M. Ghodsi. 2014. Computing homotopic line simplification. Computational Geometry: Theory and Applications 47, 7, 728--739.

[2]

E. M. Arkin, L. P. Chew, D. P. Huttenlocher, K. Kedem, and J. S. B. Mitchell. 1991. An efficiently computable metric for comparing polygonal shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence 13, 3, 209--216.

Digital Library

[3]

T. Barkowsky, L. J. Latecki, and K.-F. Richter. 2000. Schematizing maps: Simplification of geographic shape by discrete curve evolution. In Spatial Cognition II. Lecture Notes in Computer Science, Vol. 1849. Springer, 41--53.

Digital Library

[4]

M. de Berg, M. van Kreveld, and S. Schirra. 1998. Topologically correct subdivision simplification using the bandwidth criterion. Cartography and Geographic Information Science 25, 4, 243--257.

[5]

P. Bose, S. Cabello, O. Cheong, J. Gudmundsson, M. van Kreveld, and B. Speckmann. 2006. Area-preserving approximations of polygonal paths. Journal of Discrete Algorithms 4, 4, 554--566.

Digital Library

[6]

K. Buchin, W. Meulemans, and B. Speckmann. 2011a. Area-preserving C-oriented schematization. In Abstracts of the 27th European Workshop on Computational Geometry. 163--166.

[7]

K. Buchin, W. Meulemans, and B. Speckmann. 2011b. A new method for subdivision simplification with applications to urban-area generalization. In Proceedings of the 19th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems. 261--270.

Digital Library

[8]

M. E. Buchin. 2007. On the Computability of the Fréchet Distance Between Triangulated Surfaces. Ph.D. Dissertation. Freie Universität Berlin.

[9]

S. Cabello, M. de Berg, and M. van Kreveld. 2005. Schematization of networks. Computational Geometry: Theory and Applications 30, 3, 223--238.

Digital Library

[10]

T. Christ, D. Pálvölgyi, and M. Stojaković. 2010. Consistent digital line segments. In Proceedings of the 26th Symposium on Computational Geometry. 11--18.

Digital Library

[11]

S. Cicerone and M. Cermignani. 2012. Fast and simple approach for polygon schematization. In Computational Science and Its Applications—ICCSA 2012. Lecture Notes in Computer Science, Vol. 7333. Springer, 267--279.

Digital Library

[12]

S. Daneshpajouh, M. Ghodsi, and A. Zarei. 2012. Computing polygonal path simplification under area measures. Graphical Models 74, 5, 283--289.

Digital Library

[13]

D. Delling, A. Gemsa, M. Nöllenburg, and T. Pajor. 2010. Path schematization for route sketches. In Algorithm Theory—SWAT 2010. Lecture Notes in Computer Science, Vol. 6139. Springer, 285--296.

Digital Library

[14]

T. C. van Dijk, A. van Goethem, J.-H. Haunert, W. Meulemans, and B. Speckmann. 2013. Accentuating focus map via partial schematization. In Proceedings of the 21st ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems. 438--441.

Digital Library

[15]

T. C. van Dijk, A. van Goethem, J.-H. Haunert, W. Meulemans, and B. Speckmann. 2014. Map schematization with circular arcs. In Geographic Information Science. Lecture Notes in Computer Science, Vol. 8728. Springer, 1--17.

[16]

D. H. Douglas and T. K. Peucker. 1973. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica 10, 2, 112--122.

[17]

R. Estkowski and J. S. B. Mitchell. 2001. Simplifying a polygonal subdivision while keeping it simple. In Proceedings of the 17th Symposium on Computational Geometry. 40--49.

Digital Library

[18]

M. Fink, H. Haverkort, M. Nöllenburg, M. J. Roberts, J. Schuhmann, and A. Wolff. 2013. Drawing metro maps using Bézier curves. In Graph Drawing. Lecture Notes in Computer Science, Vol. 7704. Springer, 463--474.

Digital Library

[19]

A. Gemsa, M. Nöllenburg, T. Pajor, and I. Rutter. 2011. On d-regular schematization of embedded paths. In SOFSEM 2011: Theory and Practice of Computer Science. Lecture Notes in Computer Science, Vol. 6543. Springer, 260--271.

Digital Library

[20]

A. van Goethem, W. Meulemans, A. Reimer, H. Haverkort, and B. Speckmann. 2013. Topologically safe curved schematization. Cartographic Journal 50, 3, 276--285.

[21]

A. van Goethem, W. Meulemans, B. Speckmann, and J. Wood. 2014. Exploring curved schematization. In Proceedings of the 7th IEEE Pacific Visualization Symposium. 1--8.

Digital Library

[22]

L. J. Guibas, J. E. Hershberger, J. S. B. Mitchell, and J. S. Snoeyink. 1993. Approximating polygons and subdivisions with minimum-link paths. International Journal of Computational Geometry and Applications 3, 383--415.

[23]

J.-H. Haunert. 2012. A symmetry detector for map generalization and urban-space analysis. ISPRS Journal of Photogrammetry and Remote Sensing 74, 66--77.

[24]

H. Imai and M. Iri. 1988. Polygonal approximations of a curve—formulations and algorithms. Computational Morphology 6, 71--86.

[25]

B. van de Kraats, M. van Kreveld, and M. Overmars. 1995. Printed circuit board simplification: Simplifying subdivisions in practice. In Proceedings of the 11th Symposium on Computational Geometry. 430--431.

Digital Library

[26]

A. Marzal and V. Palazón. 2005. Dynamic time warping of cyclic strings for shape matching. In Pattern Recognition and Image Analysis. Lecture Notes in Computer Science, Vol. 3687. Springer, 644--652.

Digital Library

[27]

D. Merrick and J. Gudmundsson. 2006. Path simplification for metro map layout. In Graph Drawing. Lecture Notes in Computer Science, Vol. 4372. Springer, 258--269.

Digital Library

[28]

W. Meulemans. 2014. Similarity Measures and Algorithms for Cartographic Schematization. Ph.D. Dissertation. Technische Universiteit Eindhoven.

[29]

W. Meulemans, A. van Renssen, and B. Speckmann. 2010. Area-preserving subdivision schematization. In Geographic Information Science. Lecture Notes in Computer Science, Vol. 6292. Springer, 160--74.

Digital Library

[30]

M. E. Munich and P. Perona. 1999. Continuous dynamic time warping for translation-invariant curve alignment with applications to signature verification. In Proceedings of the 7th IEEE International Conference on Computer Vision. 108--115.

[31]

N. Mustafa, E. Koutsofios, S. Krishnan, and S. Venkatasubramanian. 2001. Hardware-assisted view-dependent map simplification. In Proceedings of the 17th Symposium on Computational Geometry. 50--59.

Digital Library

[32]

G. Neyer. 1999. Line simplification with restricted orientations. In Algorithms and Data Structures. Lecture Notes in Computer Science, Vol. 1663. Springer, 13--24.

Digital Library

[33]

M. Nöllenburg and A. Wolff. 2011. Drawing and labeling high-quality metro maps by mixed-integer programming. IEEE Transactions on Visualization and Computer Graphics 17, 5, 626--641.

Digital Library

[34]

P. M. van der Poorten and C. B. Jones. 2002. Characterisation and generalisation of cartographic lines using Delaunay triangulation. International Journal of Geographical Information Science 16, 8, 773--794.

[35]

N. Regnauld, A. Edwardes, and M. Barrault. 1999. Strategies in building generalisation: Modelling the sequence, constraining the choice. In Proceedings of the ICA’99 Workshop on Progress in Automated Map Generalization.

[36]

A. Reimer. 2010. Understanding chorematic diagrams: Towards a taxonomy. Cartographic Journal 47, 4, 330--350.

[37]

A. Reimer and W. Meulemans. 2011. Parallelity in chorematic territorial outlines. In Proceedings of the 14th ICA Workshop on Generalisation and Multiple Representation.

[38]

M. J. Roberts. 2012. Underground Maps Unravelled—Explorations in Information Design. Self-Published.

[39]

J. Swan, S. Anand, M. Ware, and M. Jackson. 2007. Automated schematization for Web service applications. In Web and Wireless Geographical Information Systems. Lecture Notes in Computer Science, Vol. 4857. Springer, 216--226.

Digital Library

[40]

D. Tutić and M. Lapaine. 2009. Area preserving cartographic line generalization. Cartography and Geoinformation 8, 11, 84--100.

[41]

B. Tversky. 1993. Cognitive maps, cognitive collages, and spatial mental models. In Spatial Information Theory: A Theoretical Basis for GIS. Lecture Notes in Computer Science, Vol. 716. Springer, 14--24.

[42]

M. Visvalingam and J. D. Whyatt. 1993. Line generalisation by repeated elimination of points. Cartographic Journal 30, 1, 46--51.

Cited By

Yang MZou RAi TYan X(2024)Regularizing building outlines extracted from remote sensing images by integrating multiple algorithmsGeocarto International10.1080/10106049.2024.237032239:1Online publication date: 26-Jun-2024
https://doi.org/10.1080/10106049.2024.2370322
Nöllenburg MTerziadis S(2024)Computing Data-driven Multilinear Metro MapsThe Cartographic Journal10.1080/00087041.2024.230447660:4(367-382)Online publication date: 2-Jul-2024
https://doi.org/10.1080/00087041.2024.2304476
Forsch AHaunert J(2024)Metrochrones: Schematic Isochrones for Schematic Metro MapsThe Cartographic Journal10.1080/00087041.2023.228443660:4(383-401)Online publication date: 23-Jul-2024
https://doi.org/10.1080/00087041.2023.2284436
Show More Cited By

Index Terms

Area-Preserving Simplification and Schematization of Polygonal Subdivisions
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

A topology-preserving polygonal simplification using vertex clustering
GRAPHITE '05: Proceedings of the 3rd international conference on Computer graphics and interactive techniques in Australasia and South East Asia

Product developers have used a lot of polygon data, approximated from 3D-CAD data, as a collaboration tool on the Internet. It is difficult to deal with this data for example with respect to transmission, computational cost, or rendering, so ...
Hierarchical topology-preserving simplification of terrains

We present an algorithm for simplifying terrain data that preserves topology. We use a decimation algorithm that simplifies the given data set using hierarchical clustering. Topology constraints, along with local error metrics, are used to ensure ...
Area-preserving subdivision schematization
GIScience'10: Proceedings of the 6th international conference on Geographic information science

We describe an area-preserving subdivision schematization algorithm: the area of each region in the input equals the area of the corresponding region in the output. Our schematization is axis-aligned, the final output is a rectilinear subdivision. We ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Spatial Algorithms and Systems

ACM Transactions on Spatial Algorithms and Systems Volume 2, Issue 1

April 2016

150 pages

ISSN:2374-0353

EISSN:2374-0361

DOI:10.1145/2903758

Editor:
Hanan Samet
University of Maryland, College Park

Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 April 2016

Accepted: 01 August 2015

Revised: 01 June 2015

Received: 01 November 2013

Published in TSAS Volume 2, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Netherlands Organisation for Scientific Research (NWO)
NSERC and Carleton University’s President’s 2010 Doctoral Fellowship
JST, ERATO, Kawarabayashi Large Graph Project
EU Horizon 2020 programme, under a Marie Skłodowska-Curie Individual Fellowship

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
333
Total Downloads

Downloads (Last 12 months)27
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yang MZou RAi TYan X(2024)Regularizing building outlines extracted from remote sensing images by integrating multiple algorithmsGeocarto International10.1080/10106049.2024.237032239:1Online publication date: 26-Jun-2024
https://doi.org/10.1080/10106049.2024.2370322
Nöllenburg MTerziadis S(2024)Computing Data-driven Multilinear Metro MapsThe Cartographic Journal10.1080/00087041.2024.230447660:4(367-382)Online publication date: 2-Jul-2024
https://doi.org/10.1080/00087041.2024.2304476
Forsch AHaunert J(2024)Metrochrones: Schematic Isochrones for Schematic Metro MapsThe Cartographic Journal10.1080/00087041.2023.228443660:4(383-401)Online publication date: 23-Jul-2024
https://doi.org/10.1080/00087041.2023.2284436
Forsch AKemna RLangetepe EHaunert J(2024)Polyline Morphing for Animated Schematic MapsJournal of Geovisualization and Spatial Analysis10.1007/s41651-024-00198-w8:2Online publication date: 8-Oct-2024
https://doi.org/10.1007/s41651-024-00198-w
Samsonov TYakimova OPotemkin DGuseva O(2023)Spatial variation of feature density in multiscale topographic dataGEOGRAPHY, ENVIRONMENT, SUSTAINABILITY10.24057/2071-9388-2022-12716:1(86-102)Online publication date: 7-Apr-2023
https://doi.org/10.24057/2071-9388-2022-127
Yan XYang M(2023)A deep learning approach for polyline and building simplification based on graph autoencoder with flexible constraintsCartography and Geographic Information Science10.1080/15230406.2023.221810651:1(79-96)Online publication date: 13-Jun-2023
https://doi.org/10.1080/15230406.2023.2218106
Zhou ZFu CWeibel R(2023)Move and remove: Multi-task learning for building simplification in vector maps with a graph convolutional neural networkISPRS Journal of Photogrammetry and Remote Sensing10.1016/j.isprsjprs.2023.06.004202(205-218)Online publication date: Aug-2023
https://doi.org/10.1016/j.isprsjprs.2023.06.004
Bonerath AHaunert JMitchell JNiedermann B(2023)Shortcut hulls: Vertex-restricted outer simplifications of polygonsComputational Geometry10.1016/j.comgeo.2023.101983112(101983)Online publication date: Jun-2023
https://doi.org/10.1016/j.comgeo.2023.101983
Zhai RLi AYin JDu JQiu Y(2022)A Progressive Simplification Method for Buildings Based on Structural SubdivisionISPRS International Journal of Geo-Information10.3390/ijgi1107039311:7(393)Online publication date: 12-Jul-2022
https://doi.org/10.3390/ijgi11070393
Shen YLi JZhao RHan F(2022)Multiresolution Mapping of Land Cover From Remote Sensing Images by Geometric GeneralizationIEEE Transactions on Geoscience and Remote Sensing10.1109/TGRS.2021.307679860(1-20)Online publication date: 2022
https://doi.org/10.1109/TGRS.2021.3076798
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents