|
Automatic label placement (sometimes called text placement or name placement) refers to the computer methods of placing labels automatically on a map or chart. This is related to the typographic design of such labels.
Maps communicate spatial information to the reader, therefore they are a medium of communication. The typical features depicted on a geographic map are line features (e.g. roads), area features (countries, parcels, forests, lakes, etc.), and point features (villages, cities, etc.). In addition to depicting the map's features in a geographically accurate manner, it is of critical importance to place the names that identify these features, in a way that the reader knows instantly which name describes which feature. For other uses, see Map (disambiguation). ...
Automatic text placement is one of the most difficult, complex, and time-consuming problems in mapmaking and GIS (Geographic Information System). Other kinds of computer-generated graphics - like charts, graphs etc. - require good placement of labels as well, not to mention engineering drawings. GIS redirects here. ...
This article does not cite any references or sources. ...
Naively placed labels overlap excessively, resulting in a map that is difficult or even impossible to read. Therefore, a GIS must allow a few possible placements of each label, and often also an option of resizing, rotating, or even removing (suppressing) the label. Then, it selects a set of placements that results in the least overlap, and has other desirable properties. For all but the most trivial setups, the problem is NP-Hard. In computational complexity theory, NP-hard (Non-deterministic Polynomial-time hard) refers to the class of decision problems that contains all problems H such that for all decision problems L in NP there is a polynomial-time many-one reduction to H. Informally this class can be described as containing...
Algorithms for automatic label placement
Rule-based algorithms The best computer algorithms are those that emulate an experienced human cartographer. Over centuries, cartographers have developed the art of mapmaking and label placement. For example, an experienced cartographer repeats road names several times for long roads, instead of placing them once, or in the case of Ocean City depicted by a point very close to the shore, the cartographer would place the label "Ocean City" over the water to emphasize that it is a coastal town.
Cartographers work based on accepted conventions and rules and they place labels in order of importance. For example, New York City, Vienna, Berlin, Paris, or Tokyo must show up on country maps because they are high-priority labels. Once those are placed, the cartographer places the next most important class of labels, for example major roads, rivers, and other large cities. In every step they ensure that (1) the text is placed in a way that the reader easily associates it with the feature, and (2) the label does not overlap with those already placed on the map.
Other algorithms The simplest greedy algorithm places consecutive labels on the map in positions that result in minimal extra overlap of labels. Its results are not satisfactory even for very simple problems, but it is extremely fast. The greedy algorithm determines the minimum number of US coins to give while making change. ...
Slightly more complex algorithms rely on local optimization to reach a local optimum of a placement evaluation function - in each iteration placement of a single label is moved to another position, and if it improves the result, the move is preserved. It performs reasonably well for maps that are not too densely labelled. Slightly more complex variations try moving 2 or more labels at the same time. The algorithm ends after reaching some local optimum.
The algorithm that yields good results with relatively good performance - simulated annealing - is very simple. It works like local optimization, but it may keep a change even if it worsens the result. The chance of keeping such a change is  , where ΔE is the change in the evaluation function, and T is the temperature. The temperature is gradually lowered according to the annealing schedule. When the temperature is high, simulated annealing performs almost random changes to the label placement, being able to escape a local optimum. Later, when hopefully a very good local optimum has been found, it behaves in a manner similar to local optimization. The main challenges in developing a simulated annealing solution are choosing a good evaluation function and a good annealing schedule. Generally too fast cooling will degrade the solution, and too slow cooling will degrade the performance, but the schedule is usually quite a complex algorithm, with more than just one parameter. For other uses, see Annealing. ...
local optimum is a term in Applied mathematics and Computer Science. ...
Another class of direct search algorithms are the various evolutionary algorithms, e.g. genetic algorithms. Other algorithms are also used, like various graph solutions, integer programming etc. In artificial intelligence, an evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. ...
A genetic algorithm (GA) is a search technique used in computing to find exact or approximate solutions to optimization and search problems. ...
One simple optimization that's important on real maps is dividing a set of labels into smaller sets that can be solved independently. Two labels are rivals if they can overlap in one of the possible placements. Transitive closure of this relation divides the set of labels into possibly much smaller sets. On uniformly and densely labelled maps, usually the single set will contain the majority of labels, and on maps for which the labelling is not uniform it may bring very big performance benefits. For example when labelling a map of the world, North America may be probably labelled independently from Eurasia etc. In mathematics, a binary relation R over a set X is transitive if it holds for all a, b, and c in X, that if a is related to b and b is related to c, then a is related to c. ...
North American redirects here. ...
For other uses, see Eurasia (disambiguation). ...
Text placement solutions for GIS and mapping applications There are several software solutions available for labeling in GIS environments. Do an Internet search for the following keywords:
References - Imhof, E., “Die Anordnung der Namen in der Karte,” Annuaire International de Cartographie II, Orell-Füssli Verlag, Zürich, 93-129, 1962.
- Freeman, H.,, Map data processing and the annotation problem, Proc. 3rd Scandinavian Conf. on Image Analysis, Chartwell-Bratt Ltd. Copenhagen, 1983.
- Ahn, J. and Freeman, H., “A program for automatic name placement,” Proc. AUTO-CARTO 6, Ottawa, 1983. 444-455.
- Freeman, H., “Computer Name Placement,” ch. 29, in Geographical Information Systems, 1, D.J. Maguire, M.F. Goodchild, and D.W. Rhind, John Wiley, New York, 1991, 449-460.
External links - Alexander Wolff's Map Labeling Site
- The Map-Labeling Bibliography
- Gallery of automatically labeled maps using rule-based algorithms
- Freeman, Herbert: Automated Cartographic Text Placement
|
Feeds |
Contact