Comment puis-je trouver la zone de chevauchement entre deux polygones arbitraires

Question

Je suis en train de créer une méthode qui prendra en deux listes arbitraires de noeuds, pour un sujet et un polygone de découpage, et la sortie soit:

a) la zone du chevauchement
b) une liste de noeuds pour le polygone résultant (écrêté), de sorte que je puisse calculer la surface

j'ai trouvé beaucoup d'exemples qui attache un polygone arbitraire en utilisant une forme rectangulaire fenêtre (ce qui est assez standard dans les graphiques) mais ce n'est pas ce dont j'ai besoin. Je comprends que c'est assez complexe, surtout quand on a des trous, des polygones convexes et autres. La seule hypothèse simplificatrice que je peux faire est que les polygones arbitraires ne contiendront aucun trou.

Je ne suis pas du tout un expert dans ce domaine, alors est-ce que quelque chose comme l'algorithme de Sutherland-Hodgman fonctionnerait? Existe-t-il des bibliothèques qui le font déjà, ou est-ce que je ferais mieux de simplement implémenter l'algorithme tel que décrit dans le pseudo-code sur Wikipedia?

Merci pour l'aide!

Answer 1

J'ai trouvé que l'utilisation de la bibliothèque JavaGeom fonctionnait très bien. Il intègre le code du port Java de GPC (qui n'est plus disponible) et permet ainsi des opérations polygonales arbitraires. En utilisant SimplePolygon2D et Polygon2DUtils.intersection() j'ai pu obtenir l'opération désirée.

Answer 2

Existe-t-il des bibliothèques là-bas qui font déjà ce ...

détourage Polygon est une tâche complexe. Je ne recommanderais pas d'essayer de le faire vous-même, sauf si vous voulez passer plusieurs mois là-dessus. Wikipédia énumère un certain nombre de bibliothèques clipping (et IIRC dans cette liste que le Clipper est gratuit pour une utilisation dans des applications commerciales): http://en.wikipedia.org/wiki/Boolean_operations_on_polygons#External_links

ps: je l'avoue à un parti pris pour Clipper depuis que je suis l'auteur :) plus d'infos ici: http://angusj.com/delphi/clipper.php

Answer 3

Sons comme Weiler-Atherton est celui que vous avez besoin:

l'algorithme nécessite des polygones être dans le sens horaire et non rentrante (auto intersection) . L'algorithme peut prendre en charge les trous (comme dans le sens inverse des aiguilles d'une montre polygones entièrement à l'intérieur de leur polygone parent ), mais nécessite des algorithmes supplémentaires pour déterminer les polygones sont des trous.

Vos polygones correspondent à ces critères, n'est-ce pas? Je ne connais pas les implémentations, mais il semble que vous feriez mieux d'implémenter W-A que S-H si l'un de vos polygones pouvait être concave.

Answer 4

Essayez gpc.

Answer 5

J'ai essayé beaucoup de différentes bibliothèques et celle qui fonctionnait le mieux était la JTS Topological Suite qui est pure licence Java et LGPL2.