Wie schneidet man zwei Polygone?

Dies scheint nicht-trivial (es wird ziemlich oft in verschiedenen Foren gefragt), aber ich brauche es unbedingt als Baustein für einen komplexeren Algorithmus.Wie schneidet man zwei Polygone?

Eingabe: 2 Polygone (A und B) in 2D, jeweils als Liste der Kanten [(x0, y0, x1, y2), ...]. Die Punkte werden durch Paare von double s dargestellt. Ich weiß nicht, ob sie im Uhrzeigersinn, gegen den Uhrzeigersinn oder in irgendeiner Richtung gegeben werden. I tun wissen, dass sie nicht unbedingt konvex sind.

Ausgabe: 3 Polygone, die A, B und das sich schneidende Polygon AB darstellen. Eines davon kann ein leeres (?) Polygon sein, z.B. null.

Hinweis zur Optimierung: Diese Polygone repräsentieren Raum- und Bodengrenzen. Die Raumgrenze schneidet sich normalerweise vollständig mit der Bodengrenze, es sei denn, sie gehört zu einem anderen Stockwerk derselben Ebene (argh!).

Ich hoffe irgendwie jemand hat dies bereits in C# getan und wird mich ihre Strategie/Code verwenden, wie das, was ich bisher zu diesem Problem gefunden habe, ziemlich entmutigend ist.

EDIT: So scheint es, ich bin nicht ganz Huhn für Feiling Ohnmacht bei der Aussicht, dies zu tun. Ich möchte hier die gewünschte Ausgabe wiederholen, da dies ein Spezialfall ist und die Berechnung einfacher machen könnte:

Ausgabe: Erstes Polygon minus alle überschneidenden Bits, Schnittpolygone (Plural ist in Ordnung). Ich bin nicht wirklich an dem zweiten Polygon interessiert, nur an seinem Schnittpunkt mit dem ersten.

EDIT2: Ich verwende derzeit die GPC (General Polygon Clipper)-Bibliothek, die dies wirklich einfach macht!

Quelle

2009-10-06 Daren Thomas

Dies ist komplizierter als Sie vielleicht denken. Wie wollen Sie die resultierende Form darstellen? Bedenken Sie, dass die beiden Eingaben (a) sich überhaupt nicht schneiden können, (b) sich teilweise schneiden, was zu einer konvexen oder konkaven geschlossenen Form führt, (c) sich vollständig überschneiden, was zu einer Form mit ZWEI Grenzen (dh Donut) führt Sie müssen einen Weg finden, das Innere und Äußere der Form darzustellen. –

In der Tat hat Jon Recht. Dein Problem ist nicht gut angegeben; Die resultierende Menge * ist möglicherweise kein Polygon * und daher sollte die Ausgabe der Funktion kein Polygon sein. Was möchten Sie in dem Fall tun, in dem die resultierende Form nicht verbunden ist? Stellen Sie sich zum Beispiel ein C-förmiges Poly vor, das ein I-förmiges Poly schneidet, was zu einem Doppelpunkt führt. –

danke, muss darüber nachdenken und eine Lösung finden. Ich habe nicht vorher so darüber nachgedacht ... –

Was ich glaube, Sie tun sollten

Versuchen Sie nicht, dies selbst zu tun, wenn Sie es möglicherweise helfen können. Verwenden Sie stattdessen einen der vielen verfügbaren Polygonschnittalgorithmen, die bereits vorhanden sind.

Ich dachte stark über die folgende Codebasis aufgrund der Stärke ihrer Demo-Code und die Tatsache, dass sie ihre Behandlung der meisten/alle der seltsamen Fälle erwähnt. Sie müssten einen Betrag (von Ihnen/Ihrer Firma) spenden, wenn Sie ihn kommerziell nutzen, aber es lohnt sich, eine robuste Version dieser Art von Code zu bekommen.

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

Was ich war eigentlich ein Polygon-Kreuzung Algorithmus, der einen Teil der Java2D Bibliotheken verwendet haben ist. Sie können möglicherweise etwas Ähnliches in MS-eigenen C# -Bibliotheken finden.

Es gibt andere Möglichkeiten da draußen; Suchen Sie nach "Polygon-Clipper" oder "Polygon-Clipping", da dieselben grundlegenden Algorithmen, die Polygonschnittpunkte verarbeiten, auch für allgemeine Clipping-Fälle geeignet sind.

Sobald Sie tatsächlich eine Polygon-Clipping-Bibliothek haben, müssen Sie nur Polygon B von Polygon A subtrahieren, um Ihre erste Ausgabe zu erhalten, und Polygone A und B schneiden, um Ihre zweite Ausgabe zu erhalten.

Wie Sie Ihre eigene Rolle, für die hoffnungslos masochistisch

Als ich meine eigenen bedenken rollen, fand ich den Weiler-Atherton-Algorithmus das größte Potenzial für die allgemeine Polygon-Schneiden zu haben. Früher habe ich die folgenden als Referenz:

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

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

Die Details, wie sie sagen, sind zu dicht, hier zu zählen, aber ich habe keinen Zweifel daran, dass Sie in der Lage sein werden Referenzen zu finden auf Weiler-Atherton für die kommenden Jahre. Im Wesentlichen teilt man alle Punkte in solche auf, die in das letzte Polygon eintreten oder das letzte Polygon verlassen, dann formt man aus allen Punkten einen Graphen und begibt sich dann in die entsprechenden Richtungen, um alle Polygonteile zu extrahieren wollen. Indem Sie die Definition und Behandlung der Polygone "Eingeben" und "Beenden" ändern, können Sie mehrere mögliche Polygonschnittpunkte (AND, OR, XOR usw.) erreichen.

Es ist eigentlich ziemlich implementierbar, aber wie bei jedem Computer-Geometrie-Code ist der Teufel in den Entartungen.

Quelle

2009-10-06 18:04:53 jprete

nur noch einmal besucht. Ich habe am Ende mit der Gpc-Bibliothek (Top Link). es ist fantastisch. –

Die Bibliothek FastGEO von Arash Partow enthält Implementierungen vieler interessanter Algorithmen in der computergestützten Geometrie. Polygon-Schnittpunkt ist einer von ihnen. Es ist in Pascal geschrieben, aber es implementiert nur Mathe, so dass es gut lesbar ist. Beachten Sie, dass Sie Ihre Kanten sicherlich ein wenig vorverarbeiten müssen, um sie im oder gegen den Uhrzeigersinn zu erhalten.

ETA: Aber wirklich, der beste Weg, dies zu tun ist, dies nicht zu tun. Finden Sie einen anderen Weg, Ihr Problem anzugehen, das keine willkürlichen Polygonüberschneidungen beinhaltet.

Quelle

2009-10-06 15:45:53

Wenn Sie dies tun, seien Sie sehr vorsichtig und ändern Sie nicht etwas vom Algorithmus vom ursprünglichen Code. Wenn möglich, rufen Sie einen Pascal-zu-C-Compiler auf oder kompilieren Sie ihn in eine Bibliothek, die Sie verwenden können, anstatt zu versuchen, den Code selbst zu übersetzen. – jprete

Sie können auch einen Blick auf die NetTopologySuite werfen oder sogar versuchen, es in Sql-Server 2008 & es räumliche Tools zu importieren.

Quelle

2009-10-06 17:54:56 oharab

+1 dafür. Ich war auf der Suche nach einem .NET-Port von JTS, und das sieht so aus, als würde es die Rechnung erfüllen. –

Wenn Sie einen Blick auf andere Menschen die GPL C++ Code wagen, können Sie sehen, wie sie es in Inkscape tun:

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

Quelle

2009-10-06 18:24:49 fortran

Ein Polygon vollständig durch eine geordnete beschrieben wird Liste der Punkte (P1, P2, ..., Pn). Die Kanten sind (P1 - P2), (P2 - P3), ..., (Pn - P1). Wenn Sie zwei Polygone A und B haben, die sich überlappen, gibt es einen Punkt An (aus der Liste der Punkte, die Polygon A beschreiben), der innerhalb des von Polygon B umgebenen Bereichs liegt oder umgekehrt (ein Punkt von B liegt in A). Wenn kein solcher Punkt gefunden wird, überlappen sich die Polygone nicht. Wenn ein solcher Punkt gefunden wird (d. H. Ai), überprüfen Sie die benachbarten Punkte des Polygons A (i-1) und A (i + 1). Wiederholen Sie dies, bis Sie einen Punkt außerhalb des Bereichs gefunden haben oder alle Punkte markiert sind (dann liegt das erste Polygon vollständig innerhalb des zweiten Polygons). Wenn Sie einen Punkt außerhalb gefunden haben, können Sie den Kreuzungspunkt berechnen. Finde die entsprechende Kante von Polygon B und folge ihr mit reserreds roles = überprüfe nun, ob die Punkte von Polygon B innerhalb von Polygon A liegen. Auf diese Weise kannst du eine Liste von Punkten erstellen, die das überlappende Polygon beschreiben. Bei Bedarf sollten Sie überprüfen, ob die Polygone identisch sind (P1, P2, P3) === (P2, P3, P1).

Dies ist nur eine Idee und vielleicht bessere Wege. Wenn Sie eine funktionierende und getestete Lösung finden würde ich empfehlen, dass Sie es verwenden ...

narozed

Quelle

2009-10-07 11:05:52 narozed

Versuchen Sie, GIS-Tools für das, wie ArcObjects zu verwenden, TopologySuite, GEOS, OGR, usw.Ich bin mir nicht sicher, ob all diese Distributionen für .net verfügbar sind, aber alle machen das gleiche.

Quelle

2009-10-08 19:25:26

FYI, OGR (von GDAL/OGR) verwendet GEOS (http://trac.osgeo.org/geos/) Bibliothek, so dass es keinen Unterschied in Bezug auf die Implementierung der Berechnungsgeometrie zwischen diesen beiden gibt. – mloskot

humn, gut zu wissen :) –

Wenn Sie in .NET Framework programmieren, möchten Sie vielleicht einen Blick auf SqlGeometry Klasse in .NET-Assemblies als Microsoft SQL Server System CLR Types

Die SqlGeometry Klasse stellt STIntersection Methode

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

Quelle

2009-11-11 01:16:22 mloskot

Ist diese Antwort inkorrekt, so wurde es downvote? Wenn ja, zeigen Sie bitte wo ein Fehler ist. – mloskot

ich stimme zu! Was ist los mit dieser Lösung? Ich persönlich mache alle meine räumlichen Sachen in der DB ... aber wenn du es im Code machen musst, nutze den gleichen Code :) –

Clipper verschifft verfügbar nehmen ist, ein Open-Source-Freeware Polygon-Ausschnitt-Bibliothek (in Delphi und C++ geschrieben), die genau das, was Sie Fragen - http://sourceforge.net/projects/polyclipping/

In meinen Tests ist Clipper sowohl wesentlich schneller und weniger fehleranfällig als GPC (siehe detailliertere Vergleiche hier - http://www.angusj.com/delphi/clipper.php#features). Während es Quellcode für Delphi und C++ gibt, enthält die Clipper-Bibliothek auch eine kompilierte DLL, um es sehr einfach zu machen, die Schnittfunktionen auch in anderen (Windows-) Sprachen zu verwenden.

Quelle

2010-06-06 18:52:40

Diese academic paper erklärt, wie dies zu tun ist.

Quelle

2011-10-05 00:25:37

Wie schneidet man zwei Polygone?

Antwort

Verwandte Themen