Topology-Aware Line Densification for Reprojected Curves on Maps

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.