A simple and efficient algorithm for high-quality line labeling
Alexander Wolff, L. Knipping, Marc J. van Kreveld, Tycho Strijk, Pankaj Agarwal · 2001
Introduction The interest in algorithms that automatically place labels on maps, graphs, or diagrams has increased with the advance in type-setting technology and the amount of information to be visualized. However, though manually labeling a map is estimated to take fifty percent of total map production time (Morrison, 1980), most geographic information systems (GIS) o#er only very basic label-placement features. In practice, a GIS user is still forced to invest several hours in order to eliminate manually all label-label and label-feature intersections on a map. In this chapter, we suggest an algorithm that labels one of the three classes of map objects, namely polygonal chains, such as rivers or streets. Our method is simple and e#cient. At the same time, it produces results of high aesthetical quality. It is the first that fulfills both of the following two requirements: it allows curved labels and runs in O(n 2 ) time, where