Welche Datenstruktur ?
-
Hallo,
ich versuche´momentan einen 3D Bin Packing Algorithmus zu implementieren. Dabei geht es darum, Boxen in einen Karton zu packen. Nun suche ich nach einer geeigneten Datenstruktur, in der ich die Leerräume verwalten kann.
Zuerst habe ich es in Listen gespeichert, hat allerdings den Nachteil, dass ich so nur so schwer abchecken kann, ob zwei Leerräume nebeneinander liegen, und evtl. verbunden werden könnten.
Als nächstes habe ich es mit einem 3-dimensionalen Array versucht, mit Einträgen 1, falls ein Platz belegt und 0 falls er frei ist. Das spiegelt die Wirklichkeit zwar schön wieder, aber leider ist es viel zu groß, so dass die Suche nach Leerräumen einer bestimmten Größe zu lang dauert.Nun meine Frage, gibt es eine (nicht zu komplizierte) Datenstruktur in der so etwas leichter + schneller realisierbar ist? Hatte an Octrees gedacht, hänge momentan aber daran, dass ich nicht mal weiss wie ich dort meine Boxen eintragen soll.
Vielen Dank im Voraus,
lg,
Chrissi