Comment croiser deux polygones?
cela semble non-trivial (il est demandé pas mal de choses sur différents 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é comme une liste de bords [(x0, y0, x1, y2), ...] chaque. Les points sont représentés par des paires de doubles. Je ne sais pas si ils sont donnés dans le sens horaire, antihoraire ou dans n'importe quelle direction. J' savent qu'ils ne sont pas nécessairement convexe.
Sortie: 3 polygones représentant A, B et l'intersection du polygone AB. Ce qui peut être vide (?) polygone, par exemple,null.
indice d'optimisation: ces polygones représentent les limites des pièces et des planchers. Ainsi, la limite de la pièce se croise normalement complètement avec la limite du plancher, à moins qu'elle n'appartienne à un autre plancher sur le même plan (argh!).
j'espère que quelqu'un a déjà fait ça en c# et va permettez-moi d'utiliser leur stratégie/code, car ce que j'ai trouvé jusqu'à présent sur ce problème est plutôt intimidant.
EDIT: il semble donc que je ne suis pas tout à fait poulet pour Feiler faible à la perspective de faire cela. J'aimerais rappeler la sortie désirée, ici, que c'est un cas particulier et pourrait rendre le calcul plus simple:
Sortie: premier polygone moins tous les bits qui se croisent, polygones d'intersection (le pluriel est ok). Je ne suis pas vraiment intéressé à l' deuxième polygone, juste son intersection avec le premier.
EDIT2: je suis actuellement en utilisant le GPC (Général Polygone Clipper) bibliothèque qui fait vraiment facilement!
9 réponses
Ce que je pense que vous devriez faire
ne tentez pas de le faire vous-même si vous pouvez l'aider. Utilisez plutôt l'un des nombreux algorithmes disponibles d'intersection de polygones qui existent déjà.
je considérais fortement le codebase suivant 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 devez donner un montant (de votre choix ou de celui de votre entreprise) si vous l'utilisez. commercialement, mais il vaut la peine d'obtenir une version robuste de ce genre de code.
http://www.cs.man.ac.uk / ~ toby/gpc/
en fait, j'ai utilisé un algorithme d'intersection de polygones qui fait partie des bibliothèques Java2D. Vous pouvez peut-être trouver quelque chose de similaire dans les propres bibliothèques C# DE MS à utiliser.
il y a d'autres options là-bas aussi bien; rechercher "rogon clipper" ou "polygon clipping", depuis les mêmes algorithmes de base qui traitent l'intersection des polygones a aussi tendance à être utilisable pour les cas de coupures générales.
une fois que vous avez réellement une bibliothèque de découpage de polygones, vous avez juste besoin de soustraire le polygone B du polygone A pour obtenir votre premier morceau de sortie, et intersecter les polygones A et B pour obtenir votre deuxième morceau de sortie.
Comment faire vos propre, pour l'désespérément masochiste
quand j'envisageais de rouler le mien, j'ai trouvé L'algorithme de Weiler-Atherton pour avoir le plus potentiel de coupe générale de polygones. J'ai utilisé les éléments suivants 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 être inclus ici, mais je ne doute pas que vous pourrez trouver des références sur Weiler-Atherton pour les années à venir. Essentiellement, vous divisez tous les points en ceux qui entrent dans la finale polygone ou sortie du polygone final, puis vous formez un graphe à partir de tous les points, et puis marcher le graphe dans les directions appropriées afin d'extraire tous les morceaux de polygone que vous voulez. En changeant la façon dont vous définissez et traitez les polygones "entrée" et "sortie", vous pouvez réaliser plusieurs intersections polygonales possibles (et, ou, XOR, etc.).
c'est en fait assez réalisable, mais comme avec n'importe quel code de géométrie computationnelle, le diable est dans les dégénérescences.
Arash Partow FastGEO bibliothèque contient des implémentations de nombreux algorithmes intéressants en Géométrie computationnelle. Polygon intersection est l'une d'entre elles. C'est écrit en Pascal, mais c'est seulement des maths d'implémentation donc c'est assez lisible. Notez que vous aurez certainement besoin de pré-traiter vos bords un peu, pour les obtenir dans le sens des aiguilles d'une montre ou dans le sens inverse des aiguilles d'une montre.
ETA: Mais vraiment, la meilleure façon de le faire est de ne pas faire cela. Trouver une autre façon de approchez votre problème qui n'implique pas des intersections de polygones arbitraires.
si vous programmez dans .net Framework, vous pouvez jeter un coup d'oeil à la classe SqlGeometry disponible dans les assemblages .NET livrés en tant que 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);
Vous pouvez aussi avoir un coup d'oeil à l' NetTopologySuite ou même d'essayer de l'importer dans Sql server 2008 & c'est des moyens spatiaux.
un polygone est entièrement décrit par une liste ordonnée de points (P1, P2, ..., Pn). Les bords 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 en A). Si aucun point n'est trouvée, les polygones ne se chevauchent pas. Si un tel point est trouvé (i.e. Ai) vérifier 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 tous les points sont vérifiés (alors le premier polygone se trouve complètement à l'intérieur du second polygone). Si vous avez trouvé un point à l'extérieur, alors vous pouvez calculer le point de passage. Trouvez le bord correspondant du polygone B et suivez-le avec les 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 se chevauchant. Si nécessaire, vous devriez vérifier si les polygones sont identiques, (P1, P2, P3) = = = (P2, P3, P1).
ce n'est qu'une idée et il y a peut-être de meilleures façons. Si vous trouvez une solution testée, je vous recommande de l'utiliser...
narozed
essayez d'utiliser des outils SIG pour cela, tels que ArcObjects, TopologySuite, GEOS, OGR, etc. Je ne suis pas sûr que toutes ces distributions soient disponibles pour .net, mais elles font toutes la même chose.
Clipper est un freeware open source polygone d'écrêtage de la bibliothèque (écrit en Delphi et C++) qui fait exactement ce que vous demandez - http://sourceforge.net/projects/polyclipping/
In my testing, Clipper is both significantly faster and far less likely to error than GPC (see more detailed comparisons here -http://www.angusj.com/delphi/clipper.php#features). De plus, alors qu'il y a du code source pour Delphi et C++, Le Clipper bibliothèque comprend également une DLL compilée pour le rendre très facile à utiliser les fonctions de découpage dans D'autres langues (Windows) aussi.
si vous osez jeter un oeil au code GPL C++ d'autres personnes, 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)