Как проверить, помещается ли коробка в другую коробку (разрешено любое вращение)

Предположим, что у меня есть две коробки (каждая из них представляет собой прямоугольный параллелепипед также известный как прямоугольный параллелепипед). Мне нужно написать функцию, которая решает, может ли поле с размерами (a, b, c) вставляться в ящик с размерами (A, B, C), если допускаются любые повороты по любым углам (не только на 90 °).

Сложная часть - это края внутреннего блока, которые могут быть не параллельны соответствующим краям внешнего. Например, коробка, которая очень тонкая в размерах (a, b), но с длиной 1 < c < √3 может вставляться в единичный куб (1, 1, 1), если он расположен по его главной диагонали.

Я видел вопросы [1], [2], но они, похоже, охватывают только повороты на 90 °.

Ответ 1

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

Ответ 2

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

2D-кейс: Для коробок X=(2A,2B) и X=(2A,2B), расположенных вокруг (0,0). Это означает, что углы X равны (+-A, +-B).

 ---------(A,B)
            |
 -----------(a,b)
(0,0)         |
 -----------(a,-b)
            |
 ---------(A,-B)

Вращаться X вокруг (0,0), углы всегда находятся на круге C с радиусом sqrt(a^2+b^2). Если часть круга лежит внутри коробки X, а если часть внутри X имеет достаточную длину дуги, чтобы разместить 2 точки на расстоянии 2a или 2b, чем X может поместиться внутри X. Для этого нам нужно рассчитать пересечение C с линиями x=A и y=B и рассчитать расстояние между этими пересечениями. Если расстояние равно или больше, чем 2a или 2b, чем X может помещаться внутри X.

3D-пример:. Для ящиков X=(2A,2B,2C) и X=(2A,2B,2C), расположенных вокруг (0,0,0). Вращая X вокруг (0,0,0), все углы перемещаются по сфере с радиусом sqrt(a^2+b^2+c^2). Чтобы увидеть, достаточно ли места на участке пересечения сферы, найдите пересечение сферы с плоскостями x=A, y=B и z=C, и проверьте, достаточно ли места для любого из квадов (2a,2b), (2a,2c) или (2b,2c) на этой сфере. Достаточно проверить точки на частичной границе на достаточном расстоянии. Для этой части я не уверен в эффективном подходе, возможно, найти "центр" части пересечения и проверить ее расстояние до границы, может помочь.

Ответ 3

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

Во-первых, есть 4 случая с 3 параллельными осями. Если какой-либо из них проходит (с помощью теста @jean), вы подойдете. В противном случае перейдите к следующим тестовым примерам:

Далее, есть 18 2-х диагональных случаев, где одна ось параллельна, а две другие диагональны с одной степенью свободы угла. Откажитесь от случая, если параллельная ось не подходит; в противном случае найти минимум некоторой "ударной" метрической функции одного угла поворота. Затем проверьте на предмет фактического удара по этому углу. Метрика удара должна быть некоторой непрерывной мерой того, как внутренний ящик (4 угла) находится внутри двух сторон наружной коробки, что позволяет им иногда выходить наружу во время поиска минимального угла удара. Надеемся, что а) есть предсказуемое максимальное количество минимумов и, надеюсь, б) если есть возможная подгонка, то подгонка гарантируется под углом одного из этих минимумов.

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

Не очень элегантный, я думаю. Это похоже на другой поток, спрашивающий, как долго строка заданной ширины может вписываться в поле 2d заданных размеров. Я не рассматривал там случай с параллельной осью, но диагональный случай требует решения квартильного уравнения (гораздо хуже квадратичного уравнения). У вас может быть аналогичная проблема для ваших случаев с одной параллельной осью, если вы хотите пойти аналитиком, а не искать минимумы показателя удара. Аналитическое решение для 3d-диагональных случаев без параллельной оси, вероятно, предполагает решение (для правильного корня) уравнения еще более высокого порядка.

Ответ 4

Фактически любое поле A с размерами (a1, a2, a3) может входить в другой блок B с размерами (b1, b2, b3) в следующих условиях:

i) Каждое ai меньше или равно каждому bi с я = 1. 2. 3;

ii) Любое ai должно быть меньше или равно sqrt (b1 ^ 2 + b2 ^ 2 + b3 ^ 2), главной диагонали B (diagB). Любое поле A с одним из его размеров, равным diagB, имеет два других размера, равные 0, так как любая плоскость, ортогональная ему, будет выходить за пределы поля B.

iii) Сумма a1, a2 и a3 должна быть меньше или равна diagB.

Из них видно, что наибольшая размерность ai квадрата A для него, чтобы он соответствовал блоку B, заданному ai > bi, должен лежать в интервале (bi, diagB). Таким образом, любая коробка с одним размером, большим любого размера ящика, содержащего его, обязательно будет размещена вдоль последней главной диагонали.

Проще говоря: A (a1, a2, a3) вписывается в B (b1, b2, b3), если a1 + a2 + a3 <= diagB.

Ответ 5

Можете ли вы получить размеры коробки? Скажем, a0, a1, a2 - размеры блока A, упорядоченные по размеру, а b0, b1, b2 - размеры блока B, упорядоченного по размеру.

A находится внутри B, если (a0 <= b0 AND a1 <= b1 AND a2 <= b2)