Принадлежность одного прямоугольного параллелепипеда другому

[Wran]

Даны два прямоугольных параллелепипеда. Как определить может ли один из них содержаться в другом? Грани одного параллелепипеда не обязательно параллельны граням другого.

[gris]

Попробуйте вначале решить задачу для прямоугольников.
В общем-то варианта два: размещение с параллельными гранями, либо с наклоном. Естественно, пытаемся засунуть п-д меньшего объёма в больший.

[VPro]

Поверните оси вдоль сторон большего параллелепипеда и совместите его центр с началом координат. Тогда условия принадлежности точки $(x,y,z)$ этому параллелепипеду будут простыми: $|x|\le a,\,|y|\le b,\,|z|\le c$. Для того, чтобы второй параллелепипед был целиком внутри первого НиД, чтобы этим условиям удовлетворяли все его вершины.

[gris]

Даже в этом случае надо сравнивать стороны в порядке по возрастанию. Иначе $(1, 3, 5)$ не поместится в $(7,2,4)$.
Но мне кажется, что на входе задаются просто длины сторон, а поворачивать можно при размещении. Например, $(1, 1, 10)$ вполне поместится в $(9,9,9)$ .

[Alexu007]

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

Для паралелепипеда вычисления ещё сложнее, но принцип должен быть тот же.

[VPro]

gris в сообщении #596865 писал(а):

Даже в этом случае надо сравнивать стороны в порядке по возрастанию. Иначе $(1, 3, 5)$ не поместится в $(7,2,4)$.
Но мне кажется, что на входе задаются просто длины сторон, а поворачивать можно при размещении. Например, $(1, 1, 10)$ вполне поместится в $(9,9,9)$ .

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

[gris]

VPro, там есть слово "может". Но мне кажется, что ТС сам пока не определился

[Wran]

Цитата:

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

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

[gris]

Начните с самого простого. Отсортируйте длины каждого и проверьте, нельзя ли засунуть один в другой с параллельными гранями. Кстати, уточните, считается ли что можно параллелепипед засунуть в равный ему.

[Wran]

Решение для прямоугольников (a1 > a2, b1 < b2).
От того, что центры прямоугольников будут совпадать, плохо не будет. Поэтому считаем, что они совпадают. Тогда диагональ меньшего прямоугольника проходит через центр большего и делится этим центром пополам. Поэтому проводим отрезок, длина которого равна длине диагонали меньшего прямоугольника, концы которого лежат на больших сторонах большого прямоугольника, а центр совпадает с центром большого прямоугольника (провести такой отрезок можно). Дальше строим прямоугольный треугольник, гипотенуза которого - проведенный отрезок, а катеты равны сторонам меньшего прямоугольника (рис.). Если вершина с прямым углом вышла за границы большего прямоугольника, значит, один прямоугольник содержать другой не может. В противном случае может.

-- 19.07.2012, 13:25 --

Цитата:

Отсортируйте длины каждого и проверьте, нельзя ли засунуть один в другой с параллельными гранями.

Это я понял :)

Цитата:

Кстати, уточните, считается ли что можно параллелепипед засунуть в равный ему.

Да.

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

[VPro]

Wran в сообщении #596945 писал(а):

Цитата:

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

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

Тогда все просто. Пусть длину сторон прямоугольников $a_1, b_1, c_1$ и $a_2, b_2, c_2$. Сортируем каждую тройку по убыванию (можно и по возрастанию). Если после этого для каждой соответствующей пары чисел выполнено одно и то же неравенство, то меньший прямоугольник можно запихнуть в больший. В противном случае, если присутствуют неравенства разных знаков, то никакими поворотами один в другой уже не впихнешь.

[Wran]

Цитата:

Тогда все просто. Пусть длину сторон прямоугольников $a_1, b_1, c_1$ и $a_2, b_2, c_2$. Сортируем каждую тройку по убыванию (можно и по возрастанию). Если после этого для каждой соответствующей пары чисел выполнено одно и то же неравенство, то меньший прямоугольник можно запихнуть в больший. В противном случае, если присутствуют неравенства разных знаков, то никакими поворотами один в другой уже не впихнешь.

Например, параллелепипед со сторонами 1 1 200 легко поместится в параллелепипед со сторонами 199 199 199.

[VPro]

Да, действительно, не все так просто. Лишнее доказательство того, что интуиция иногда нагло врет.

[Alexu007]

1. Если прямоугольники расположены на одной оси, то можно вписать, если длина меньше (или равно) и ширина меньше (или равно) - это самый простой вариант.

2. Ось совпадает с большой диагональю - максимум можно уместить эту диагональ, при этом ширина будет равна нулю (линия). Больше диагонали вписать ничего нельзя.

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

Кстати, интересно, а как это решить (геометрию забыл, как и многое другое)? Допустим, дан большой прямоугольник со сторонами 1м и 0,5м. В него вписывается длинный и узкий с длинной стороной например 1,02м. Собсна это всё данные, которые мы имеем. Нужно определить максимальную ширину, которую может иметь этот узкий прямоугольник, чтобы не выходить за рамки большого.


С паралелепипедом расчёты сложнее (нужно будет считать все три плоскости), но принцип должен быть тот же.

[Alexu007]

О, даже картиночку нарыл. Только по условиям задачи мы не знаем угла Т. А = 100см, В = 50см, Х = 102см. Нужно найти У.