On Tue, 07 May 2002 16:26:15 +0200, Torsten Werner wrote:
Am Dienstag, dem 07. Mai 2002 um 14:14:31, schrieb Andreas Kretschmer:
kennt jemand ein Programm, in dem ich eine beliebige Form, z.B. Sechseck, mit Maßen etc. beschreiben kann und das Programm mir dann die Fläche des umschließenden Rechteckes ermittelt?
Kein Programm, aber das Algorithmus ist u. U. trivial:
(\max x_i - \min x_i) * (\max y_i - \min y_i)
Das ist nur sinnvoll, wenn die Kanten des umschießenden Rechtecks zwingend parallel zur x- und y-Achse liegen müssen. Wenn "schräge" Rechtecke erlaubt sind, bzw. die zu umschließende Fläche gedreht werden darf, kommt man u.U. mit einer viel kleineren Fläche aus. Oft geht es um Zuschnitte und da darf man drehen.
Der Algorithmus zur Bestimmung der Fläche hängt von den zulässigen Formen ab. Für konvexe Flächen steht in http://www.magic-software.com/Documentation/MinBox2.pdf ein einleuchtender Algorithmus. Er probiert alle Rechtecke durch, bei denen die Kanten parallel/senkrecht zu einer Seite des zu umschließenden Polygons sind. Eins davon ist das minimale. Das Paper beweist auch, warum nur diese Rectecke in Frage kommen.
Für nicht konvexe Flächen kann man in einem ersten Schritt eine konvexe Hülle ermitteln und dann wie oben fortfahren.
Sonst frage mal google nach "minimum bounding rectangle"
Reinhard