Dies scheint nicht trivial zu sein (es wird in verschiedenen Foren ziemlich oft gefragt), aber ich brauche es unbedingt als Baustein für einen komplexeren Algorithmus.

Eingang: 2 Polygone (A und B) in 2D, angegeben als Kantenliste[(x0, y0, x1, y2), ...] jeder. Die Punkte werden durch Paare von dargestelltdoubles. Ich weiß nicht, ob sie im Uhrzeigersinn, gegen den Uhrzeigersinn oder in irgendeine Richtung gegeben werden. ichtun wissen, dass sie nicht unbedingt konvex sind.

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

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

Ich hoffe, jemand hat dies bereits in c # getan und lässt mich seine Strategie / seinen Code verwenden, da das, was ich bisher zu diesem Problem festgestellt habe, ziemlich entmutigend ist.

BEARBEITEN: Es scheint also, als wäre ich nicht ganz ein Idiot bei der Aussicht, dies zu tun. Ich möchte die gewünschte Ausgabe hier noch einmal wiederholen, da dies ein Sonderfall ist und die Berechnung möglicherweise vereinfacht:

Ausgabe: Erstes Polygon abzüglich aller sich überschneidenden Bits, Schnittpolygone (Plural ist in Ordnung). Das zweite Polygon interessiert mich nicht wirklich, nur die Schnittmenge mit dem ersten.

EDIT2: Ich benutze derzeit dieGPC (General Polygon Clipper) Bibliothek, die das wirklich einfach macht!