Un algorithme simple pour l’intersection des polygones

Je cherche un algorithme très simple pour calculer l’intersection / l’écrêtage des polygones. Autrement dit, étant donné les polygones P , Q , je souhaite trouver le polygone T qui est contenu dans P et dans Q , et je souhaite que T soit maximal parmi tous les polygones possibles.

Je ne me soucie pas du temps d’exécution (j’ai quelques très petits polygones), je peux aussi me permettre d’obtenir une approximation de l’intersection des polygones (c’est-à-dire un polygone avec moins de points, mais qui est toujours contenu dans l’intersection des polygones) ).

Mais il est vraiment important pour moi que l’algorithme soit simple (test moins coûteux) et de préférence court (moins de code).

edit: veuillez noter que je souhaite obtenir un polygone qui représente l’intersection. Je n’ai pas seulement besoin d’une réponse booléenne à la question de savoir si les deux polygones se croisent.

Je comprends que l’affiche originale cherchait une solution simple, mais malheureusement, il n’y a pas vraiment de solution simple.

Néanmoins, j’ai récemment créé une bibliothèque de découpage freeware open-source (écrite en Delphi, C ++ et C #) qui découpe tous les types de polygones (y compris ceux qui s’entrecroisent). Cette bibliothèque est assez simple à utiliser: http://sourceforge.net/projects/polyclipping/ .

Vous pouvez utiliser un algorithme Polygon Clipping pour trouver l’intersection entre deux polygones. Cependant, ces algorithmes ont tendance à être compliqués lorsque tous les cas extrêmes sont pris en compte.

Weiler-Atherton est une implémentation du découpage de polygones que vous pouvez utiliser avec votre moteur de recherche préféré. article de wikipedia sur Weiler-Atherton

Alan Murta a une implémentation complète d’un GPC clipper de polygones.

Modifier:

Une autre approche consiste à diviser d’abord chaque polygone en un ensemble de sortingangles plus faciles à traiter. Le théorème des deux oreilles de Gary H. Meisters fait l’affaire. Cette page de McGill explique bien la subdivision en sortingangle.

Si vous utilisez C ++ et que vous ne voulez pas créer l’algorithme vous-même, vous pouvez utiliser Boost.Geometry . Il utilise une version adaptée de l’algorithme de Weiler-Atherton mentionné ci-dessus.

Vous ne nous avez pas donné votre représentation d’un polygone. Donc, je choisis (plutôt comme suggérant) un pour vous 🙂

Représente chaque polygone comme un grand polygone convexe et une liste de plus petits polygones convexes à soustraire de ce grand polygone convexe.

Maintenant, avec deux polygones dans cette représentation, vous pouvez calculer l’intersection comme suit:

Calculer l’intersection des grands polygones convexes pour former le grand polygone de l’intersection. Ensuite, soustrayez les intersections de tous les plus petits pour obtenir une liste des polygones sous-traités.

Vous obtenez un nouveau polygone suivant la même représentation.

Puisque l’intersection des polygones convexes est facile, cette recherche d’intersection devrait également être facile.

Cela semble fonctionner, mais je n’ai pas approfondi mes reflections sur la justesse / la complexité temps / espace.

Voici une approche basée sur la sortingangulation qui est assez simple à mettre en œuvre et qui peut être exécutée dans O (N 2 ).

BTW, O (N 2 ) est optimal pour ce problème. Imaginez deux polygones en forme de lames de fourche se croisant à angle droit. Chacun a un nombre de segments proportionnel au nombre de dents; le nombre de polygones dans l’intersection est proportionnel au carré du nombre de dents.

  1. D’abord, sortingangulez chaque polygone.

  2. Comparez tous les sortingangles de P par paire avec tous les sortingangles de Q pour détecter les intersections. Toute paire de sortingangles qui se croisent peut être divisée en plus petits sortingangles, chacun étant en P, en Q ou dans l’intersection. (Tout ce que vous avez utilisé à l’étape 1 peut être réutilisé pour vous aider.) Ne conservez que les sortingangles qui se trouvent dans l’intersection.

  3. Calculez les voisins de chaque sortingangle en les comparant par paires et construisez un graphe d’adjacence. Ce graphique contiendra un sous-graphe connecté pour chaque polygone à l’intersection de P et Q.

  4. Pour chacun de ces sous-graphes, choisissez un sortingangle, avancez jusqu’au bord, puis faites le tour du bord pour produire les segments délimitant le polygone de sortie correspondant.

Voici une approche simple et stupide: en entrée, discrétisez vos polygones en bitmap. Pour se croiser, et les bitmaps ensemble. Pour produire des polygones de sortie, tracez les bordures irrégulières du bitmap et lissez les jaggies à l’aide d’un algorithme d’approximation de polygone . (Je ne me souviens pas si ce lien fournit les algorithmes les plus appropriés, ce n’est que le premier hit Google. Vous pouvez consulter l’un des outils pour convertir les images bitmap en représentations vectorielles. Vous pouvez peut-être les appeler sans réimplémenter l’algorithme ?)

Je pense que la partie la plus complexe serait de tracer les frontières .

Au début des années 90, je faisais face à quelque chose comme ce problème au travail. Je l’ai étouffé: je suis arrivé avec un algorithme (complètement différent) qui fonctionnerait sur des coordonnées en nombres réels, mais qui semblait se heurter à une pléthore de cas dégénérés, totalement impossibles à résoudre, face à la réalité des entrées en virgule flottante (et bruyantes). . Peut-être qu’avec l’aide d’Internet, j’aurais fait mieux!

Je n’ai pas de solution très simple, mais voici les principales étapes pour le véritable algorithme:

  1. Effectuez une double liste chaînée personnalisée pour les sumts et les arêtes des polygones. Utiliser std::list ne fonctionnera pas car vous devez permuter les pointeurs / décalages suivants et précédents pour une opération spéciale sur les nœuds. C’est le seul moyen d’avoir du code simple, et cela donnera de bonnes performances.
  2. Trouvez les points d’intersection en comparant chaque paire d’arêtes. Notez que la comparaison de chaque paire d’arête donnera le temps O (N²), mais l’amélioration de l’algorithme à O (N · logN) sera facile par la suite. Pour certaines paires d’arêtes (disons a → b et c → d), le point d’intersection est trouvé en utilisant le paramètre (de 0 à 1) sur l’arête a → b, qui est donné par tₐ = d₀ / (d₀-d₁) , où d₀ est (ca) × (ba) et d₁ est (da) × (ba). × est le produit en croix 2D tel que p × q = pₓ · qᵧ-pᵧ · qₓ. Après avoir trouvé tₐ, trouver le point d’intersection en fait un paramètre d’interpolation linéaire sur le segment a → b: P = a + tₐ (ba)
  3. Divisez chaque arête en ajoutant des sumts (et des noeuds dans votre liste chaînée) où les segments se recoupent.
  4. Ensuite, vous devez traverser les nœuds aux points d’intersection. Il s’agit de l’opération pour laquelle vous devez effectuer une double liste chaînée personnalisée. Vous devez échanger une paire de pointeurs suivants (et mettre à jour les pointeurs précédents en conséquence).

Ensuite, vous avez le résultat brut de l’algorithme de résolution d’intersection de polygones. Normalement, vous voudrez sélectionner une région en fonction du nombre d’enroulements de chaque région. Recherchez le numéro de bobinage des polygones pour obtenir une explication à ce sujet.

Si vous voulez faire un algorithme O (N · logN) à partir de celui O (N²), vous devez faire exactement la même chose, sauf que vous le faites dans un algorithme de balayage de ligne. Recherchez l’ algorithme de Bentley Ottman . L’algorithme interne sera le même, à la seule différence que vous aurez un nombre réduit d’arêtes à comparer, à l’intérieur de la boucle.

La façon dont j’ai travaillé sur le même problème

  1. briser le polygone en segments de ligne
  2. trouver la ligne d’intersection en utilisant IntervalTrees ou LineSweepAlgo
  3. trouver un chemin fermé en utilisant GrahamScanAlgo pour trouver un chemin fermé avec des sumts adjacents
  4. Renvoi 3. avec DinicAlgo pour les dissoudre

note: mon scénario était différent étant donné que les polygones avaient un vertice commun. Mais espérons que cela peut aider

Cela peut être une approximation énorme en fonction de vos polygones, mais en voici une:

  • Calculer le centre de masse pour chaque polygone.
  • Calculez la distance minimale ou maximale ou moyenne entre chaque point du polygone et le centre de gravité.
  • Si C1C2 (où C1 / 2 est le centre du premier / deuxième polygone)> = D1 + D2 (où D1 / 2 est la distance que vous avez calculée pour le premier / second polygone), les deux polygones “se croisent”.

Bien que cela devrait être très efficace, toute transformation du polygone s’applique de la même manière au centre de masse et les distances entre les nœuds centraux ne peuvent être calculées qu’une seule fois.