20 février 2019

Détecter si un point est à l'intérieur d'un polygone convexe

Explications sur un polygone convexe
{\displaystyle {\begin{vmatrix}a&b\\c&d\end{vmatrix}}=ad-bc}
On vérifie que le point est toujours à gauche (résultat négatif du déterminant si l'on parcourt le polygone dans le sens radial) de chacune des droites formées par les arrêtes.

Cet algorithme est bien plus performant que ceux donnés sur les liens ci-dessous, et plus pratique car nous pouvons facilement savoir si un point est sur une arrête (D = 0 -> 1 fois) ou un sommet (D = 0 -> 2 fois)

https://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/
https://www.geeksforgeeks.org/check-whether-a-given-point-lies-inside-a-triangle-or-not/