Vérifier si le polygone s'auto-intersecte

Question

J'ai un objet System.Windows.Shapes.Polygon, dont la disposition est entièrement déterminée par une série de points.J'ai besoin de déterminer si ce Polygone se croise lui-même;c'est-à-dire, si l'un des côtés du polygone coupe l'un quelconque des autres côtés en un point qui n'est pas un sommet.Existe-t-il un moyen simple / rapide de calculer cela?

Answer 1

• Facile, lent, faible encombrement mémoire : comparez chaque segment avec tous les autres et vérifiez les intersections. Complexité O(n²).

• Légèrement plus rapide, empreinte mémoire moyenne (version modifiée de ci-dessus): stockez les bords dans des "buckets" spatiaux, puis exécutez l'algorithme ci-dessus sur la base de chaque bucket. Complexité O (n ² / m) pour m buckets (en supposant une distribution uniforme).

• Empreinte mémoire rapide et élevée : utilisez une fonction de hachage spatial pour diviser les bords en buckets. Vérifiez les collisions. Complexité O (n) .

• Empreinte mémoire rapide et faible : utilisez un algorithme de balayage, tel que celui décrit ici (ou ici ). Complexité O (n log n)

Le dernier est mon préféré car il a une bonne vitesse - l'équilibre de la mémoire, en particulier l ' algorithme Bentley-Ottmann . La mise en œuvre n'est pas trop compliquée non plus.

Answer 2

Vérifiez si une paire de segments de ligne non contigus se croise.

Answer 3

Par souci d'exhaustivité, j'ajoute un autre algorithme à cette discussion.

En supposant que le lecteur connaisse les boîtes englobantes alignées sur les axes (Google si ce n'est pas le cas), il peut être très efficace de trouver rapidement des paires d'arêtes qui ont la leur AABB en conflit en utilisant "l'algorithme Sweep and Prune".(recherche le sur Google).Les routines d'intersection sont alors appelées sur ces paires.

L'avantage ici est que vous pouvez même intersecter une arête non droite (cercles et splines) et l'approche est plus générale mais presque aussi efficace.