3D инвентаризации структуры данных отслеживания и алгоритм

Question

Краткое описание проблемы:

Мы должны следить за инвентаризацию твердых трехмерных прямоугольников (я считаю, что эти называются кубоиды, но я стою исправиться).

Каждый кубоид имеет фиксированную длину, ширину и глубину. Скажем, это 20x5x5 для аргументации. Итак, для начала у нас есть 10 из этих 20x5x5 кубоидов.

После этого в ходе работы небольшие или второстепенные кубики с переменными размерами вырезаны из этих больших/первичных кубоидов.

Резюме вопроса:

A) Какая структура данных будет лучше отслеживать запас основного кубического наличия на складе.

B) Какой алгоритм (ы) лучше всего определить, может ли первичный кубик обслуживать вырезание вторичного кубоида?

Дополнительная информация и вопросы:

Первое сокращение от первичного параллелепипеда очень легко вычислить/определить. Проблема возникает со вторым, третьим и так далее разрезами, так как нам нужно отслеживать результирующие размеры всех ребер и вершин первичного кубоида, оставшегося на складе.

Если более одного первичного кубоида соответствует требованиям к второму кубоиду, наименьший первичный кубоид предпочтительнее, чтобы обеспечить истощение запасов FIFO. Поэтому нам нужно было бы рассчитать оставшийся объем всех совпадающих первичных кубоидов, чтобы определить, какая из них самая маленькая.

Это становится сложно, потому что после вырезания вторичного кубоида из первичного кубоида необходимо отслеживать новые переменные размеры основного кубоида (все ребра и вершины). Таким образом, нам нужно будет отслеживать точки на основном кубоиде, из которого вырезался вторичный кубоид (а также результирующая форма).

Так что это проблема как объема, так и проблема с этой штукой.

Следует добавить, что кубоиды измеряются и разрезаются до миллиметровой точности (в случае, если это имеет какое-либо значение для структуры данных).

Answer 1

У меня есть неполный ответ для вас, но это может быть полезно:

Прежде всего, here аналогичный вопрос, только в 2D.
Просмотрев один из ответов, кто-то упомянул ARC project. С первого взгляда кажется, что идея, обсуждавшаяся в 2D, может (может быть) применяться к вашей проблеме в 3D.

Я бы подумал, что применение любой идеи из проекта AC с ограничением на применение ко всем 3 измерениям может сработать.

В любом случае, я думаю, что это тот случай, балансирование между сложностью DS и времени потребуется для расчета ли не каждый кубовидной может быть разрезана для следующей части требуется ...