Comment recouper deux polygones?
https://stackoverflow.com/questions/1526352
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Cela semble non trivial (il se demande beaucoup sur divers forums), mais je dois absolument cela comme un bloc de construction pour un algorithme plus complexe.
Entrée : 2 polygones (A et B) en 2D, étant donné que la liste des arêtes [(x0, y0, x1, y2), ...] chacun. Les points sont représentés par des paires de doubles. Je ne sais pas si elles sont données dans le sens horaire, dans le sens antihoraire ou dans toutes les directions du tout. I ne savent qu'ils ne sont pas nécessairement convexe.
Sortie : 3 polygones représentant A, B et le polygone d'intersection AB. Dont chacun peut être un polygone vide (?), Par exemple null.
Astuce pour l'optimisation : Ces polygones représentent les limites de chambre et de sol. Ainsi, la limite de la chambre sera normalement entièrement intersection avec la limite du sol, à moins qu'il appartient à un autre étage sur le même plan (argh!).
Je suis quelqu'un genre d'espoir a déjà fait en c # et me laisser utiliser leur stratégie / code, comme ce que je l'ai trouvé à ce jour sur ce problème est plutôt décourageant.
EDIT : Il semble que je ne suis pas tout à fait le 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 : Première polygone moins tous les bits se coupent, les polygones d'intersection (au pluriel est ok). Je ne suis pas vraiment intéressé par le second polygone, juste son intersection avec la première.
EDIT2 : J'utilise actuellement le GPC ( Polygon général Clipper) bibliothèque qui fait vraiment facilement!
La solution
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 un des nombreux algorithmes d'intersection de polygones disponibles qui existent déjà.
Je considérais fortement la base de code 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 étranges. Vous auriez besoin de faire un don d'un montant (vous / choix de votre entreprise) si vous l'utilisez dans le commerce, mais il vaut la peine d'obtenir une version robuste de ce genre 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 peut-être trouver quelque chose de similaire dans les bibliothèques propres C # MS à utiliser.
Il y a d'autres options là-bas aussi; recherchez « clipper polygone » ou « écrêtage de polygone », puisque les mêmes algorithmes de base qui gèrent l'intersection des polygones ont également tendance à être utilisable pour les cas de découpage général.
Une fois que vous avez fait une bibliothèque écrêtage polygone, il vous suffit de soustraire un polygone B du polygone A pour obtenir votre premier morceau de sortie, et recouper les polygones A et B pour obtenir votre deuxième morceau de sortie.
Comment rouler votre propre, pour le désespérément masochistes
Quand je considérais rouler mon propre, j'ai trouvé 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 dans ceux qui entrent dans le polygone final ou la sortie du polygone finale, alors vous formez un graphique sur tous les points, puis marchez le graphique dans les directions appropriées afin d'en extraire toutes les pièces du polygone vouloir. En changeant la façon dont vous définissez et traiter les "entrant" et "exiting" polygones, vous pouvez réaliser plusieurs intersections de polygones possibles (AND, OR, XOR, etc.).
Il est en fait assez implémentable, mais comme avec tout code de géométrie algorithmique, le diable est dans les dégénérescences.
Autres conseils
FastGEO Arash Partow contient des implémentations de nombreux algorithmes intéressants dans la géométrie algorithmique. intersection Polygon est l'un d'entre eux. Il est écrit en Pascal, mais il est seulement la mise en œuvre des mathématiques il est assez facile à lire. Notez que vous aurez certainement besoin de prétraiter vos bords un peu, pour les amener dans le sens horaire ou anti-horaire pour.
ETA: Mais vraiment, la meilleure façon de le faire est de ne pas faire . Trouver une autre façon d'aborder votre problème qui ne concerne pas les intersections de polygones arbitraires.
Si vous programmez dans .NET Framework, vous pouvez jeter un oeil à la classe SqlGeometry disponibles dans les assemblages .NET expédié comme Types Microsoft System SQL Server CLR
La classe SqlGeometry fournit STIntersection méthode
SqlGeometry g1 = SqlGeometry.Parse("POLYGON ((...))");
SqlGeometry g2 = SqlGeometry.Parse("POLYGON ((...))");
SqlGeometry intersection = g1.STIntersection(g2);
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 chevauche, il y aura un point An (de la liste des points décrivant polygone A) qui se trouve dans la zone entourée par un polygone B ou vice versa (un point B est en A). Si aucun tel point est trouvé, les polygones ne se chevauchent pas. Si un tel point est trouvé (c.-à-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 mensonges dans le second completly polygone). Si vous avez trouvé un point extérieur, vous pouvez calculer le point de passage. Trouvez le bord du polygone B et suivre correspondant aux rôles resersed = vérifier maintenant si les points de polygone se trouvent B dans un polygone A. De cette façon, vous pouvez construire une liste de points qui décrivent le polygone qui se chevauchent. 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 peut y avoir de meilleures façons. Si vous trouvez un travail et solution éprouvée, je vous recommande de ne l'utiliser ...
narozed
Essayez d'utiliser des outils SIG pour que, comme ArcObjects, TopologySuite, GEOS, OGR, etc. Je ne sais pas si toutes ces distributions sont availuable à .net, mais ils font tous la même chose.
Clipper est un freeware open source bibliothèque clipping 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 beaucoup plus rapide et beaucoup moins sujettes aux erreurs que GPC (voir des comparaisons plus détaillées ici - http://www.angusj.com/delphi/clipper.php#features ). De plus, alors qu'il ya le code source pour Delphi et C ++, la bibliothèque Clipper comprend également une DLL compilée pour le rendre très facile à utiliser les fonctions de découpage dans d'autres langues (Windows) aussi.
papier académique explique comment faire.
Si vous osez jeter un oeil au code d'autres GPL de personnes 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)
