Ein begrenztes Rechteck innerhalb eines konkaven/konvexen Polygons finden

Question

Ich suche nach einer Methode, um ein achsenausgerichtetes Rechteck innerhalb eines konkaven oder konvexen Polygons zu finden.

Ich habe im Internet gesucht, die nächsten Lösungen, die ich finden konnte, würden nur ein konvexes und kein konkaves Polygon passen. Zum Beispiel -

Finding an axis-aligned rectangle inside a polygon

Um ehrlich zu sein, ich bin kein große Mathe wiz, also würde ich eher Codebeispiele oder eine Code-Bibliothek finden, aber ich glaube, ich könnte etwas Mathematik von mir handhaben, oder jemanden finden um mir dabei zu helfen.

Es wäre wirklich schön, wenn die Lösung auch in Java sein könnte, aber vielleicht bin ich zu gierig: P

bearbeiten: Als Antwort auf Russells Kommentar, ich bin ein bisschen mehr Informationen hinzufügen.

Das begrenzte Rechteck sollte so groß wie möglich sein. Das Rechteck soll Text darin enthalten. Maximal 1 bis 4 Wörter, mit Unterstützung für Textumbruch. Wenn es zum Beispiel zu dünn wäre, würde ich den Text vertikal statt horizontal platzieren. Für das Seitenverhältnis muss es also ausreichen, um 1-4 Wörter entweder vertikal oder horizontal mit Wortumbruch zu enthalten. Ich kann die Größe des Textes ändern, wenn das Rechteck klein ist, aber vorzugsweise sollte der Text so groß wie möglich sein. Eine andere Anforderung, die wünschenswert wäre, wäre, dass, wenn die allgemeine Ausrichtung des Polygons diagonal ist und der Text viel besser passt, wenn er diagonal ausgerichtet ist, dann das Rechteck nicht unbedingt mit der Achse "aber ausgerichtet" wäre stattdessen mit den diagonalen Linien des Polygons ausgerichtet sein. Ich denke, diese Nachfrage macht das wirklich schwierig, aber wenn ihr es für möglich hält, wäre es großartig!

Ich denke, ich habe jetzt alle Anforderungen abgedeckt. : P

Vielen Dank!

Answer 1

Da Sie dies für Text tun möchten, nehme ich an, Geschwindigkeit ist wichtig, Genauigkeit weniger wichtig. Ich schlage das dann vor:

1. Platzieren Sie das Polygon auf einem Raster mit Zellen proportional zu Textbemaßungen.
2. Entfernen Sie die Zellen an der Grenze mit Bresenham's line algorithm..
3. entfernen Zellen außerhalb der Grenzzellen (durch nach innen von den Kanten des Gitters zu arbeiten.
4. das maximale Rechteck auf den verbleibenden Zellen finden, beispielsweise das Verfahren here gezeigt.

Siehe auch Puzzle: Find largest rectangle (maximal rectangle problem).

EDIT: Ich habe gerade die Anfrage, dass dieser Algorithmus anpassen, wenn das Polygon in einem Winkel ausgerichtet ist. Mein Vorschlag ist, die principle axes des Polygons zu finden, um die Ausrichtung zu überprüfen, sie zu drehen, um die dominante Achse an der x-Achse auszurichten, und den obigen Algorithmus anzuwenden.

Auch möchte ich darauf hinweisen, dass "Entfernen einer Zelle" wirklich nur bedeutet, ein Bit in einem 2D-Array, das die Rasterzellen darstellt.

Answer 2

Ich habe einmal ein ähnliches System in einer sehr kluge Art und Weise implementiert, indem ich einfach nach möglichen Rechtecken suchte und Shape.contains() darauf verwendete. Es war etwas langsam - vielleicht 1s Layout für die Gettsburg Adresse in einem Oval - aber nützlich für statischen Text und für kleinen Text in einfachen Formen.

Wenn Sie interessiert sind, könnten Sie die JAR-Datei here entpacken und unter TextWrappingLayout aussehen. Es ist wahrscheinlich viel komplizierter als das, was Sie brauchen würden, denn anstatt in einem einzelnen Rechteck zu liegen, versucht es, jede Linie so nahe wie möglich am Rand zu platzieren, aber Sie können die Grundidee sehen.