Étant donné un grand nombre de sommets dans un polygone non convexe, comment puis-je trouver les bords?

StackOverflow https://stackoverflow.com/questions/2741589

Question

J'ai un ensemble de sommets (appelé A) et je veux trouver tous les sommets frontaliers tels que ce sommets aux frontières ensemble un aperçu de la forme.

Un grand nombre des sommets A sont redondants, car ils sont à l'intérieur de la forme, je veux me débarrasser de ces sommets.

Ma question est similaire à meilleur algorithme pour trouver les bords (polygone) de sommets mais je besoin de travailler pour un cas de polygone non convexe.

EDIT: Clarification: Le dessous de l'image est un polygone concave. C'est ce que je voulais dire par des non-convexe. Si je lance un algorithme de coque convexe, il ne préserverait pas la partie concave du polygone. (À moins que je ne me trompe pas).

polygone concave

J'ai un ensemble de sommets à l'intérieur et à la frontière du polygone: [[x1, y1], [x2, y2] ...] Je veux réduire l'ensemble de sorte que les sommets ne sont que les grandes lignes de bordure de la forme.

Autres conseils

Votre description est un peu vague, mais il est possible que vous êtes à la recherche de l'algorithme pour construire un Convex Hull d'un ensemble de points. En termes simples, la coque convexe est la forme que vous obtenez si vous mettez une bande de caoutchouc autour de tous les sommets.
L'écriture d'un algorithme de coque convexe en 2D est pas très difficile et il y a des bibliothèques qui le font comme qhull

(Cette réponse est également donnée dans la question que vous vous un lien vers ce qui semble être un cas particulier de votre question)

Ceci est une vieille question peut-être abandonné, mais il m'a fait penser à ce sujet. Vous n'êtes pas à la recherche d'une coque convexe, vous voulez maintenir la forme de polygones, mais juste se débarrasser des points qui se situent entre « arêtes » le long d'une ligne.

La solution pourrait consister à pas à travers des points voisins et à calculer la pente linéaire de la première et de seconde, puis en enregistrant cette valeur de pente, calculer la pente de la deuxième et de la troisième, si la pente de pt1-pt2 est égale à celle de pt2-pt3 puis pt2 est redondante en formant la ligne et peut donc être supprimée. Gardez une boucle à travers jusqu'à ce que vous retourne derrière pt1.

Cette veillerait forme concave est maintenue, mais des points supplémentaires non pertinents sont supprimés.

Le terme que vous recherchez est coque concave .

La forme la plus simple du problème n'a pas été bien défini comme enveloppe convexe, parce que le polygone concave qui couvre les points donné ne soit pas unique. Cependant, il y a beaucoup de bonnes approches.

L'un des plus simple approche est que vous utilisez l'algorithme d'emballage cadeau, mais au lieu de considérer tous les points à chaque étape que vous considérez que k -nearest voisins du sommet actuel.

Ici k est votre hyper-paramètre à régler. Si k est trop élevé, vous obtenez la coque convexe. Si k est trop faible, vous le polygone résultant a beaucoup de concavités.

Voici quelques liens connexes:

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top