Quel est le moyen le plus rapide de rechercher le & # 8220; visuel & # 8221; centre d'un polygone de forme irrégulière?
https://stackoverflow.com/questions/1203135
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je dois trouver un point qui est le centre visuel d'un polygone de forme irrégulière. Par centre visuel, j'entends un point qui apparaît visuellement au centre d'une grande zone du polygone. L’application consiste à placer une étiquette à l’intérieur du polygone.
Voici une solution qui utilise la mise en mémoire tampon interne:
Si cela doit être utilisé, quel est un moyen efficace et rapide de trouver le tampon? Si un autre moyen doit être utilisé, lequel est-ce ainsi?
Un bon exemple de polygones vraiment difficiles est un U épais et géant (écrit en Arial Black ou Impact ou dans une police similaire).
La solution
Si vous pouvez convertir le polygone en une image binaire, vous pouvez utiliser la base existante dans le domaine du traitement d'image, par exemple: Un algorithme de squelette rapide sur les images binaires représentées par blocs .
Mais ce n’est pas vraiment raisonnable dans le cas général, à cause d’erreurs de discrétisation et de travail supplémentaire.
Cependant, vous trouverez peut-être ces informations utiles:
- Squelette droit d'un simple polygone
- Détermination de la Squelette d'un polygone simple en temps (presque) linéaire
EDIT: Peut-être voudrez-vous rechercher le point qui est le centre du plus grand cercle contenu dans le polygone. Ce n’est pas nécessairement toujours dans le centre observé, mais la plupart du temps donnerait probablement le résultat escompté, et seulement dans les cas légèrement pathologiques, quelque chose qui est totalement inacceptable.
Autres conseils
J'ai trouvé à MapBox une très bonne solution appelée Polylabel . Le code source complet est disponible sur leur Github également.
Essentiellement, il essaie de trouver le centre visuel du polygone, comme l’a dit T Austin.
Certains détails suggèrent que cela pourrait être une solution pratique:
Malheureusement, le calcul de [la solution idéale] est complexe et lent. Les solutions publiées au problème requièrent soit Triangulation de Delaunay contrainte ou calcul d’un squelette droit comme étapes de prétraitement, lentes et sujettes aux erreurs.
Pour notre cas d'utilisation, nous n'avons pas besoin d'une solution exacte - nous sommes prêts à échanger de la précision pour obtenir plus de vitesse. Lorsque nous plaçons une étiquette sur carte, il est plus important qu’elle soit calculée en millisecondes plutôt que être mathématiquement parfait.
Une note rapide sur l'utilisation cependant. Le code source fonctionne très bien pour Javascript prêt à l'emploi si vous avez l'intention de l'utiliser avec un " normal " polygone, vous devez alors l’envelopper dans un tableau vide car les fonctions ici prennent GeoJSONPolygons plutôt que d'habitude polygones c'est-à-dire
var myPolygon = [[x1, y1], [x2, y2], [x3, y3]];
var center = polylabel([myPolygon]);
Avez-vous envisagé d'utiliser la formule du centre de gravité?
Que diriez-vous de:
Si le centre de gravité du polygone est à l'intérieur du polygone, utilisez-le, sinon:
1) Étendez une ligne allant du centre de la droite au polygone divisant le polygone en deux moitiés d'égale surface
2) Le & centre; centre visuel " est le point situé à mi-chemin entre le point le plus proche où la ligne touche le périmètre et le point suivant coupant le périmètre dans la direction qui s’éloigne du centroïde
Voici quelques images pour l'illustrer:
Calcule la position centrale (x, y) de chaque bord du polygone. Vous pouvez le faire en trouvant la différence entre les positions des extrémités de chaque bord. Prendre la moyenne de chaque centre dans chaque dimension. Ce sera le centre du polygone.
La méthode centroïde a déjà été suggérée plusieurs fois. Je pense que c'est une excellente ressource qui décrit le processus (et bien d'autres astuces utiles avec des polygones) de manière très intuitive:
http://paulbourke.net/geometry/polygonmesh/centroid.pdf
De même, pour placer une étiquette d'interface utilisateur simple, il peut suffire de calculer le cadre de sélection du polygone (un rectangle défini par les coordonnées x et y les plus basses et les plus hautes de tout sommet du polygone), et d'obtenir son centre. à:
{
x = min_x + (max_x - min_x)/2,
y = min_y + (max_y - min_y)/2
}
Cela est un peu plus rapide que de calculer le centroïde, ce qui peut être significatif pour une application en temps réel ou intégrée.
Notez également que si vos polygones sont statiques (ils ne changent pas de forme), vous pouvez optimiser en enregistrant le résultat du calcul du centre de gravité / centre de gravité BB (relatif au premier sommet du polygone, par exemple). structure de données du polygone.
Je ne dis pas que c'est le plus rapide, mais cela vous donnera un point à l'intérieur du polygone. Calculez le squelette droit . Le point que vous recherchez se trouve sur ce squelette. Vous pouvez, par exemple, choisir celui qui a la distance normale la plus courte au centre du cadre de sélection.
Que diriez-vous de trouver le "cercle encerclé"? du polygone (le plus grand cercle à l'intérieur), puis centrer l'étiquette au centre? Voici quelques liens pour vous aider à démarrer:
http://www.mathopenref.com/polygonincircle.html
https://nrich.maths.org/discus/messages/145082/ 144373.html? 1219439473
Cela ne fonctionnera pas parfaitement sur tous les polygones. un polygone ressemblant à un C aurait l'étiquette à un endroit quelque peu imprévisible. Mais l’avantage serait que l’étiquette chevaucherait toujours une partie solide du polygone.
Si je comprends le sens de l'article auquel vous avez fait référence (problème assez intéressant, d'ailleurs), cette "mise en mémoire tampon à l'intérieur" & Cette technique est quelque peu analogue à la modélisation de la forme en question à partir d’un morceau de sucre dissous par l’acide des bords à placez une étiquette.
Malheureusement, comment y parvenir dans un algorithme n'est pas très clair pour moi ....
Je pense que si vous fracturiez le polygone en ses sommets, puis appliquiez une fonction pour trouver la plus grande coque convexe, puis le centre de cette coque convexe, elle correspondrait étroitement au signe "apparent". centre.
Recherche de la plus grande coque convexe en fonction des sommets: Recherchez le paragraphe Polygon simple.
Faites la moyenne des sommets de la coque convexe pour trouver le centre.
Pouvez-vous placer l’étiquette au centre naïf (peut-être dans le cadre de sélection), puis la déplacer en fonction des intersections des arêtes du polygone local et du BB de l’étiquette? Déplacez-vous le long des normales des angles qui se croisent et, si plusieurs arêtes se croisent, additionnez leurs normales pour obtenir un mouvement?
Devinez juste ici; dans ce genre de problème, j'essaierais probablement de résoudre le problème de manière itérative tant que les performances ne sont pas trop préoccupantes.
Pas beaucoup de temps pour élaborer ou tester ceci maintenant, mais j'essaierai d'en faire plus quand j'en aurai l'occasion.
Utilisez les centroïdes comme méthode principale. Testez pour voir si le centre de gravité est dans le polygone; sinon, tracez une ligne à travers le point le plus proche et sur l’autre côté du polygone. Au milieu de la section de cette ligne située dans le polygone, placez votre étiquette.
Etant donné que le point le plus proche du centre de la centroïde est susceptible de lier une zone assez grande, je pense que cela pourrait donner des résultats similaires à ceux des incircles de Kyralessa. Bien sûr, cela pourrait devenir fou si vous aviez un polygone troué. Dans ce cas, les incircles seraient probablement beaucoup mieux. Par ailleurs, il utilise par défaut la méthode (rapide?) Centroïde dans les cas typiques.
Ce problème serait probablement analogue à la recherche du "centre de masse". en supposant une densité uniforme.
EDIT: cette méthode ne fonctionnera pas si le polygone a des "trous"
vous pouvez utiliser la méthode du centre de gravité (ou centre de gravité) utilisée dans le génie civil, voici un lien utile de wikipedia:
