A grid algorithm suitable for line and area feature label placement

The labelling problem has been central in the framework of automated cartography. The quality and efficiency of label placement have great influences on the expression and understanding of maps. Although many algorithms have been developed to address the labelling problems of point features, very little work has been directed towards those of line or area features. Owing to the weakness of these approaches, the label quality rules of line or area features were reconsidered and strengthened based on the cognizance of cartographers. Such rules should be separate from the labelling algorithms to be appropriate for the program’s flexibility. A new grid algorithm, in contrast to traditional vector-based methods, is proposed. For the line feature, the cells passed by a line are computed, and their parallel cells are selected as the bottom of the text. For the area feature, a maximal inclusive rectangle is searched for the numerical label of its corresponding polygon (area), the midpoint of which is considered the potential position. A test program was developed and shows that the algorithm is simple and appropriate. The efficiency of the algorithm is closely related to the cell density.