Aus Platzgründen pflege ich meine leeren Wasserflaschen immer zusammenzudrücken. Heute kam dabei die Frage auf, wie sich der den entstandenen unregelmäßigen dreidimensionalen Körper umgebende Quader mit dem minimalen Volumen eindeutig bestimmen ließe. Geht das, und wenn ja, wie?
Klingt schonmal ziehmlich NP-hart [img]
http://www.fb18.de/gfx/25.gif[/img]
In der Mathematik findest du sowas unter dem Stichwort "Kachelung" oder "Parkettierung", allerdings meine ich, mich zu erinnern, dass dabei keine Lücken bleiben dürfen, was bei deinem Problem durchaus erlaubt wäre.
Wahrscheinlich scheitert es in der Praxis schon daran, dass du keine Lust haben wirst, die möglichen Formen der einzelnen zerdrückten Flaschen exakt zu beschreiben, was für einen Algorithmus wohl unvermeidbar ist…
Du kannst dich natürlich auf einzelne Prototypen beschränken, das nimmt schonmal einen Teil der Unendlichkeit aus der Komplexität ;-)
Einfacher erscheint es mir, alle Flaschen, die du hast, in eine Spezial-Müll-Presse zu stecken, die die enthaltenen Flaschen immer zu einem eindeutig bestimmten Würfel der Größe 10 * 10 * 10 cm³ zusammenquetscht. [img]
http://www.fb18.de/gfx/24.gif[/img]
Einfacher erscheint es mir, alle Flaschen, die du hast, in eine Spezial-Müll-Presse zu stecken, die die enthaltenen Flaschen immer zu einem eindeutig bestimmten Würfel der Größe 10 * 10 * 10 cm³ zusammenquetscht. [img]http://www.fb18.de/gfx/24.gif[/img]
Wie wäre es mit einer kleinen, privaten Verbrennungsanlage? [img]
http://www.fb18.de/gfx/28.gif[/img] Da freuen sich die Nachbarn bestimmt.
Wie wäre es statt dessen mit SodaClub o.ä.? Das spart nicht nur Geld, Platz und Transportaufwand, sondern auch Müll – wodurch sich dein Problem gar nicht erst stellen dürfte.
Wie wäre es statt dessen mit SodaClub o.ä.? Das spart nicht nur Geld, Platz und Transportaufwand, sondern auch Müll – wodurch sich dein Problem gar nicht erst stellen dürfte.
Schrecklich, diese Abzockerei – erst muss man das Geraet kaufen, dann die Gascontainer. Dann passt in die Wasserflaschen kaum was rein, und das fertige Produkt ist immer im entscheidenden Moment alle. Dann ist natuerlich irgendwann (bald) der Gascontainer alle und man muss ein paar Tage warten, bis man einen neuen besorgt hat. Und dann hat man auch immer noch die ganze Arbeit.
Da lob ich mir doch die gute alte Aldi-Mineralwasserflasche, 1.5l fuer 17 Cent oder sowas :)
Wenn man nicht ständig aus der Flasche nuckelt, kann man die auch recht problemlos einige Male über den Wasserhahn nachfüllen. Das spart dann auch gleich das Anschleppen der Wasserflaschen.
Einfacher erscheint es mir, alle Flaschen, die du hast, in eine Spezial-Müll-Presse zu stecken, die die enthaltenen Flaschen immer zu einem eindeutig bestimmten Würfel der Größe 10 * 10 * 10 cm³ zusammenquetscht. [img]http://www.fb18.de/gfx/24.gif[/img]
Wie wäre es mit einer kleinen, privaten Verbrennungsanlage? [img]http://www.fb18.de/gfx/28.gif[/img] Da freuen sich die Nachbarn bestimmt.
Den Rausch gibt es gratis dazu!
Wahrscheinlich scheitert es in der Praxis schon daran, dass du keine Lust haben wirst, die möglichen Formen der einzelnen zerdrückten Flaschen exakt zu beschreiben, was für einen Algorithmus wohl unvermeidbar ist…
Kann man nicht "Big-O"-Mässig davon ausgehen, dass alle Flaschen höchstens die Größe einer Kugel mit dem-und-dem Duchmesser haben und damit rechnen?
Tomek
Dafür gibt es einen Algorithmus mit O(n^3): Joseph O'Rourke "Finding Minimal Enclosing Boxes", International Journal of Computer and Information Sciences, vol. 14, no. 3, pp. 183-199, Juni 1985.
Das Verfahren ist wohl allerdings zu kompliziert und zu langsam um für die praktische Arbeit interessant zu sein. Wenn dich eine gute Näherung auch zufrieden stellt, gibts auch einfachere und schnellere Möglichkeiten. Zu "Fitting OBB" (Oriented Bounding Box) gibts bestimmt was bei Google.
Wahrscheinlich scheitert es in der Praxis schon daran, dass du keine Lust haben wirst, die möglichen Formen der einzelnen zerdrückten Flaschen exakt zu beschreiben, was für einen Algorithmus wohl unvermeidbar ist…
Kann man nicht "Big-O"-Mässig davon ausgehen, dass alle Flaschen höchstens die Größe einer Kugel mit dem-und-dem Duchmesser haben und damit rechnen?
Tomek
Dann wirst du eine Obergrenze, aber nicht unbedingt das Optimum finden. D.h. für das gegebene Problem ist dieser Weg nicht möglich.
Algorithmus mit O(n^3): Joseph O'Rourke "Finding Minimal Enclosing Boxes"
Das hätte ich nicht gedacht. O(n³) erscheint mir verdammt schnell!
Allerdings lese ich gerade
"O Rourke, who presented an O(n³) algorithm for the three dimensional problem of computing the smallest rectangular box enclosing a convex polytope."
(n ist dabei übrigens die Anzahl der Knoten des konvexen Polytopes.)
Ist das überhaupt das gefragte Problem? Es geht doch nicht darum, eine konkrete Flasche zu umhüllen, sondern statt dessen viele konkrete Flaschen so anzuordnen, dass sie das "kleinstquadrige" Volumen einnehmen.
Ist das überhaupt das gefragte Problem? Es geht doch nicht darum, eine konkrete Flasche zu umhüllen
Doch, genau das war meine anfängliche Fragestellung.
Vielen Dank für die Paper-Tipps!
