Algorithmus zum Finden des größten leeren Rechtecks ​​inmitten anderer Polygone

Question

Das Szenario: Es gibt einen rechteckigen Raum, in dem willkürlich angeordnete Polygone beliebiger Orientierung angeordnet sind. Ziel ist es, das größte leere Rechteck zu finden, das in die leeren Bereiche des rechteckigen Raums eingefügt werden kann. Diese Bilder unten veranschaulichen das Szenario mit den Polygonen in Blau und der gepunkteten Linie, die das maximale leere Rechteck darstellt, das in jedem Szenario angepasst werden kann.

Das Problem: Offenbar größte leere Rechtecke zu finden, ist ein well known problem in der algorithmischen Geometrie, aber die Algorithmen, die ich in diesem Bereich behandelt mit leeren Rechtecke inmitten Punkte zu finden (CGAL hat implementiert dies) und Liniensegmente. Gibt es eine Möglichkeit, diese bestehenden Techniken für mein Szenario anzupassen? Oder gibt es einen einfacheren Weg, dies zu tun?

Answer 1

Leider scheint der Großteil der mir bekannten Geometrie der Computergeometrie schöne Beschreibungen von Algorithmen und Beweise für ihre Korrektheit zu liefern, ohne Implementierungen bereitzustellen. Vielleicht liegt das daran, dass die Implementierungen im Allgemeinen eher involviert sind.

Sie erwähnen nicht, welchen Grad an Ungenauigkeit Sie tolerieren können. Wenn Sie etwas Toleranz haben, ist diese Antwort für Sie.

Mein Vorschlag ist, dass Sie dieses schwere Problem in ein einfacheres Problem verwandeln.

1. Find the bounding box Ihrer Polygonsammlung.
2. Teilen Sie die Bounding Box in ein Raster. Je feiner das Raster, desto besser ist Ihre Genauigkeit, aber je länger Sie brauchen, um eine Lösung zu finden.
3. Find wie viel Fläche jeder Gitterzelle (als rechteckiges Polygon dargestellt) das Polygon-Set schneidet.
4. Wenn die Überlappung ausreichend ist (größer als ein bestimmter Mindestwert), markieren Sie die Rasterzelle mit einer Null; Andernfalls markieren Sie es mit einer Eins.
5. Sie haben jetzt eine rechteckige Anordnung von Nullen und Einsen. Dies bildet die Grundlage für das einfachere Problem: Was ist die größte rechteckige Teilmenge dieses Gitters, die vollständig aus Einsen besteht?

Dieses leichte Problem hat eine Reihe von Lösungen zugänglich alle über das Internet (z 1, 2, 3, 4, 5, 6).