tr-2007-216-full.pdf (89.9 kB)
A fast and simple heuristic for metro map path simplification
reportposted on 2022-07-25, 00:31 authored by T Dwyer, N Hurst, D Merrick
We give a heuristic for simplifying a path defined by a given sequence of points. The heuristic seeks to fit the points with a set of line segments aligned with a limited set of possible directions. Such “schematic path simplification” has application in automatically drawing simplified metro maps from geographic data. We show that a simple version of our algorithm produces reasonable results against real-world data and runs in linear time with respect to the number of points (assuming a small fixed number of possible directions). We then give some refinements to the algorithm which may improve the quality of the results but which significantly increase the worst-case time complexity.