Tester si un polygone est simple ou complexe
Pour un polygone défini comme une séquence de (x,y) de points, comment puis-je détecter si c'est complexe ou pas? Un polygone complexe a des intersections avec lui-même, comme l'a montré:
Est-il une meilleure solution que la vérification de chaque paire, qui aurait une complexité temporelle en O(N2)?
source d'informationauteur Drew Noakes
Vous devez vous connecter pour publier un commentaire.
Il y a de balayage des méthodes qui peuvent déterminer beaucoup plus vite qu'une approche par force brute. En outre, ils peuvent être utilisés pour briser un non simple polygone en plusieurs polygones simples.
Pour plus de détails, voir cet articleen particulier, cette le code de test pour un simple polygone.
Voir Bentley Ottmann Algorithme pour un balayage en fonction O((N + I)log N) méthode pour cela.
Où N est le nombre de segments de ligne et je est le nombre de points d'intersection.
En fait, ce qui peut être fait en temps linéaire utiliser Chazelle de l'algorithme de triangulation. Il triangule le polygone ou trouver le polygone n'est pas simple.