Un algorithme simple pour l'intersection de polygones

Question

Je suis à la recherche d'un algorithme très simple pour le calcul du polygone d'intersection/écrêtage. C'est, compte tenu des polygones P, Q, je souhaite trouver un polygone T qui est contenue dans P et Q, et je voudrais T d'être à son maximum parmi tous les possibles de polygones.

Je n'ai pas l'esprit le temps d'exécution (j'ai quelques très petits polygones), je peux également permettre d'obtenir une approximation de la polygones' intersection (c'est un polygone avec moins de points, mais qui est encore contenue dans les polygones d'intersection).

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

edit: remarque, je souhaite obtenir un polygone qui représente l'intersection. Je n'ai pas besoin seulement d'un booléen réponse à la question de savoir si les deux polygones se croisent.

Answer 1

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

Néanmoins, j'ai récemment créé une bibliothèque de coupures de logiciels libres open-source (écrites en Delphi, C ++ et C #), qui permet de clipser toutes sortes de polygones (y compris ceux qui se croisent automatiquement). Cette bibliothèque est assez simple à utiliser: http://sourceforge.net/projects/polyclipping/ .

Answer 2

Vous pouvez utiliser un Polygone d'Écrêtage algorithme pour trouver l'intersection entre deux polygones. Cependant ceux-ci tendent à être des algorithmes complexes, lorsque l'ensemble des cas limites sont prises en compte.

Une mise en œuvre de polygone de découpage, vous pouvez utiliser votre moteur de recherche préféré pour trouver est Weiler-Atherton. article de wikipédia sur Weiler-Atherton

Alan Murta a une mise en œuvre complète d'un polygone clipper GPC.

Edit:

Une autre approche est d'abord de diviser chaque polygone en un ensemble de triangles, qui sont plus faciles à traiter. Les Deux Oreilles Théorème par Gary H. Meisters fait le tour. Cette page à l'université McGill fait un bon travail d'expliquer triangle de la subdivision.

Answer 3

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.

Answer 4

Voici une approche basée sur la triangulation qui est assez simple à mettre en œuvre et peuvent être faites pour s'exécuter en O(N²).

BTW, O(N²) est optimale pour ce problème. Imaginez deux polygones en forme de fourche lames se coupant à angle droit. Chacun a un certain nombre de segments proportionnels au nombre de dents, le nombre de polygones dans l'intersection est proportionnelle au carré du nombre de dents.

1. Tout d'abord, recouper chaque polygone.

2. Comparez tous les triangles de P par paires avec tous les triangles de Q pour détecter les intersections. N'importe quelle paire de l'intersection des triangles peut être divisé en plus petits triangles de chaque de ce qui est dans P, Q, ou dans l'intersection. (Ce que vous avez utilisé à l'étape 1 peut être réutilisé pour de l'aide avec cela.) Seulement de garder les triangles qui sont dans l'intersection.

3. Calculer les voisins de chaque triangle, en les comparant deux à deux, et de construire un graphe d'adjacence. Ce graphe contient un sous-graphe connecté pour chaque polygone, à l'intersection de P et de Q.

4. Pour chacun de ces sous-graphe, choisissez un triangle, marcher sur le bord, et à marcher autour de la pointe, la production des segments de délimitation de la sortie correspondante du polygone.