Singapore Institute of Technology
main.pdf (13.58 MB)

Topology-Aware Line Densification for Reprojected Curves on Maps

Download (13.58 MB)
conference contribution
posted on 2023-10-09, 01:46 authored by Michael Thorsten GastnerMichael Thorsten Gastner, Nihal Z Miaji, Adi Singhania, Nguyen Phong Le

Many map features, such as administrative borders, coastlines, roads or rivers, are conventionally represented as polylines on a Cartesian plane. However, these objects are located on the curved surface of the Earth, necessitating an approximation when representing them as flat polylines. Ideally, the positions of vertices along each polyline should be chosen to represent the topology of mapped features accurately. For example, boundaries between adjacent geographic regions should have coincident vertices to eliminate gaps or overlaps.Yet, a topologically correct representation in one map projection does not guarantee that the same vertices will generate a valid polyline topology in another map projection due to the distortion of straight lines into curves. To restore a valid topology, it may be necessary to insert additional vertices before transforming the polylines from one map projection to another.

Conventional methods insert a fixed number of equidistant vertices between the original consecutive vertex pairs or add vertices at the midpoints of line segments that exceed a predetermined distance threshold. However, these simplistic approaches significantly increase the vertex count and do not ensure topological validity. In this presentation, we introduce an alternative method where vertex insertion is responsive to the local polyline geometry, thus ensuring a valid topology. The algorithm employs an auxiliary quadtree and its Delaunay triangulation to insert vertices (Figure 1). After projecting all the vertices, topology-aware line simplification is applied to reduce the vertex count.




Journal/Conference/Book title

19th International Conference on Geoinformation and Cartography, Zadar, Croatia

Publication date



  • Published

Rights statement

Michael T. Gastner, Nihal Z. Miaji, Adi Singhania and Nguyen Phong Le (2023) Presentation at 19th International Conference on Geoinformation and Cartography, Zadar, Croatia.

Corresponding author

Michael T Gastner

Project ID

  • 14612 (R-R22-A405-0003) Designing mobile-friendly cartograms for visualising geospatial data

Usage metrics



    Ref. manager