Boolesche Operationen auf Rechteckpolygonen

Question

Avast dort Kollegen Programmierer!

Ich habe folgendes Problem:

Ich habe zwei Rechtecke überlappen, wie unten auf dem Bild gezeigt.

Ich möchte das Polygon, um herauszufinden, von Punkt ABCDEF aus.

Alternative Weihnachtsbeschreibung: Der rote Ausstecher schneidet etwas vom schwarzen Keks ab. Ich möchte den schwarzen Keks berechnen.

Jedes Rechteck ist eine Datenstruktur mit 4 2d-Vertices.

Was ist der beste Algorithmus, um dies zu erreichen?

Answer 1

Dies ist ein Spezialfall des allgemeinen 2D-Polygon Clipping. Ein guter Ausgangspunkt ist der Weiler-Atherton-Algorithmus. Wikipedia has a summary und links to the original paper. Der Algorithmus scheint mit der von Ihnen beschriebenen Datenstruktur übereinzustimmen.

Beachten Sie, dass es sehr wahrscheinlich ist, dass Sie ein Rechteck mit einem Loch (wenn das rote vollständig innerhalb des schwarzen ist) oder sogar zwei Rechtecken (z. B. wenn das Rot größer und dünner als das Schwarz ist). Wenn Sie sicher sind, dass nur eine Ecke des roten Rechtecks ​​in der schwarzen liegt, sollte die Lösung viel einfacher sein.

Answer 2

constructive solid geometry

Answer 3

Ich fand hier einige Sachen, die ich verwenden könnte:

http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Boolean_set_operations_2/Chapter_main.html

ich die CGAL Quelle tatsächlich heruntergeladen, bevor ich diese Frage gepostet, aber ich denke, ich werde in sie näher betrachten.

Answer 4

Wie genau sind die Koordinaten? Wenn die Rechtecke ziemlich klein sind, ist es am einfachsten, sie einfach auf eine Leinwand zu malen, zuerst ein schwarzes Rechteck, dann ein rotes. Die verbleibenden schwarzen Pixel auf der Leinwand sind das übrig gebliebene Polygon. Ein anderer Ansatz besteht darin, das Koordinatengitter in eine Reihe von Rechtecken zu zerlegen, die auf allen Seiten der Rechtecke basieren (ohne ungebundene Rechtecke, bis zu 9 Rechtecke, wenn Sie zwei ursprüngliche Rechtecke haben). Dann teste einfach einen repräsentativen Punkt von jedem dieser Rechtecke auf Zugehörigkeit zu den bestimmten Polygonen, um zu bestimmen, welche Rechtecke innen und welche außen sind.