Tester si un polygone est simple ou complexe
pour un polygone défini comme une séquence de (x,y) points, Comment puis-je détecter s'il est complexe ou non? Un polygone complexe a des intersections avec lui-même, comme montré:
y a-t-il une meilleure solution que de vérifier chaque paire qui aurait une complexité temporelle de O(N 2)?
3 réponses
il y a des méthodes de balayage qui peuvent déterminer ceci beaucoup plus rapidement qu'une approche de force brute. De plus, ils peuvent être utilisés pour briser un polygone non simple en plusieurs polygones simples.
Pour plus de détails, voir cet article, en particulier, ce code à tester pour un simple polygone.
Voir Algorithme De Bentley Ottmann pour une méthode basée sur le balayage O((N + I)log n) Pour ceci. Où N est le nombre de segments de ligne et I le nombre de points d'intersection.
en fait, cela peut être fait en temps linéaire en utilisant l'algorithme de triangulation de Chazelle. Il triangule le polygone ou trouver le polygone n'est pas simple.