An algorithm for locating candidate labelling boxes within a polygon

Vector-based geographic information systems usually require annotation, such as a polygon number or attribute data, in a suitable location within a polygon. Traditional methods usually compute the polygon centroid, test the centroid for inclusion or exclusion, and select some alternative point when the centroid falls outside the polygon. Two problems are associated with this approach: (1) the text can be centered on the point, but may be placed in a visually awkward place, and (2) part of the text may fall outside the polygon and may overlap other polygon boundaries or other text labels. An algorithm is presented that circumvents both of these problems, by computing a number of horizontal candidate labelling rectangles (boxes) within a polygon from which a suitable selection can be made or from which one may conclude that the text label does not fit the polygon.