groesstes Rechteck innerhalb eines Polygons/Shape finden..?

[sirbender]

Hi,

Nehmen wir an ich habe ein Polygon/Shape in Java und will das flaechenmaessig groesste Rechteck finden das da reinpasst. Die optimale Loesung ist nicht noetig ausser die findet sich schnell. Was wichtig ist ist Geschwindigkeit und ein gute sub-optimale Loesung.

Koennt ihr mir mit einer schnellen Loesung weiterhelfen?

Danke,
sb

 

[Marco13]

Könnte aufwändig sein. Ein erster, spontaner Gedanke wäre, ein Raster drüberzulegen, und in diesem Raster (für jeden Rasterpunkt???) ein FloodFill zu starten (das sich vielleicht auch nur "Rechteckig" ausbreiten kann???) ... müßte man mal genauer überlegen...

 

[ARadauer]

darf das rechteck gedreht sein?

 

[slawaweis]

Nehmen wir an ich habe ein Polygon/Shape in Java und will das flaechenmaessig groesste Rechteck finden das da reinpasst. Die optimale Loesung ist nicht noetig ausser die findet sich schnell. Was wichtig ist ist Geschwindigkeit und ein gute sub-optimale Loesung.

Koennt ihr mir mit einer schnellen Loesung weiterhelfen?

die Aufgabe ist nicht trivial, vor allem wenn noch konkave Polygone hinzukommen. Ich kenne mich mit Geometrie und Java ziemlich gut aus, aber so eine Aufgabe ist mir neu. Kannst Du mal bitte den Kontext dazu beschreiben, vielleicht hast Du einfach den falschen Ansatz gewählt.

Ansonsten wäre das schnellste und unsauberste die Monte-Carlo-Methode. D.h. man erstellt sich eine Reihe Rechtecke und testet die Schnittmenge mit dem Shape. Die geringste Schnittmenge gewinnt. Dazu setzt man sich noch einen Maximalwert, wie oft so ein Vergleich durchgeführt wird. Funktioniert aber nur bei konvexen Polygonen.

Monte-Carlo-Algorithmus ? Wikipedia

Slawa

 

[sirbender]

darf das rechteck gedreht sein?

Jup, darf gedreht sein.

 

[Marco13]

Dann fällt das mit dem Raster schon mal weg... Selbst wenn man davon ausgeht, dass die Fläche als Polygon (d.h. ohne Bezierkuven, bzw. eben diese durch ein Polygonline angenähert) gegeben ist, würde ich sagen, dass das RICHTIG schwer sein kann, wenn man es "analytisch" lösen will. Eigentlich wäre irgendwas stochastisches (Monte Carlo bzw. sowas wie Genetic Algorithms oder Simulated Annealing) da vielleicht gar nicht verkehrt. Wenn es wirklich SCHNELL sein soll tritt dann das Problem (oder der postivie Effekt) auf, dass diese Verfahren i.a. die Lösungen immer weiter verbessern, und man dann zwischen Qualität und Geschwindigkeit wählen kann.