Visibilité de 2 sommets dans un simple polygone

Question

Je travaille sur une petite application avec la librairie P5 qui permet à un utilisateur de cliquer sur une toile pour créer des points et construire un polygone et je veux calculer le graphe de visibilité de ce polygone . Comment puis-je implémenter un algorithme qui peut me dire si 2 sommets sont visibles dans ce polygone? Je ne sais pas comment vérifier si une ligne entre ces 2 sommets est à l'intérieur du polygone. merci.

Answer 1

Laissez un et b être deux sommets. Vérifiez d'abord que le segment ab est localement à l'intérieur à un, et au b. C'est-à-dire qu'il tombe dans le cône déterminé par les sommets avant et après un, et b. Si oui, alors vous devez couper le segment ab avec chaque bord du polygone (sauf ceux qui concernent un et b, parce que vous venez de les vérifier).

Pour cela, vous avez besoin d'un code d'intersection de segment de segment. Vous pouvez trouver ceci partout sur le Web, y compris dans le chapitre 7 de Computational Geometry in C, et this description by Martin Thoma.