l'horizon pour un point au cours incrémental Convex Hull 3D

Question

Je suis mise en œuvre progressive CH 3D en C++ avec qt, mais je ne peux pas surmonter ce problème:

Je dois trouver le point de vue horizon d'un point donné :

J'ai une carte avec la liste de toutes les faces visibles d'un point donné « pr », mais je ne sais pas comment obtenir que l'horizon sans changer la complexité de l'algorithme (il est O (nlogn)).

Mon idée était la suivante: pour tous les bords de visages visibles, vérifiez si le visage incident du jumeau est visible ou non. Si ce n'est pas visible, ajoutez-le dans la liste des arêtes d'horizon, mais cela modifie la complexité de l'algorithme (je pense).

Notez que j'ai une autre liste où j'ai l'ensemble de tous les points qui peuvent voir un visage donné (peut-être que cela aide).

Vraiment merci à l'avance

Answer 1

Si vous avez polytopes convexes, seulement, votre idée doit le faire (Sa complexité est O (1), vous avez déjà les résultats). Oui, vous feriez une recherche supplémentaire avec la complexité O (n).