Supposons qu'il existe un polygone sans trous et auto-intersections (c'est-à-dire un simple polygone) défini par J'aimerais trouver tout autre sommet Y a-t-il un algorithme pour le faire dans Une recherche rapide suggère que pour un polygone donné et tout point à l'intérieur de ce polygone a Visibilité Polygone peut être construit dans n sommets. Choisissez un Reflex Vertex V de ce polygone.
u du même polygone qui est "visible" à partir du sommet v . Par visible, je veux dire, qu'un segment de ligne entre v et u est complètement à l'intérieur du polygone.
O (n) heure ou mieux? Existe-t-il un algorithme qui peut trouver tous les sommets visibles dans O (n) temps?
o (n) . Je suppose que la recherche d'un seul sommet visible devrait être encore plus facile.
5 Réponses :
Vous pouvez tester tout sommet individuel dans O (n) temps, et c'est donc tester tous les sommets dans o (n ^ 2) . Pour tester tout si un sommet individuel En outre, vous pouvez tester si l se trouve dans le polygone, comme: supposons que les arêtes d'incident sur Soyez prudent avec vos tests d'intersection, comme L intersectez trivialement les bords de polygones incident à Également, si
Que tu devrais choisir? Votre algorithme est O (n ^ 2).
Sûrement, vous devez également vérifier que l mensonges à l'intérieur le polygone
Et vous devriez choisir le premier U qui passe le test.
OK, mais après le modifier, c'est toujours O (n ^ 2). Je ne suis intéressé que par l'algorithme O (n).
Assez juste! Si je pense à quelque chose, je vous le ferai savoir. Est-il possible pour vous de pré-traiter le polygone de quelque manière que ce soit? Aussi, à l'instar de combien de sommets ces polygones ont-ils?
Oui, je peux le prétraiter, mais je peux passer au plus de temps O (n log (n)) à ce sujet.
Vous pouvez utiliser une triangulation du polygone.
supposant que vous avez une triangulation Notez que ce n'est pas nécessairement tous les sommets visibles de Bien sûr, vous auriez besoin de construire une triangulation en premier. Il existe des algorithmes efficaces qui permettent une triangulation de Delaunay contrainte d'être intégrée dans t , un ensemble de sommets visibles u pour un vertex v pourrait être trouvé en examinant les bords internes associés dans la triangulation. Spécifiquement, si l'ensemble de triangles attachés à V est traversé et que les bords internes identifiés (ceux qui apparaissent deux fois!), Le jeu u est tous des sommets de bord sauf V .
V , juste un ensemble avec | u | > = 0 (doit être au moins un bord interne de V) . Il est efficace, cependant - seulement O (m) où m est le nombre de triangles / bords visités, ce qui est essentiellement O (1) pour intrants raisonnables.
O (n * journal (n)) , mais ce n'est pas tout à fait O (n) . De bonnes implémentations de Delaunay contraint peuvent être trouvées dans Triangle et CGAL .
Merci. Une réponse valide, mais je préférerais ne pas la mettre en œuvre de cette façon. La mise en œuvre de l'algorithme de triangulation dans O (n * journal (n)) n'est pas triviale.
Il suffit de continuer à aller dans une certaine direction à travers des sommets à partir de V et de la liste de mise à jour des sommets visibles. Si je ne manquais rien, ce sera O (n).
Pour simplicité, appelons V visible.
J'ai essayé pendant une journée de la mettre en mots, a échoué et utilisé pseudo -code :)
J'ai modifié l'algorithme telle qu'elle était incorrecte. J'espère que cette fois-ci couvre tous les cas! a - a ' dans le côté a' , laissez b le point d'intersection de ce bord avec la ligne a-- a ' et c le point final du bord (celui à droite de a - C ). maintenant continue Passez à travers les bords du polygone, et si un bord traverse le segment a - b de gauche à droite puis réglez b au nouveau point d'intersection et C au sommet final. Lorsque vous avez fini, nous avons un triangle A - B - C . Maintenant, recommencez à partir de c regarder chaque sommet pour voir s'il se trouve à l'intérieur du triangle a - b - c et dans ce cas jeu c au nouveau sommet. À la fin a - c est une diagonale du polygone. Voici une implémentation en C qui suppose que le point réflexe a est dans p [0] :
Cela semble presque fonctionner. Mais il y a un problème lorsque le polygone est trop collé (polygone en spirale), le premier sommet trouvé C ne serait pas trouvé correctement. Aussi le chèque si un d est à l'intérieur d'un triangle peut être insuffisant, car il peut bloquer la visibilité de C même si ce n'est pas dans le triangle.
Ce problème a été résolu il y a 30 ans:
elgindy et avis, "un algorithme linéaire pour calculer le polygone de visibilité à partir d'un point", j. Algorithmes 2 , 1981, p. 186--197.
Il y a un très beau papier de Joe & Simpson, 1985, "Visibilité d'un simple polygone d'un point", offre un pseudocode soigneusement vérifié: ( lien de téléchargement PDF ). Cela a sûrement été mis en œuvre à plusieurs reprises depuis, dans de nombreuses langues. Par exemple, il existe un lien avec L'article Wikipedia sur le sujet .
Si quelqu'un est intéressé par une implémentation de l'algorithme de Joe et Simpson, voir Ce .
Eh bien, il y a le Partition d'espace binaire . Il permet une visibilité des chèques de visibilité dans O (n), mais a une configuration beaucoup plus compliquée, il ne serait donc que bon pour vous si vous vérifiez le même polygone, et je suppose que vous n'êtes pas ...
@Xavierholt: En fait, je ferai cette recherche plusieurs fois pour différents sommets V, donc une configuration qui se trouve au plus O (n * journal n) est ok. Mais un chèque O (n) n'est probablement pas suffisant. Je pouvais faire une vérification O (n) sans aucune structure de données simplement en itérant tous les bords du polygone.