Wie finde ich das Maximum-Area-Rectangle in einem konvexen Polygon?

21

In diesem Beitrag suchen wir nach Algorithmen / Ideen, wie man das Maximum-Flächen-Rechteck innerhalb eines konvexen Polygons findet .

In der folgenden Abbildung sind Zahlen die Bereiche der angepassten Rechtecke. Wie gezeigt, kann ein gewünschtes Rechteck in jeder Abmessung variieren und kann in jedem Winkel sein.

Bearbeiten:

Wir haben keine klare Vorstellung davon, wie wir mit dem erwähnten Problem umgehen sollen, als wir hier fragten. Wir gehen jedoch davon aus, dass das Maximum-Area-Rectangle eines der Rechtecke sein kann, bei denen eine Kante an einer Kante des Polygons ausgerichtet ist (natürlich nicht unbedingt dieselbe Länge).

Bildbeschreibung hier eingeben

Entwickler
quelle
1
Können Sie angeben, welche Software Sie verwenden? Stellen Sie auch Ihre Arbeit so weit oder den allgemeinen Ansatz, den Sie erarbeitet haben, um dies zu lösen. Vielleicht kann jemand verbessern, was Sie bereits getan haben. Meiner Erfahrung nach ergeben sich weitaus nützlichere Antworten als das Posten einer Frage "aus heiterem Himmel".
Martin
1
Eng verbunden: gis.stackexchange.com/questions/22895/… .
Whuber
@Martin Software: Die Programmierung Pythonerfolgt dann Fortranbei Bedarf. Wir haben eine Vermutung, dass basierend auf unserem vorherigen Beitrag hier auch oben erwähnt whuber, dass ein Rechteck mit einer Kante, die mit Polygon gemeinsam ist, eine Antwort wäre.
Entwickler
1
Ihr Problem ist wirklich interessant, und ich glaube, ich habe hier und hier einen Lösungsalgorithmus gefunden .
Nickves
1
@nickves Danke für die Links. Würden Sie diese Informationen bitte als Antwort mit einer kleinen Erklärung der Algorithmen einfügen? Es wird möglicherweise eine gute Antwort sein, um akzeptiert zu werden.
Entwickler

Antworten:

4

Einige Anmerkungen, die zu groß sind, um sie in einen Kommentar einzufügen (obwohl dies keinen offensichtlichen Algorithmus nahelegt):

Die Pointe (EDITED) : Mindestens zwei Eckpunkte des Rechtecks ​​mit der maximalen Fläche müssen an der Grenze des Polygons liegen (dh entlang einer Kante oder an einem Eckpunkt). Wenn das Rechteck mit der maximalen Fläche kein Quadrat ist, müssen mindestens drei Eckpunkte an der Grenze des Polygons liegen.

Ich habe es mir in vier Schritten bewiesen:

Hinweis 1 : Mindestens ein Eckpunkt des Rechtecks ​​mit der maximalen Fläche liegt immer an der Grenze des Polygons. Dies ist ziemlich offensichtlich, aber ein Beweis könnte (im Widerspruch) so lauten: Angenommen, Sie hätten ein "maximales" Rechteck ohne Scheitelpunkt an der Grenze des Polygons. Das bedeutet, dass um jeden seiner Scheitelpunkte mindestens ein kleiner Raum vorhanden ist. So können Sie Ihr Rechteck ein wenig erweitern, was seiner Maximalität widerspricht.

Hinweis Nr. 2 : Mindestens zwei Eckpunkte des Rechtecks ​​mit der maximalen Fläche liegen immer an der Grenze des Polygons. Ein Beweis könnte so lauten (wieder im Widerspruch): Angenommen, Sie hätten ein "maximales" Rechteck mit nur einem Scheitelpunkt an der Grenze (garantiert durch Note # 1). Betrachten Sie die beiden Kanten, die diesem Scheitelpunkt nicht benachbart sind. Da sich ihre Endpunkte NICHT an der Grenze befinden, ist um jeden ein kleiner Raum vorhanden. So könnte eine dieser Kanten ein wenig "extrudiert" werden, was die Fläche des Polygons vergrößert und seiner Maximalität widerspricht.

Anmerkung 3 : Es gibt zwei diagonal gegenüberliegende Eckpunkte des Rechtecks ​​mit der maximalen Fläche, die an der Grenze des Polygons liegen. (Aus Anmerkung 2 wissen wir, dass es mindestens zwei gibt, aber nicht unbedingt, dass sie einander gegenüberliegen.) Aber auch hier ist es ein Widerspruch, wenn die beiden Grenzscheitelpunkte nebeneinander liegen, dann die gegenüberliegende Kante (von deren beiden Scheitelpunkten keiner) an der Grenze) könnte ein wenig extrudiert werden, was die Fläche des Rechtecks ​​vergrößert und seiner Maximalität widerspricht.

Hinweis Nr. 4 : (BEARBEITET) Wenn das Rechteck mit der maximalen Fläche kein Quadrat ist, liegen drei seiner Scheitelpunkte an der Grenze des Polygons.

Nehmen wir zum Beweis an, dass dies nicht der Fall ist, dh, dass das Rechteck mit der maximalen Fläche kein Quadrat ist, sondern nur zwei seiner Scheitelpunkte an der Grenze des Polygons liegen. Ich werde zeigen, wie man ein größeres Rechteck konstruiert, das der Maximalität widerspricht.

Rufen Sie die Eckpunkte des Rechtecks A, B, C, und D. Nehmen Sie ohne Verlust der Allgemeinheit an, dass Bund Ddie beiden sind, die sich an der Polygongrenze befinden. Da sich Aund Cim Inneren des Polygons befinden, gibt es einen Wackelraum um sie herum (dargestellt mit Kreisen um Aund Cim Bild unten). Zeichnen Sie nun einen Kreis um das Rechteck und schieben Sie die Punkte Aund Cein wenig um den Kreis um den gleichen Betrag (zu machen A'und C', siehe Abbildung unten), so dass das neue Rechteck entstehtA'BC'Dist mehr Quadrat als das ursprüngliche Rechteck. Durch diesen Vorgang wird ein neues Rechteck erstellt, das sich ebenfalls innerhalb des ursprünglichen Polygons befindet und eine größere Fläche aufweist. Dies ist ein Widerspruch, daher ist der Beweis erbracht.

Konstruieren eines neuen Rechtecks

Um diesen Beweis zu glauben, müssen Sie sich davon überzeugen, dass die Fläche eines Rechtecks, das in einen Kreis eingeschrieben ist, größer wird, wenn es "quadratischer" wird (dh der Unterschied zwischen den Kantenlängen wird kleiner). Außerdem muss das Polygon konvex sein, damit die neuen Linien darin enthalten sind. Und es gibt wahrscheinlich noch andere kleine Details, die unter den Teppich gekehrt werden, aber ich bin mir ziemlich sicher, dass sie alle funktionieren.

csd
quelle
Anmerkung 4 ist faul, weil das "Wackeln" der beiden anderen Scheitelpunkte keine Rechtecke erzeugt.
Whuber
Wahr. Ihre Visualisierung des vierten Beispiels ist jedoch nicht ganz richtig (wenn sich zwei Eckpunkte an der Polygongrenze befinden, können Sie sie nicht weiter dehnen). Ich kann zwar nicht genau sagen, wie ich es erklären soll (habe versucht, einen Kommentar zu schreiben, bin aber zu chaotisch geworden), aber ich vertraue darauf, dass Sie Recht haben.
Saryk
Ich glaube, es gibt Gegenbeispiele zu Anmerkung 4. Diejenigen, die ich gefunden habe, erfordern jedoch einige Berechnungen, um dies zu zeigen. Am einfachsten ist eine Störung durch ein unregelmäßiges Sechseck (ein Quadrat mit zwei gegenüberliegenden Ecken, die leicht abgeschnitten sind).
whuber
Einverstanden, dass Note # 4 faul ist. Ich werde heute Abend genauer hinsehen und es entweder reparieren oder entfernen.
csd
+1 Das ist eine schöne Lösung für den Schwierigkeitsgrad. Danke für die Bearbeitung!
Whuber
3

Ich habe eine sehr schnelle und abscheuliche Skizze über Ihre grüne Notiz in der Frage gemacht. Ich konnte es nicht als Kommentar posten, also musste ich eine Antwort schreiben, auch wenn es keine ist.
Ich glaube, dass wir im Bild unten ein Rechteck mit maximaler Fläche haben (nicht perfekt, es ist nur eine Skizze, die auf Paint erstellt wurde, um eine Idee zu vermitteln), und ich glaube nicht, dass Sie eine größere finden können, die eine gemeinsame Seite mit der haben würde Grenzen des schwarzen Plygons ...
Allerdings kann ich mich irren, in diesem Fall haben Sie alle meine Entschuldigungen.
Schnelle Skizze, die ich auf Farbe gemacht habe

Saryk
quelle
3
Guter Punkt (+1). Es gibt jedoch ein viel einfacheres Gegenbeispiel: Betrachten Sie das Problem, ein Rechteck mit maximaler Fläche in ein reguläres Achteck zu schreiben. Es ist leicht zu sehen (und leicht zu beweisen, indem man zuerst ein maximales Quadrat innerhalb des Achteckkreises findet), dass die Ecken der Lösung mit den alternierenden Scheitelpunkten des Achtecks ​​zusammenfallen und dass diese Lösung wesentlich größer ist als jedes kantenausgerichtete eingeschriebene Rechteck.
Whuber
Tatsächlich (ich habe gerade große Zweifel) hat das äußerste kleinste Rechteck (das aus diesem Beitrag ) dieses Polygons nicht die gleiche Ausrichtung wie eine der Seiten, oder? (Ich würde es sehen, die gleiche Ausrichtung wie mein rotes Rechteck)
Saryk
3
Das Polygon ist übrigens nicht konvex. Die ursprüngliche Frage beschränkt sich auf konvexe Polygone.
csd
2
@csd Das ist ein großartiger Punkt, aber Saryk ist immer noch richtig, wie mein Gegenbeispiel zeigt. Saryk, es gibt kein Problem mit dem minimalen Flächenbegrenzungsrechteck: Es ist leicht (rigoros) zu beweisen, dass es eine Seite des konvexen Rumpfs enthalten muss. Ich glaube, dass das mit maximaler Fläche beschriftete Rechteck (eines konvexen Polygons) nur zwei Eckpunkte haben muss, die die Grenze berühren, nicht mehr.
whuber
2

Die meisten anderen Algorithmen finden das in ein konvexes Polygon eingeschriebene geradlinige Rechteck mit maximaler Fläche und haben eine Komplexität von O(log n). Ich glaube nicht, dass Ihre Vermutung, dass das maximale Flächenpolygon an einer der Seiten ausgerichtet ist, richtig ist, da Sie lediglich die Polygonzeiten drehen müssten n, was zu einer Komplexität von führt O(n log n), und in meinen kurzen Nachforschungen konnte ich das nicht finde alles, was sagt, dass es so einfach war.

Das Papier Largest Inscribed Rectangles in Convex Polygons von Knauer et al . beschreibt einen Approximationsalgorithmus, mit dem Sie der richtigen Antwort nahe kommen.

Soweit ich den Algorithmus verstehe, baut er auf einem der bekannten achsenausgerichteten Maximalflächenpolygone auf und tastet dann zufällig Punkte im Polyonraum ab, generiert aus diesen Zufallsstichproben mehrere Achsen, iteriert über diese Achsen und wendet die Achse an -aligned Algorithmus zu jedem und gibt dann das größte Rechteck in diesem Satz zurück.

lreeder
quelle
Gibt es vielleicht einen Tippfehler im ersten Satz? Es kann unmöglich einen O (log (n)) - Algorithmus geben, da das bloße Einlesen der Koordinaten eine O (n) -Operation ist!
Whuber
Der Link ist tot
dangerousdave
1
@dangerousdave - Es wurde ein alternativer Link gefunden, egal wie lange er dauert.
lreeder