A General Cartographic Labelling Algorithm

Abstract

Some apparently powerful algorithms for automatic label placement on maps use heuristics that capture considerable cartographic expertise but are hampered by provably inefficient methods of search and optimization. On the other hand, no approach to label placement that is based on an efficient optimization technique has been applied to the production of general cartographic maps—those with labelled point, line, and area features—and shown to generate labellings of acceptable quality. We present an algorithm for label placement that achieves the twin goals of practical efficiency and high labelling quality by combining simple cartographic heuristics with effective stochastic optimization techniques.