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!
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 ... –