Meilleur algorithme pour trouver les arêtes (polygones) des sommets

Question

J'ai un grand nombre de sommets, dont certains sont des arêtes, d'autres sont redondants (dans la forme) et je souhaite les supprimer.

L’algorithme le plus simple auquel je puisse penser est de vérifier un par un s’ils heurtent la forme formée par les autres. Mais cela devrait être un algorithme très lent.

J'ai pensé en choisir un à partir du bord (le plus éloigné de l'origine par exemple) et calculer le chemin le plus long à partir de ce début ... devrait obtenir le chemin du bord, n'est-ce pas?

Des suggestions?

Answer 1

Le problème avec les algorithmes polyédriques est de choisir celui qui correspond à votre entrée et à votre sortie désirée, car il existe plus d’une façon de représenter un polyèdre et la conversion entre les représentations peut être coûteuse. Dans ce cas, vous commencez avec des points et souhaitez terminer par des sommets. L'algorithme analyse Graham pour calculer les sommets de la coque convexe devrait faire l'affaire, bien que des efforts supplémentaires puissent être nécessaires pour les prolonger il a passé le cas 2-D. C’est O ( n log n ) dans le nombre de sommets en entrée.

Answer 2

Je ne sais pas quel est le meilleur algorithme pour trouver ce polygone, mais le polygone que vous recherchez s'appelle & "Convex Hull &";.

.

En recherchant cela, vous devriez trouver un algorithme de correspondance.

Answer 3

La coque convexe est l’un des problèmes les plus étudiés de la géométrie numérique. Le Graham Scan est l’un des algorithmes plus simples, mais certainement pas le seul. L'algorithme d'emballage de cadeau , également appelé Marche de Jarvis, est le plus simple que je connaisse. Le référentiel d'algorithmes Stony Brook comporte plusieurs implémentations de coque convexe algorithmes en C et C ++. La géométrie en action montre principalement les applications des coques convexes. Voici une collection de de faible dimension et programmes de calcul de coque convexe de dimensions arbitraires.