From Point Feature Label Placement to Map Labelling
Maxence Laurent, Éric D. Taillard, Oliver Ertz, Francis Grin, Daniel Rappo, Sebastien Roh, Route de Cheseaux · ArODES (HES-SO (https://www.hes-so.ch/)) · 2009
Some of the objects should be labelled by a text that should be placed close to it. In the case of labelling a point-feature, the text is placed around the object (and not directly above it, to avoid obscuration of the feature). The goal of point-feature labelling is to find a position for each label in such a way that no label overlaps another one or overlaps the symbol marking a point. Very often, finding a conflict-free labelling is not possible. So, a labelling containing as many label as possible without conflicts is searched for. As soon as more than one candidate position is possible for placing the label of each object, the problem of choosing an adequate position for each label is difficult (NP-Hard). Basically, the problem is modelled as finding a stable set of maximum cardinality in a conflict graph. The conflict graph is built as follows : a vertex is associated to each candidate label and there is an edge connecting two vertices if the associated labels cannot be placed simultaneously on the map, either because they overlap or they label the same object.