Comment traduire les marqueurs en demi-cercle avec une intersection de ligne minimale?

Question

J'ai une carte et beaucoup de marqueurs y sont affichés. Parfois, les marqueurs sont si proches les uns des autres qu'ils se chevauchent. Pour remédier à cela, j'ai mis en place une bibliothèque spiderfier pour remédier à cette situation.

L'idée est de grouper les marqueurs de façon assez rapprochée vers le haut sur l'écran (vers le bas mathématiquement) de telle sorte qu'ils ne se croisent pas les uns les autres.

Les marqueurs sont affichés sous la forme de rectangles.

mise en œuvre:

• traverse les marqueurs et les marqueurs qui se coupent, les autres sont inclus dans un groupe avec le centre de ((minX + maxX)/2, maxY) et le rayon est juste suffisamment grande pour afficher les marqueurs à la périphérie sans se croiser chaque-autre
• alors qu'il ya des demi-cercles qui se croisent chaque-autre, nous les fusionner en un plus grand demi-cercle
• nous trions les marqueurs par un comparateur, en plaçant « plus petit "marqueurs à gauche sur la périphérie du cercle par rapport à leurs homologues" plus grands "
• nous affichons les marqueurs sur le cercle de la moitié supérieure, mais nous affichons une ligne de leur emplacement modifié leur emplacement réel

Jusqu'à présent, si bon. Problème: Ces lignes se croisent trop souvent et nous avons besoin d'une fonction de comparaison avec laquelle le nombre d'intersection de lignes de repère est minimisé.

Essais:

1. P1.x < = P2.x => P1 = P2 <

2. arctan ((P1.y - Cy)/(R * (P1.x - cx))) < = arctan ((P2.y - Cy)/(R * (P2.x - cx))) => P1 = P2 <

Je attendais attaché à la deuxième tentative , mais a dû reconnaître que ce n'est pas un bon dea, puisque la ligne de translation et la ligne entre la position réelle et le centre du cercle ne sont pas nécessairement colinéaires, en fait leur angle peut devenir assez grand s'il y a beaucoup de marqueurs ayant leur position réelle très proche les uns des autres, la surface du demi-cercle, sauf cette sous-région, est assez stérile. Donc, cela conduit à des intersections aussi bien et c'est beaucoup plus complexe que le premier essai. Je crois que le Math.atan de Javascript est implémenté soit avec Taylor series soit Fourier series, ce qui implique des dérivées dans le premier cas et intégrées dans le second cas. Ou, il pourrait y avoir une troisième approche, qui est aussi très complexe. Je penserais à des optimisations et à d'autres choses du genre si cette deuxième approche avait réduit de façon significative le nombre d'intersections, mais comme l'amélioration est à peine observable, je suis revenue à la première approche.

Je pense à l'approche suivante:

• calculer l'emplacement des emplacements de marquage sur la tentative périphérie
• pour traduire tous les marqueurs à leur plus proche emplacement possible
• trouver les groupes en conflit et résoudre tous les conflits en trouvant l'optimum, qui est la traduction-ensemble avec la plus petite traduction totale

Cette idée conduisant à un état où s Le nombre d'intersection de la ligne de conduite est minimal et, dans la négative, comment pourrais-je minimiser le nombre de ces intersections?

Answer 1

Ceci est un problème difficile, étudié depuis longtemps maintenant. Il est parfois appelé automatic label placement. Le travail cité ci-dessous est typique de ce qui est disponible dans la littérature.

---

---

Van Kreveld, Marc, Tycho Strijk et Alexander Wolff. "Étiquetage à points avec étiquettes coulissantes." Actes du quatorzième symposium annuel sur la géométrie algorithmique. ACM, 1998. ACM link.