|
=> POPMUSIC+TS => | |
Le problème du placement de labels consiste à disposer des légendes autour de points en minimisant les chevauchements. Afin de faciliter l'application d'algorithmes, on limite le nombre possible de positions d'un label par rapport à son point. Le problème ainsi posé reste NP-difficile, il est donc obligatoire de recourir à des heuristiques de recherche. La méta-heuristique POPMUSIC permet de décomposer les problèmes en sous-problèmes qui seront eux-mêmes traités à l'aide d'une heuristique de recherche avec tabous.
Les résultats obtenus sont de très bonne qualité en un temps court comparativement à d'autres algorithmes comme CGA (algorithme génétique). Un petit algorithme est également mis en oeuvre sous la forme d'une deuxième passe après l'optimisation de placement qui permet de masquer les labels qui entrent en collision, un poids est assigné à chacun des labels afin de savoir lesquels masquer pour ne garder que les plus importants. Par exemple pour le placement de noms de villes sur une carte géographique le poids pourrait être le nombre d'habitants.
