Rechtecke überlappungsfrei bekommen
-
Hallo,
gegeben ist eine Menge von rektilinearen Rechtecken in der Ebene. Verschiedene Rechtecke der Menge können sich überschneiden. Ich möchte nun eine Menge von Rechtecken erhalten, die die gleiche Fläche überdeckt wie die ursprüngliche Rechteckmenge, aber keine Überlappungen mehr hat.
Beispiel:
Gegeben: R1 [(0/0) (2/4)] R2 [(1/0) (3/5)] R3 [(2/0) (4/4)]
(Das Rechteck R1 wird durch die Ecken (0/0) und (2/4) aufgespannt.)Mögliche Lösung:
R1 [(0/0) (4/4)] R2 [(1/4) (3/5)]
Gibt es da fertige Algorithmen, um sowas zu berechnen? Was sind die schnellsten bekannten Algorithmen?
-
Gab's da nicht schon mal nen Thread zu? Würde mal nach Mac OS Window Tiling oder so ähnlich suchen...
-
Klingt nach nem typischen Sweepline-Algorithmus. Ich tippe also auf Aufwand O(n log n) obwohl... könnte quadratisch viele Schnittpunkte geben, also noch maximal quadratischen Reporting-Aufwand. Schneller wird's wohl kaum gehen.