Summary of problem:
We need to keep track of inventory of solid three dimensional rectangles (I believe these are called cuboids but I stand to be corrected).
Each cuboid arrives with a fixed length, breadth, and depth. Let's say it's 20x5x5 for argument's sake. So to begin, we have 10 of these 20x5x5 cuboids in stock.
Then during the course of business, smaller / secondary cuboids of variable dimensions are cut out from these bigger / primary cuboids.
Summary of question:
A) What data structure would be best to track stock of primary cuboid stock availability.
B) What algorithm(s) would be best to determine whether a primary cuboid can cater for a secondary cuboid cut out?
Additional details and issues:
The first cut from a primary cuboid is very easy to calculate / determine. The problem comes into hand with the second, third, and so on cuts, since we need to track the resulting dimensions of all edges and vertices of the primary cuboid remaining in stock.
If more than one primary cuboid meets the requirements for the secondary cuboid, the smallest primary cuboid is preferable so as to cater for FIFO depletion of stock. So we would need to calculate the remaining volume of all matching primary cuboids to determine which is the smallest one.
This gets tricky because once a secondary cuboid has been cut out from a primary cuboid, the primary cuboid's new variable dimensions need to be tracked (all edges and vertices). Thus we will need to keep track of the points on the primary cuboid that the secondary cuboid was cut out of (as well as the resulting shape).
So it's both a volume problem and a "does this piece fit in that piece" problem.
I should add that cuboids are measured and cut to millimetre precision (in case this has any implications for the data structure).
