Quel est le moyen le plus rapide de trouver le centre «visuel» d’un polygone de forme irrégulière?

Si vous pouvez convertir le polygone en une image binary, vous pouvez utiliser le fondement existant dans le domaine du traitement de l’image, par exemple: Un algorithme de squelette rapide sur les images binarys représentées par des blocs .

Mais ce n’est pas vraiment raisonnable dans le cas général, à cause des erreurs de discrétisation et du travail supplémentaire.

Cependant, vous trouvez peut-être ceux-ci utiles:

• Squelette droit d’un polygone simple
• Détermination du squelette d’un polygone simple en temps (presque) linéaire

EDIT: Vous voulez peut-être 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, cela donnerait probablement le résultat escompté, et ce n’est que dans des cas légèrement pathologiques, quelque chose de totalement inactif.

Avez-vous cherché à utiliser la formule centroïde?

http://en.wikipedia.org/wiki/Centroid

http://en.wikipedia.org/wiki/K-means_algorithm

J’ai trouvé une très bonne solution à partir de MapBox appelée Polylabel . La source complète est également disponible sur leur Github .

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, calculer [la solution idéale] est à la fois complexe et lent. Les solutions publiées pour résoudre le problème requièrent soit une contrainte de Delaunay Triangulation, soit le calcul d’un squelette simple en tant qu’étapes de prétraitement – les deux étant lentes et sujettes aux erreurs.

Pour notre cas d’utilisation, nous n’avons pas besoin d’une solution exacte – nous sums prêts à négocier une certaine précision pour obtenir plus de rapidité. Lorsque nous plaçons une étiquette sur une carte, il est plus important de la calculer en millisecondes que d’être mathématiquement parfait.

Une note rapide sur l’utilisation cependant. Le code source fonctionne parfaitement pour Javascript, mais si vous souhaitez l’utiliser avec un polygone “normal”, vous devez l’envelopper dans un tableau vide car les fonctions prennent des GeoJSONPolygons plutôt que des polygones normaux

var myPolygon = [[x1, y1], [x2, y2], [x3, y3]]; var center = polylabel([myPolygon]); 

Que diriez-vous:

Si le centroïde du polygone est à l’intérieur du polygone, utilisez-le, sinon:

1) Étendre une ligne du centroïde à travers le polygone en divisant le polygone en deux moitiés d’aire égale

2) Le “centre visuel” est le point situé à mi-distance 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 opposée au centroïde

Voici quelques images pour l’illustrer:

La méthode Centroid a déjà été proposée plusieurs fois. Je pense que c’est une excellente ressource qui décrit le processus (et de nombreuses autres astuces utiles avec les polygones) de manière très intuitive:

http://paulbourke.net/geometry/polygonmesh/centroid.pdf

En outre, pour placer une étiquette d’interface utilisateur simple, il suffit de calculer la boîte englobante du polygone (un rectangle défini par les coordonnées x et y les plus basses et les plus hautes de tout sumt du polygone) et de se centrer sur:

 { x = min_x + (max_x - min_x)/2, y = min_y + (max_y - min_y)/2 } 

C’est un peu plus rapide que de calculer le centroïde, ce qui peut être important 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 / centre de masse BB (relatif par exemple au premier sumt du polygone) à la structure de données de le polygone.

Calculez 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 arête. Prenez la moyenne de chaque centre dans chaque dimension. Ce sera le centre 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 est sur ce squelette. Vous pouvez par exemple choisir celui dont la distance normale est la plus courte au centre du cadre de sélection.

Que diriez-vous de trouver le “cercle” du polygone (le plus grand cercle qui s’y trouve), puis de centrer l’étiquette au centre de celui-ci? 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, probablement; un polygone qui ressemblerait à 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 point du papier auquel vous vous êtes lié (problème assez intéressant, entre autres), cette technique de “tamponnage interne” est un peu analogue à la modélisation de la forme en question à partir d’un morceau de sucre dissous par l’acide des bords (par exemple, lorsque la distance tampon augmente, la forme originale rest plus petite) Le dernier bit restant est l’endroit idéal pour placer une étiquette.

Comment accomplir cela dans un algorithme n’est malheureusement pas très clair pour moi ….

Je pense que si vous décomposiez le polygone en ses sumts, puis appliquez une fonction pour trouver la plus grande shell convexe, puis trouvez le centre au large de cette shell convexe, cela correspondrait étroitement au centre “apparent”.

Recherche de la plus grande shell convexe en fonction des sumts: Regardez sous le paragraphe Simple Polygon.

Moyenne des sumts de la shell convexe pour trouver le centre.

Pourriez-vous placer l’étiquette au centre naïf (de la boîte englobante, peut-être), puis le déplacer en fonction des intersections des arêtes des polygones locaux et du BB de l’étiquette? Déplacez-vous le long des normales des arêtes qui se croisent et, si plusieurs arêtes se coupent, additionnez leurs normales pour le mouvement?

Juste deviner ici; Dans ce type de problème, j’essaierais probablement de résoudre itérativement tant que la performance ne pose pas trop de problèmes.

Pas beaucoup de temps pour élaborer ou tester cela maintenant, mais je vais essayer de faire plus quand j’ai une chance.

Utilisez les centroïdes comme méthode principale. Tester pour voir si le centroïde est dans le polygone; sinon, tracez une ligne à travers le point le plus proche et de l’autre côté du polygone. Au milieu de la section de cette ligne située dans le polygone, placez votre étiquette.

Parce que le point le plus proche du centroïde est susceptible de délimiter une assez grande surface, je pense que cela pourrait donner des résultats similaires à ceux de Kyralessa. Bien sûr, cela pourrait devenir fou si vous aviez un polygone avec des trous. Dans ce cas, les encres seraient probablement bien mieux. Par contre, il utilise par défaut la méthode centroïde (rapide?) Pour 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 en génie civil, voici un lien utile de wikipedia:

http://en.wikipedia.org/wiki/Center_of_mass