Как рассчитать площадь контакта одного прямоугольного кубоида с соседними кубоидами

Question

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

В грубой силе я ищу возможныйпозиция для каждого кубоида в пространстве, который не пересекается с другими кубоидами.Я понял это, используя класс BoundingBox в Java 3D, где можно проверить, пересекается ли данный блок с заданным набором других блоков.Теперь у меня есть много возможных мест, из которых мне нужно выбрать место с наибольшей площадью контакта с другими ячейками.

Моя проблема в том, что я не знаю, как эффективно рассчитать эту площадь.Небольшой пример ...

Блок 1: нижняя левая точка x = 0, y = 0, z = 0;верхняя правая точка x = 10, y = 10, z = 10

Рамка 2: левая нижняя точка x = 10, y = 0, z = 0;верхняя правая точка x = 15, y = 5, z = 5

Коробка 3 имеет те же размеры, что и коробка 1, и должна располагаться с максимальной площадью контакта

В этом примере все позиции, гдеодна сторона врезки 3 соответствует любой, кроме правой части врезки 1 (там, где находится врезка 2), являются оптимальными решениями.

Я был бы очень рад, если у кого-то есть идея или даже решение.Я также доволен бесплатными библиотеками, если они не слишком велики.

Спасибо!

Answer 1

Рассмотрим каждую потенциальную пару соприкасающихся граней по очереди.

Поместите блок 2 в любое место, где он контактирует с блоком 1. Затем вы выполняете рекурсивный поиск.Для каждого местоположения вы идентифицируете все пересекающиеся кубоиды, а затем находите минимальное движение вверх, вниз, влево и вправо, которое предотвратит пересечение с одним из этих пересекающихся кубоидов.Это создает четыре новых места для поиска.Затем вы также работаете с ними.

Чтобы уточнить, если вы двигаетесь влево, вы найдете крайнюю правую левую грань пересекающегося кубоида и двигаетесь так, чтобы грань больше не пересекалась.Другие кубоиды, вероятно, все еще будут пересекаться, но мы рекурсивно отойдем от них.

Если пересечений нет, у вас есть место остановки, и вы отмечаете область и продолжаете поиск.

Еслидвижение делает невозможным прикосновение к исходной рамке, вы не исследуете этот путь дальше.

Для каждого лица вы можете обнаружить, что либо места не существует, либо есть хотя бы одно с максимальнымконтакт для этого лица.

Затем повторите процедуру для остальных 5 лиц.