Labelling Maps using Multi-Objective Evolutionary Algorithms
Lucas Bradstreet · 2004
Map labelling is the problem of arranging place names on maps such that labels do not overlap and are clear to a reader. Determining the optimal label arrangement is combinatorially difficult and has so far defied total automation. As such, map making remains a costly process. Today’s map labelling techniques generally consider only the number of overlaps during optimisation and while they do succeed at minimising this objective, there are other objectives that contribute to the overall quality of a map. We will discuss a multi-objective evolutionary algorithm designed to automate map labelling when assessing overall map quality by several criteria such as label overlaps, clarity, font size and aesthetics. This process allows a user to select their optimal compromise between each of the quality criteria. As the best compromise between these objectives is highly subjective and dependant on the map being labelled, our algorithm is superior to others in that it simultaneously finds a set of trade-off solutions rather than applying a set evaluation function that predefines the way that these quality constraints should be optimised. We have demonstrated several example real world maps to prove that this technique is able to produce maps of higher quality than competing techniques. We have also selected several final labelled maps which illuminate the compromises between quality criteria.