A simple and efficient algorithm for high-quality line labeling

Abstract

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) offer 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 efficient. 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(n2) time, where n is the number of points of the polyline.