geeignete Datenstruktur für dreidimensionale Raumbelegung

[Peter23]

Hallo zusammen,

mir stellt sich folgendes Problem: Ich habe eine Karton mit einer bestimmten Höhe, Breite und Tiefe und soll darin verschiedene Schachteln so anordnen, dass möglichst kein Platz verschwendet wird.

Zur Speicherung dieser Anordnung wollte ich ein dreidimensionales Array nutzen, also

new Schachtel[Höhe][Breite][Tiefe]

und dann für jede belegte Position eine Referenz auf die jeweilige Schachtel ablegen. Da die Maße in Millimeter angegeben sind, bekomme ich aber bereits bei der Erzeugung des Arrays eine OutOfMemory Exception. Mit Zentimetern klappt die Erzeugung.

Habe gelesen, dass man den Speicher der VM erhöhen kann, frage mich aber, ob es nicht insgesamt eine einfachere Alternativ gibt.

Vielen Dank schonmal und Gruß
Peter

 

[Ice-Tea]

java -jar -Xmx786M blabla.jar

EDIT:
ohh, sry hatte nicht bis zu ...alternative... gelesen

 

[0x7F800000]

Ich würde es nicht empfehlen, jeden Kubikmillimeter abzuspeichern. Es kommt mir nämlich genauso verschwenderisch vor, als ob du wenige rechteckige schachteln durch ein Modell mit zig milliarden klitzekleinen Atomen simulieren würdest.

Überlege dir stattdessen lieber, wie du einen Quader eben als Quader daretsellst, und nicht als einen haufen Kubikmillimeter-würfelchen.

Das geht. Um dann rauszufinden, ob auf bereits gestapelte Schachteln eine weitere irgendwie draufpasst, musst du sehr vorsichtig mit den elementaren + - min max funktionen den zur verfügung stehenden Platz ausrechnen. Es ist alles andere als trivial. Ich würde dir empfehlen, das erstmal auf 2D-Boxen auszuprobieren. Aber möglich ist es jedenfalls.

dann brauchst du für n boxen vielleicht n*6 float-werte zu speichern, da kannst du locker mit millionen boxen herumhantieren.

Wie man aber einen guten algorithmus schreibt, der diese Aufgabe erledigt: keine Ahnung.
Bruteforce wird aber ziemlich schnell überfordert sein, das versprech ich dir. Ich bin mir sogut wie 100% sicher, dass es NP ist.

 

[0x7F800000]

Und als geeignete datenstruktur würde ich spontan einen octree vorschlagen, wobei jeder Quader mehreren Leafs zugeordnet werden kann. Dann findest du schneller, welche leerräume in deiner schachten von welchen würfeln begrenzt werden, und brauchst dann nicht alle reingepackten würfel zu prüfen.

 

[Peter23]

Und als geeignete datenstruktur würde ich spontan einen octree vorschlagen

Danke erstmal für die Rückantwort. Gibt es diesen octree bereits als Klasse in Java?

 

[0x7F800000]

Zum Glück nicht
Das würde einem nämlich nur unnötige Interfaces aufzwingen. Das ist doch erstmal nur so ein Konzept, das muss je nach situation eh immer irgendwie anders umgesetzt werden.

edit: bzw doch, natürlich, mit einer an Gewissheit grenzender Sicherheit wurde sowas schon in Java geschrieben. Nicht in der Standard-API zumindest. Wenn du aber lange genug googlest wirst du irgendwann man fündig, nehme ich mal an.
Aber wozu brauchst du das... Selber schreiben ist doch 100 Mal schneller, als gedankengänge von irgendwelchen anderen Leuten nachzuvollziehen. (in diesem konkreten fall, versteht sich)