Placement automatique des étiquettes - Automatic label placement
Le placement automatique d'étiquettes , parfois appelé placement de texte ou placement de noms , comprend les méthodes informatiques permettant de placer automatiquement des étiquettes sur une carte ou un graphique. Ceci est lié à la conception typographique de ces étiquettes .
Les entités typiques représentées sur une carte géographique sont des entités linéaires (par exemple des routes), des entités surfaciques (pays, parcelles, forêts, lacs, etc.) et des entités ponctuelles (villages, villes, etc.). En plus de représenter les caractéristiques de la carte d'une manière géographiquement précise, il est d'une importance cruciale de placer les noms qui identifient ces caractéristiques, de manière à ce que le lecteur sache instantanément quel nom décrit quelle caractéristique.
Le placement automatique de texte est l'un des problèmes les plus difficiles, les plus complexes et les plus longs de la cartographie et du SIG (Système d'information géographique) . D'autres types de graphiques générés par ordinateur - comme les tableaux , les graphiques, etc. - nécessitent également un bon placement des étiquettes, sans parler des dessins techniques et des programmes professionnels qui produisent ces dessins et graphiques, comme des feuilles de calcul (par exemple Microsoft Excel ) ou des logiciels informatiques. (par exemple Mathematica ).
Les étiquettes placées naïvement se chevauchent excessivement, ce qui donne une carte difficile voire impossible à lire. Par conséquent, un SIG doit permettre quelques emplacements possibles de chaque étiquette, et souvent aussi une option de redimensionnement, de rotation ou même de suppression (suppression) de l'étiquette. Ensuite, il sélectionne un ensemble de placements qui entraîne le moins de chevauchements et possède d'autres propriétés souhaitables. Pour toutes les configurations sauf les plus triviales, le problème est NP-hard .
Algorithmes basés sur des règles
Les algorithmes basés sur des règles tentent d'imiter un cartographe humain expérimenté. Au fil des siècles, les cartographes ont développé l'art de la cartographie et du placement d'étiquettes. Par exemple, un cartographe expérimenté répète plusieurs fois les noms de routes pour les routes longues, au lieu de les placer une fois, ou dans le cas d'Ocean City représenté par un point très proche du rivage, le cartographe placerait l'étiquette « Ocean City » sur le terre pour souligner qu'il s'agit d'une ville côtière.
Les cartographes travaillent sur la base de conventions et de règles acceptées, telles que celles détaillées par le cartographe suisse Eduard Imhof en 1962. Par exemple, New York, Vienne, Berlin, Paris ou Tokyo doivent apparaître sur les cartes des pays car ce sont des étiquettes de haute priorité. Une fois ceux-ci placés, le cartographe place la prochaine classe d'étiquettes la plus importante, par exemple les routes principales, les rivières et autres grandes villes. À chaque étape, ils s'assurent que (1) le texte est placé de manière à ce que le lecteur l'associe facilement à l'entité, et (2) que l'étiquette ne chevauche pas celles déjà placées sur la carte.
Algorithmes d'optimisation locale
L' algorithme glouton le plus simple place des étiquettes consécutives sur la carte dans des positions qui entraînent un chevauchement minimal des étiquettes. Ses résultats ne sont pas parfaits même pour des problèmes très simples, mais il est extrêmement rapide.
Des algorithmes légèrement plus complexes reposent sur une optimisation locale pour atteindre un optimum local d'une fonction d'évaluation de placement - à chaque itération, le placement d'une seule étiquette est déplacé vers une autre position, et s'il améliore le résultat, le déplacement est conservé. Il fonctionne assez bien pour les cartes qui ne sont pas trop densément étiquetées. Des variantes légèrement plus complexes essayez de déplacer 2 étiquettes ou plus en même temps. L'algorithme se termine après avoir atteint un optimum local.
Un algorithme simple – le recuit simulé – donne de bons résultats avec des performances relativement bonnes. Cela fonctionne comme une optimisation locale, mais cela peut garder un changement même si cela aggrave le résultat. La chance de conserver un tel changement est , où est le changement dans la fonction d'évaluation, et est la température . La température est progressivement abaissée selon le programme de recuit . Lorsque la température est élevée, le recuit simulé effectue des changements presque aléatoires du placement de l'étiquette, pouvant échapper à un optimum local . Plus tard, quand on espère qu'un très bon optimum local a été trouvé, il se comporte d'une manière similaire à l'optimisation locale. Les principaux défis dans le développement d'une solution de recuit simulé sont le choix d'une bonne fonction d'évaluation et d'un bon programme de recuit. Généralement, un refroidissement trop rapide dégradera la solution et un refroidissement trop lent dégradera les performances, mais le programme est généralement un algorithme assez complexe, avec plus d'un seul paramètre.
Une autre classe d'algorithmes de recherche directe sont les divers algorithmes évolutionnaires , par exemple les algorithmes génétiques .
Algorithmes de division pour régner
Une optimisation simple qui est importante sur les cartes réelles consiste à diviser un ensemble d'étiquettes en ensembles plus petits qui peuvent être résolus indépendamment. Deux labels sont concurrents s'ils peuvent se chevaucher dans l'un des emplacements possibles. La fermeture transitive de cette relation divise l'ensemble d'étiquettes en ensembles éventuellement beaucoup plus petits. Sur les cartes uniformément et densément étiquetées, le jeu unique contiendra généralement la majorité des étiquettes, et sur les cartes pour lesquelles l'étiquetage n'est pas uniforme, cela peut apporter de très gros avantages en termes de performances. Par exemple, lors de l'étiquetage d'une carte du monde, l' Amérique est étiquetée indépendamment de l' Eurasie, etc.
2-algorithmes de satisfiabilité
Si un problème d'étiquetage de carte peut être réduit à une situation dans laquelle chaque étiquette restante n'a que deux positions potentielles dans lesquelles elle peut être placée, alors il peut être résolu efficacement en utilisant une instance de 2-satisfiabilité pour trouver un placement évitant toute paire conflictuelle des stages ; plusieurs algorithmes de placement d'étiquettes exacts et approximatifs pour des types de problèmes plus complexes sont basés sur ce principe.
Autres algorithmes
Les algorithmes de placement automatique d'étiquettes peuvent utiliser n'importe lequel des algorithmes pour trouver l' ensemble disjoint maximal à partir de l'ensemble d'étiquettes potentielles. D'autres algorithmes peuvent également être utilisés, comme diverses solutions de graphes, la programmation en nombres entiers, etc.
Remarques
Les références
- Freeman, H., Traitement des données cartographiques et problème d'annotation, Proc. 3e Conf. Scandinave sur l'analyse d'images, Chartwell-Bratt Ltd. Copenhague, 1983.
- Ahn, J. et Freeman, H., « Un programme pour le placement automatique des noms », Proc. AUTO-CARTO 6, Ottawa, 1983. 444–455.
- Freeman, H., « Placement de nom d'ordinateur », ch. 29, dans Geographical Information Systems, 1, DJ Maguire, MF Goodchild et DW Rhind, John Wiley, New York, 1991, 449-460.
- Podolskaya NN Algorithmes de suppression automatique des conflits d'étiquettes pour les applications graphiques interactives. Technologies de l'information (ISSN 1684-6400), 9, 2007, p. 45-50. En russe : Подольская Н.Н. оритмы автоматического отброса формуляров для интерак тивных графических риложений. нформационные технологии, 9, 2007, с. 45-50.
- Kameda, T. et K. Imai. 2003. Placement des étiquettes de carte pour les points et les courbes. IEICE Transactions des fondamentaux de l'électronique, des communications et de l'informatique. E86A(4) : 835-840.
- Ribeiro Glaydston et Luiz Lorena. 2006. Heuristique pour les problèmes de placement d'étiquettes cartographiques. Informatique & Géosciences. 32 : 739-748.
- Wagner, F., A. Wolff, V. Kapoor et T. Strijk. 2001. Trois règles suffisent pour un bon placement d'étiquette. Algorithmique. 30:334-349.