Algorithme de placement des étiquettes? (de préférence en JavaScript)
j'aimerais placer automatiquement de 100 à 200 étiquettes à bulles pour que les exigences suivantes soient respectées:
- les étiquettes ne doivent pas se chevaucher
- de préférence, les étiquettes ne doivent pas chevaucher les bulles L'étiquette
- doit être proche de la bulle
- Position préférée de l'étiquette (haut à gauche, haut, bas, droite, etc.) devraient être respectées dans une certaine mesure
- font-size peut varier
y a-t-il des bibliothèques / algorithmes utiles pour cela? (de préférence JavaScript ou PHP)
(l'emplacement de l'étiquette dans l'image ne répond pas à ces exigences)
9 réponses
Cela peut être formulé comme un problème de Programmation Linéaire. Vous souhaitez maximiser ou minimiser une fonction (représentant le "poids" ou la "bonté" de la solution) sous réserve de certaines contraintes (vos exigences). Vous aurez besoin de formaliser vos exigences en tant que valeurs. Quelque chose comme ceci:
Variables:
x1 = 1 if Labels overlap, 0 otherwise
x2 = some measure of "how much" a label overlaps a bubble
x3 = distance from label to bubble //Label should be close to bubble
x4 = distance between ideal and actual label position
x5 = difference between actual and ideal font size
minimize x1 + 10*x2 + x3 + 20*x4 + 5*x5
subject to constraints:
x1 = 0 // labels can never overlap
x2 < /* maximum amount a label is allowed to overlap a bubble */
...
x5 < 6 // font size does not vary by more than +/- 6 pts.
j'ai fait les coefficients et les contraintes, vous pouvez les utiliser pour régler le résultat basé sur les caractéristiques qui sont les plus importants pour vous. Augmentation des Coefficients la valeur d'une exigence (dans ce cas, f4 est la plus pondérée de sorte qu'elle "est la plus importante". Les contraintes sont des limites dures qui ne peuvent être violées.
Puisqu'il s'agit d'un problème bien connu, vous pouvez maintenant le résoudre en utilisant un certain nombre de méthodes. L'algorithme du Simplexe est populaire. Il y a tout un chapitre dans Cormen et. al sur ces problèmes.
j'imagine que vous travaillez avec javascript, html et css? Bien, en tout cas, deux approches viennent à l'esprit.
est d'abord formulé comme un problème d'optimisation. Vous devez calculer la position idéale pour chaque étiquette. Cela dépendra de la taille de la bulle, de l'emplacement désiré (c.-à-d. Haut, Bas, Gauche, Droite) et de la taille de l'étiquette (à la fois la police et la longueur). Ensuite, vous devez paramétrer vos coordonnées, par exemple dans une liste D'éléments 2N où N est le nombre d'étiquettes. Ensuite, vous devez initialiser les étiquettes dans une certaine position (ou une population si vous utilisez un algorithme génétique) et appliquer un algorithme d'optimisation qui nécessitera une fonction de coût. Cela serait basé sur la distance entre un ensemble de positions d'étiquette sont de l'idéal, ainsi que tout ce qui viole vos règles, telles que le chevauchement.
ou, en faire un problème de physique. "Attacher" chaque étiquette à sa bulle avec un lien rigide. Donner à chaque étiquette et chaque bulle un force de répulsion et aussi ajouter une force de gravitation globale et plus forte (en haut/gauche/droite/vers le bas). Avoir une simulation physique courte jusqu'à ce que vous atteignez un équilibre. Les mathématiques ne devrait pas être trop dur.
je pense que si vous utilisez D3 dans vos outils, vous pouvez utiliser l'algorithme de placement d'étiquette" basé sur la force". La solution appartient à l'origine à Max Planck Research Networks mais il existe déjà un exemple Javascript prêt à l'emploi, ici: placement d'étiquette basé sur la Force dans D3
malheureusement, je pense qu'il va être difficile de trouver cette solution facilement disponible en Javascript ou PHP. Mais, je pense que votre problème peut être décomposé en petits sous-problèmes (basés sur vos règles) pour vous aider à concevoir votre solution.
j'identifierais les règles les plus importantes. D'après l'apparence du graphique que vous avez fourni, je dirais que la règle #1 et #2 apporterait la plus grande amélioration de lisibilité.
à déterminer le placement selon ces règles, je calculerais les conteneurs limites du texte et des bulles et tester pour l'intersection. À l'intersection, se déplacer à un endroit sans intersection. Si vous ne pouvez pas en trouver un, utilisez un espace avec un minimum de chevauchement.
cela vous permettrait également de créer un heuristique de placement pondéré pour haut-gauche, bas-droite, etc, pour aider à placer les étiquettes dans les endroits" préférés".
j'essaierais d'écrire un petit morceau de l'algorithme de placement en utilisant deux bulles avec deux étiquettes qui sont généralement proches et pourraient se chevaucher. Si vous pouvez généraliser votre algorithme de placement pour travailler pour ce petit sous-ensemble, vous devriez être bon aller de l'avant avec plus de bulles.
aussi, peut-être pourriez-vous utiliser quelque chose sur l'ordre d'un arbre de KD ou une autre structure de données de partitionnement de l'espace pour localiser les voisins les plus proches à éviter.
j'ai trouvé une approche en Java réellement pour ce problème qui fonctionne réellement et s'appelle Force Directed Map Labeling et est une expérience open-source academy.
Voici la documentation + le code source du projet: étiquetage cartographique forcé
Que Diriez-vous de
de l'étiquette.substring (0, Math.sqrt (bubbleValueOrRadius))
j'ai trouvé ça dans un protovis.js exemples.
Ce fil est très bon dans la couverture de certaines approches. J'utilise la disposition de la force avec plusieurs foyers, car elle semble être la meilleure méthode globale.