2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Принадлежность одного прямоугольного параллелепипеда другому
Сообщение18.07.2012, 21:54 
Даны два прямоугольных параллелепипеда. Как определить может ли один из них содержаться в другом? Грани одного параллелепипеда не обязательно параллельны граням другого.

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

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

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

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

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

 
 
 
 Re: Принадлежность одного прямоугольного параллелепипеда другому
Сообщение19.07.2012, 12:23 
gris в сообщении #596865 писал(а):
Даже в этом случае надо сравнивать стороны в порядке по возрастанию. Иначе $(1, 3, 5)$ не поместится в $(7,2,4)$.
Но мне кажется, что на входе задаются просто длины сторон, а поворачивать можно при размещении. Например, $(1, 1, 10)$ вполне поместится в $(9,9,9)$ .

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

 
 
 
 Re: Принадлежность одного прямоугольного параллелепипеда другому
Сообщение19.07.2012, 13:02 
Аватара пользователя
VPro, там есть слово "может". Но мне кажется, что ТС сам пока не определился :-)

 
 
 
 Re: Принадлежность одного прямоугольного параллелепипеда другому
Сообщение19.07.2012, 13:06 
Цитата:
Задача, как я понял, не в том, чтобы проверить, можно ли один прямоугольник поместить в другой (эта задача решается очень просто). Задача в том, чтобы проверить принадлежность для заданных (например, координатами вершин) прямоугольников.

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

 
 
 
 Re: Принадлежность одного прямоугольного параллелепипеда другому
Сообщение19.07.2012, 13:13 
Аватара пользователя
Начните с самого простого. Отсортируйте длины каждого и проверьте, нельзя ли засунуть один в другой с параллельными гранями. Кстати, уточните, считается ли что можно параллелепипед засунуть в равный ему.

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

-- 19.07.2012, 13:25 --

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

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

 
 
 
 Re: Принадлежность одного прямоугольного параллелепипеда другому
Сообщение19.07.2012, 18:54 
Wran в сообщении #596945 писал(а):
Цитата:
Задача, как я понял, не в том, чтобы проверить, можно ли один прямоугольник поместить в другой (эта задача решается очень просто). Задача в том, чтобы проверить принадлежность для заданных (например, координатами вершин) прямоугольников.

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

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

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

 
 
 
 Re: Принадлежность одного прямоугольного параллелепипеда другому
Сообщение20.07.2012, 09:08 
Да, действительно, не все так просто. Лишнее доказательство того, что интуиция иногда нагло врет.

 
 
 
 Re: Принадлежность одного прямоугольного параллелепипеда другому
Сообщение20.07.2012, 23:03 
1. Если прямоугольники расположены на одной оси, то можно вписать, если длина меньше (или равно) и ширина меньше (или равно) - это самый простой вариант.

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

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

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


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

 
 
 
 Re: Принадлежность одного прямоугольного параллелепипеда другому
Сообщение21.07.2012, 00:09 
Изображение
О, даже картиночку нарыл. Только по условиям задачи мы не знаем угла Т. А = 100см, В = 50см, Х = 102см. Нужно найти У.

 
 
 [ Сообщений: 16 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group