Algorithme de placement d'étiquette de graphique à bulles? (de préférence en JavaScript)

Question

J'aimerais placer automatiquement 100-200 bulle étiquettes de sorte que les conditions suivantes sont remplies:

• Les étiquettes ne doivent pas se chevaucher
• Les étiquettes devraient, de préférence, ne pas chevaucher les bulles
• L'étiquette doit être proche de la bulle
• Préféré position de l'étiquette (en haut à gauche, en haut, en bas, à droite, etc.) devraient être respectés dans une certaine mesure
• Taille de police peut varier

Sont-il utile de bibliothèques / algorithmes pour cela? (de préférence, JavaScript ou PHP)

(L'étiquette de placement dans l'image ne remplit pas ces conditions)

Answer 1

Que dis-tu de ça?

Un algorithme efficace pour l'étiquetage des graphiques à nuage de points

Answer 2

J'imagine que vous travaillez avec javascript, html et css? Bien, en tout cas, deux approches viennent à l'esprit.

La première est de formuler comme un problème d'optimisation. Vous avez besoin de calculer la position idéale pour chaque étiquette. Ce sera basé sur la taille de la bulle, l'emplacement souhaité (c'est à dire en haut, bas, gauche, droite), et la taille de l'étiquette (à la fois de la police et de la longueur). Ensuite, vous devez paramétrer vos coordonnées, par exemple dans une liste de 2N éléments, où N est le nombre d'étiquettes. Ensuite, vous devez initialiser les étiquettes dans une certaine position (ou d'une population si à l'aide d'un algorithme génétique) et d'appliquer un algorithme d'optimisation qui aura besoin d'une fonction de coût. Ce serait basé sur un ensemble de positions de labels sont de l'idéal, ainsi que tout ce qui porte atteinte à vos règles, comme le chevauchement.

Ou, en font un problème de physique. "Attacher" chaque étiquette de sa bulle avec certains lien rigide. Donner à chaque étiquette et chaque bulle une force de répulsion et également ajouter un mondial et de la plus forte graviational de la force (dans le préféré le haut/la gauche/la droite/vers le bas). Un court simulation physique jusqu'à ce que vous atteindre un équilibre. Les mathématiques ne devrait pas être trop dur.

Answer 3

Je pense que si vous utilisez D3 dans vos outils, vous pouvez utiliser un 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

Answer 4

Cela peut être formulé comme un problème de Programmation Linéaire. Vous voulez maximiser ou minimiser une fonction (représentant le "poids" ou de la "bonté" de la solution), sous réserve de certaines contraintes (vos besoins). Vous aurez besoin de formaliser vos besoins 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. Les Coefficients de l'augmentation de la valeur d'une obligation (dans ce cas, f4 est pondéré en plus de sorte qu'il est 'le plus important". Les contraintes sont difficiles limites qui ne peuvent être violés.

Puisque c'est un problème bien connu, vous pouvez maintenant le résoudre à l'aide d'un certain nombre de méthodes. L'algorithme du Simplexe est populaire. Il y a un chapitre entier de Cormen et. al sur ces problèmes.

Answer 5

Peut-être jouer avec des boîtes à outils d'aide comme les suivantes:

• protovis
• d3