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é:

example complex polygon image

y a-t-il une meilleure solution que de vérifier chaque paire qui aurait une complexité temporelle de O(N 2)?

15
demandé sur Matteo Italia 2010-10-23 03:57:52

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.

14
répondu Reed Copsey 2010-10-23 00:15:53

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.

5
répondu Amit Prakash 2015-02-09 05:26:05

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.

2
répondu Chao Xu 2015-01-17 09:28:12