Label placement Rules, techniques

Label placement

• Rules, techniques

Labels on a map

• Text, name of map features

• No fixed geographical position

• Labels of point features (0-dim), line features (1-dim), areal features (2-dim)

Labels of point features

• Cities on a small-scale map

• Heights of peaks

• Measured values at measurement points

Labels of point features

Labels of line features

• Rivers

• Heights on contour lines

• Streets

Labels of areal features

• Countries, oceans, forests, lakes

Three kinds of labels

Label placement

• Where should the text be placed? Which shape?

• 20% - 50% of the map production time; can be automated

• Which rules do cartographers use? - No overlap  readability - Clear for which feature  association - Aesthetical guidelines

Rules according to Imhof (1962)

Problematic cases

Another problematic case

Specific rules point labels

• Label must be close to point, preferably to the right and above

• No overlap with other labels, except perhaps in the spacing of the areal label

• Label may intersect line feature; then line must be interrupted

• Points close to large body of water must have their label in the water. In other cases there may be no line between a point and its label

• If it cannot be avoided, a name may be split over two lines of text

Specific rules line labels

• Label must follow shape of river

• Label should not bend upwards and downwards consecutively

• At long line features the label must be repeated

• No extra spacing between characters, spacing between words of the label is allowed

• For vertical line features: upward reading direction left on the map and downward right on the map

• Contour lines: labels must interrupt contour line; top label points to higher regions

Specific rules areal labels

• Horizontal labeling is good unless this conflicts with the dominant shape of the region

• Monotonous curving; no inflection points

• Label must be spread over whole region

• Non-horizontal labels must be curved

• Adjacent regions preferably have same shape of label (both horizontal, e.g.)

• Sometimes an areal label may be outside its region, but not in another labeled region

Strategies for automatic label placement

• Compute for each feature various candidate positions according to the rules

• Choose for each feature one candidate position, such that the chosen positions don’t have overlap

• Sometimes a feature cannot be labeled, and sometimes the label of a feature must be repeated

Candidate positions points

• Point labels

Candidate positions lines

• Compute strip with character height above the river which follows the shape approximately, but doesn’t have too high curvature (e.g. with opening, closure)

• Determine suitable segments in the strip as candidates

Candidate positions regions

• Determine skeleton (medial axis) of region (polygon)

• Determine longest path on skeleton as dominant shape

• Choose middle with suitable character spacing

• Vary a little for more candidates

Candidate positions regions, horizontal

• Choose spacing and determine length : height of label

• Compute largest scaled copy of the label (rectangle) that just fits inside the polygon

• Put the label in the correct font size in the middle of the scaled copy

Removal part of the candidates

• Compute those candidate positions that intersect map features significantly, or would give unclear association, and remove them

Reasons for removal

Choosing from the candidates

• Translate to a graph problem (graph G): - each candidate position of each feature is a node in G - two nodes have an edge in G if their candidate positions intersect - two nodes have an edge in G if their candidate positions are of the same feature

Example

Computing intersecting candidates

• Each candidate is (approximately) a simple geometric shape

• Determine all pairs of intersecting candidates using a plane sweep algorithm

• O((n+k) log n) time, with k the number of intersecting pairs

• Typically: k = O(n)

Graph problem: maximum independent set

• Also called maximum stable set

• NP-hard problem: solving optimally is very time consuming

• Cannot be approximated with performance guarantees

• Many heuristics

Heuristics for maximum independent set

• Select each candidate that is adjacent to a clique, and remove the candidate and clique from the graph

• Repeat as long as possible (optimal selections)

• Select candidate that intersects few other candidates

• Select candidate if a feature has only one (or a few) candidates left

• Eliminate candidates that intersect many candidates

Refinements

• Features and labels have different importances  translate problem to maximum weight independent set

• First place areal labels, then determine candidate point labels and select, then determine line labels and place them (order of decreasing freedom of placement)

Labels in GIS

• Can label positions be pre-computed and stored, for better efficiency? No, because

• Which themes are shown is not known beforehand;
• Which scale and size of the map is needed is not known beforehand

Labels on interactive maps

• Pop-up labels, or labels only after click

• During zooming in, remove labels when their feature goes outside the frame

• During zooming in, allow more and more labels; during zooming out, remove labels of less important features Size of labels does not change!

Commercial packages

• Maplex for ESRI’s ArcInfo and ArcGIS

• EverName for MapInfo

• MapText for ArcInfo, ArcGIS, MapInfo, GeoMedia, …

User Interface of EverName

Output of EverName

Output of MapText