Comment couper deux polygones?

Question

Cela semble non-trivial (il est demandé beaucoup sur divers forums), mais j'ai absolument besoin de cela comme un bloc de construction pour un algorithme plus complexe.

Entrée: 2 polygones (A et B) en 2D, donnés sous la forme d'une liste d'arêtes [(x0, y0, x1, y2), ...] chacun. Les points sont représentés par des paires de double s. Je ne sais pas s'ils sont donnés dans le sens des aiguilles d'une montre, dans le sens inverse des aiguilles d'une montre ou dans n'importe quelle direction. I do sachez qu'ils ne sont pas nécessairement convexes.

Sortie: 3 polygones représentant A, B et le polygone d'intersection AB. L'un ou l'autre peut être un polygone vide (?), Par ex. null.

Conseil pour l'optimisation: Ces polygones représentent les limites de la pièce et du plancher. Donc, la limite de la pièce se croisera normalement complètement avec la limite du plancher, sauf si elle appartient à un autre étage sur le même plan (argh!). Je souhaite que quelqu'un ait déjà fait cela en C# et me laisse utiliser leur stratégie/code, car ce que j'ai trouvé jusqu'ici sur ce problème est plutôt intimidant.

EDIT: Donc, il semble que je ne suis pas entièrement poulet pour feiling faible à la perspective de le faire. Je reprends ici la sortie désirée, car cela est un cas particulier et peut rendre le calcul plus simple:

Sortie: polygone d'abord moins tous les bits qui se croisent, des polygones d'intersection (au pluriel est ok). Je ne m'intéresse pas vraiment au deuxième polygone, juste son intersection avec le premier.

EDIT2: J'utilise actuellement la bibliothèque GPC (General Polygon Clipper) qui rend cela vraiment facile!

Answer 1

Ce que je pense que vous devriez faire

Ne pas essayer de faire vous-même si vous pouvez l'aider. Au lieu de cela, utilisez l'un des nombreux algorithmes d'intersection de polygones disponibles qui existent déjà. Je considérais fortement la base de code suivante sur la force de leur code de démonstration et le fait qu'ils ont mentionné leur traitement de la plupart/tous les cas bizarres. Vous devrez donner un montant (de vous/au choix de votre entreprise) si vous l'utilisez commercialement, mais cela vaut la peine d'obtenir une version robuste de ce type de code.

http://www.cs.man.ac.uk/~toby/gpc/

Ce que je fait réellement était d'utiliser un algorithme de polygone intersection qui fait partie des bibliothèques Java2D. Vous pouvez éventuellement trouver quelque chose de similaire dans les propres bibliothèques C# de MS à utiliser.

D'autres options existent également; Recherchez "polygon clipper" ou "polygone clipping", car les mêmes algorithmes de base qui gèrent l'intersection polygonale ont également tendance à être utilisables pour les cas généraux de découpage. Une fois que vous avez réellement une bibliothèque de découpage de polygones, vous devez simplement soustraire le polygone B du polygone A pour obtenir votre première sortie, et croiser les polygones A et B pour obtenir votre deuxième sortie.

Comment rouler votre propre, pour le désespérément masochistes

Quand je considérais rouler mon propre, je trouve l'algorithme Weiler-Atherton d'avoir le plus grand potentiel pour le polygone de coupe générale. J'ai utilisé le suivant comme référence:

http://cs1.bradley.edu/public/jcm/weileratherton.html

http://en.wikipedia.org/wiki/Weiler-Atherton

Les détails, comme on dit, sont trop denses pour inclure ici, mais je ne doute pas que vous serez en mesure de trouver des références sur Weiler-Atherton pour les années à venir. Essentiellement, vous divisez tous les points en ceux qui entrent dans le polygone final ou en sortant du polygone final, puis vous formez un graphique sur tous les points, puis vous parcourez le graphique dans les directions appropriées afin d'extraire tous les polygones vouloir. En changeant la façon dont vous définissez et traitez les polygones «entrant» et «sortant», vous pouvez réaliser plusieurs intersections de polygones possibles (AND, OR, XOR, etc.). C'est en fait assez implémentable, mais comme avec n'importe quel code de géométrie computationnelle, le diable est dans les dégénérescences.

Answer 2

La bibliothèque FastGEO d'Arash Partow contient des implémentations de nombreux algorithmes intéressants en géométrie de calcul. L'intersection des polygones en fait partie. C'est écrit en Pascal, mais cela ne fait qu'appliquer les mathématiques, donc c'est assez lisible. Notez que vous aurez certainement besoin de prétraiter vos bords un peu, pour les mettre dans le sens horaire ou antihoraire. ETA: Mais vraiment, le meilleur moyen de le faire est de ne pas le faire. Trouvez une autre façon d'aborder votre problème qui n'implique pas d'intersections de polygones arbitraires.

Answer 3

Vous pouvez également jeter un oeil à la NetTopologySuite ou même essayer de l'importer dans SQL Server 2008 & c'est outils spatiaux.

Answer 4

Si vous osez jeter un oeil à d'autres code de personnes GPL C++, vous pouvez voir comment ils le font dans Inkscape:

http://bazaar.launchpad.net/~inkscape.dev/inkscape/trunk/view/head:/src/2geom/shape.cpp (ligne 126)

Answer 5

Un polygone est entièrement décrit par un ordre liste des points (P1, P2, ..., Pn). Les arêtes sont (P1 - P2), (P2 - P3), ..., (Pn - P1). Si vous avez deux polygones A et B qui se chevauchent, il y aura un point An (de la liste sur les points décrivant le polygone A) qui se trouve dans la zone entourée par le polygone B ou vice versa (un point de B se trouve dans A). Si aucun point n'est trouvé, les polygones ne se chevauchent pas. Si un tel point est trouvé (c'est-à-dire Ai), vérifiez les points adjacents du polygone A (i-1) et A (i + 1). Répétez jusqu'à ce que vous trouviez un point en dehors de la zone ou que tous les points soient vérifiés (alors le premier polygone se trouve complètement dans le second polygone). Si vous avez trouvé un point à l'extérieur, vous pouvez calculer le point de passage. Trouvez le bord correspondant du polygone B et suivez-le avec des rôles resersés = vérifiez maintenant si les points du polygone B se trouvent dans le polygone A. De cette façon, vous pouvez construire une liste de points qui décrivent le polygone qui se chevauche. Si nécessaire, vous devriez vérifier si les polygones sont identiques, (P1, P2, P3) === (P2, P3, P1).

Ceci est juste une idée et il y a peut-être de meilleurs moyens. Si vous trouvez un travail et solution éprouvée, je vous recommande de ne l'utiliser ...

narozed

Answer 6

Essayez d'utiliser des outils SIG pour que, comme ArcObjects, TopologySuite, GEOS, OGR, etc.Je ne suis pas sûr si toutes ces distributions sont disponibles à. Net, mais ils font tous la même chose.

Answer 7

Si vous programmez dans .NET Framework, vous pouvez jeter un oeil à la classe SqlGeometry disponibles dans les assemblages .NET expédié comme Microsoft SQL Server System CLR Types

La classe SqlGeometry fournit STIntersection méthode

SqlGeometry g1 = SqlGeometry.Parse("POLYGON ((...))"); 
SqlGeometry g2 = SqlGeometry.Parse("POLYGON ((...))"); 
SqlGeometry intersection = g1.STIntersection(g2); 

Answer 8

Clipper est un freeware open source bibliothèque d'écrêtage polygone (écrit en Delphi et C++) qui fait exactement ce que vous demandez - http://sourceforge.net/projects/polyclipping/

Dans mes tests, Clipper est à la fois significativement plus rapide et beaucoup moins sujet aux erreurs que GPC (voir des comparaisons plus détaillées ici - http://www.angusj.com/delphi/clipper.php#features). En outre, s'il existe du code source pour Delphi et C++, la bibliothèque Clipper inclut également une DLL compilée pour faciliter l'utilisation des fonctions de découpage dans d'autres langages (Windows).

Answer 9

Cette academic paper explique comment procéder.