Finde überlappende konvexe Polygone

Question

Ich habe eine Reihe von konvexen Polygonen mit einer moderaten Anzahl von Seiten (sagen wir von 4 bis 30). Es gibt einige Zehntel Polygone, sagen wir 100 bis 1000. Die meisten sind isoliert, aber einige bilden kleine Gruppen von 2 bis 10, die sich überlappen.

Ich muss diese Gruppen überlappender Polygone effizient identifizieren.

Gibt es einen klassischen Algorithmus? (Ich denke an einen Sweepline-Ansatz, aber vielleicht ist es besser?) Wäre es von Vorteil, die Polygone vor der Erkennung in Kästen einzuschließen?

Unten, ein repräsentativer Fall.

Answer 1

Ein traditioneller Ansatz, der für diese Art von Problem in zwei Dimensionen verwendet wird ist ein Quadtree zu bauen, die hierarchisch in immer kleinere Eimer Ihre 2D-Raum teilt, bis Sie eine kleine Anzahl von Objekten in jedem Eimer haben.

Ihre Überlappungserkennung würde den Quadtree durchlaufen, bis Sie den Bucket oder den Satz von Buckets gefunden haben, die von Ihrem Objekt geschnitten wurden, und dann Ihre Überlappungserkennung mit einem kleineren Satz von Objekten durchführen.

Es gibt eine einfache Einführung in Aufbau und sie zur Kollisionserkennung verwenden hier: Quick Tip: Use Quadtrees to Detect Likely Collisions in 2D Space

Ein einfacher, aber rechenintensiver Ansatz etwas ein bisschen wie mit einem Z-Puffer zu tun wäre, um zu bestimmen, ob ein Polygon einer anderen verschliesst :

• jedes Ihrer Polygone Zuweisung einer eindeutigen Nummer (es ist Tiefe)
• Rastern jedes Polygon in einen Puffer, die jeweils in den Puffer schreiben zu überprüfen, ob Sie ein Pixel eingeschlossen haben, die bereits festgelegt ist. Wenn dies der Fall ist, identifiziert die Tiefe, welches Polygon Sie verdeckt haben, und den neuen Wert, in den Sie das Polygon schreiben, mit dem Sie es verdeckt haben.