Пересечение цилиндров
Подскажите пожалуйста алгоритм, определяющий имеют ли два цилиндра пересечение (общий объем) в трехмерном пространстве.
Вот здесь немного теории http://physics.nad.ru/matboard/messages/13156.html а здесь немного практики http://www.codenet.ru/progr/opengl/opengl_04.phpа здесь разные решения http://vm.msun.ru/Scrypty.htm
ЗЫ: Гугл->Поиск->"Пересечение цилиндров" дает 11 страниц ссылок.
Вот здесь немного теории http://physics.nad.ru/matboard/messages/13156.html а здесь немного практики http://www.codenet.ru/progr/opengl/opengl_04.phpа здесь разные решения http://vm.msun.ru/Scrypty.htm
ЗЫ: Гугл->Поиск->"Пересечение цилиндров" дает 11 страниц ссылок.
Спасибо, но по этим ссылкам я уже ходил и алгоритма не нашел, может быть плохо смотрел.
Спасибо, но по этим ссылкам я уже ходил и алгоритма не нашел, может быть плохо смотрел.
Тебе сам алгоритм нужно составить или картинку нарисовать?
Подскажите пожалуйста алгоритм, определяющий имеют ли два цилиндра пересечение (общий объем) в трехмерном пространстве.
Какими параметрами заданы цилиндры?
Какими параметрами заданы цилиндры?
Высота, радиус основания, линейные и угловые координаты для каждого цилиндра. Необходимо узнать - имеют ли цилиндры общий объем (т.е. пересекаются ли в пространстве. Пример: подъемный кран работает вблизи трубы, есть ли столкновение балки крана с трубой). Сам объем считать не надо. Если есть известный алгоритм - буду очень признателен, если нет - не морочтесь, буду думать сам.
Есть цилиндры А и В.
Соединим их "центры" отрезком ОаОb и найдём точки пересечения этого отрезка с поверхностю каждого цилиндра: Pa и Pb.
Если точки расположены на отрезке в порядке Oa-Pa-Pb-Ob, то пересечения нет. Если же в порядке Oa-Pb-Pa-Ob, то пересечение есть.
Осталось только построить алгоритм поиска пересечения поверхности цилиндра с лучом, исходящим из его центра.
Подумаю ещё.
Высота, радиус основания, линейные и угловые координаты для каждого цилиндра. Необходимо узнать - имеют ли цилиндры общий объем (т.е. пересекаются ли в пространстве. Пример: подъемный кран работает вблизи трубы, есть ли столкновение балки крана с трубой). Сам объем считать не надо. Если есть известный алгоритм - буду очень признателен, если нет - не морочтесь, буду думать сам.
Циллиндры можно задать в виде систем уравнений, например, циллиндр вдоль оси Y:
{ x^2 + z^2 <= R^2
y1 <= y <= y2 }
При произвольном расположении циллиндров в пространстве эти системы решаются только численными методами. Долго, но решаются.
В компьютерной графике такие просчеты не выполняются (разве что только при трассировке лучей, но там это получается автоматически). Обычно такие объекты вписывают в фигуры, расчитать столкновение которых просто. Если вписать циллиндры в параллелепипеды - все решается очень просто и безопаснее для балки крана с трубой ;)
При произвольном расположении циллиндров в пространстве эти системы решаются только численными методами.
[COLOR=red][SIZE=4]Не читайте, всё, что я написал после этой фразы. Я бредил. <<<добавлено 5 марта 2005>>>[/SIZE][/COLOR]
Если Вы имеете в виду численные методы в смысле приближённых вычислений, то я с Вами не согласен.
Решение "в лоб" представляется тривиальным. План его следующий.
1. Переносим и поворачиваем систему координат так, чтобы цунтр цилиндра А располагался в начале координат, а его образующая была параллельна оси z.
2. Ищем пересечение образующей с лучом, соединяющим центры цилиндров. Пусть это точка Т1.
3. Ищем пересечения луча с плоскостями оснований цилиндров Т2 и Т3.
Это можно сделать, не прибегая к численным методам.
4. Выбираем из точек Т1,2,3 точку Та, которая действительно лежит на поверхности цилиндра А.
Это можно сделать несколькими IFами.
Это будет моя точка Ра, но только в преобразованных координатах.
5. Делаем [1..4] с цилиндром В и получаем точку Tb.
6. Возвращаем точки Ta и Tb в первоначальные координаты. Это будут мои точки Pa и Pb.
7. Анализируем взаимное расположение точек Oa-Pa-Pb-Ob.
Quod erat demonstrandum.
Нужно только сделать всё аккуратно.
Разве не так?
Однако, я уверен, что задача пересечения цилиндра и луча уже была кем-нибудь решена. На эту именно тему я и собирался подумать, а точнее посмотреть где-нибудь, что думают по этому поводу Ньютон, Лейбниц или, может быть, даже Пифагор с Евклидом...
Но вот инрересно, как из анализа точек Oa, Pa, Pb, Ob можно сделать вывод о пересечении цилиндров? Можно представить себе геометрию, где растояние (Oa, Pa) будет большим (Oa, Pb) и цилиндры не будут при этом пересекаться. Равно как и (Oa, Pa) < (Oa, Pb) и цилиндры пересекаются.
Можно подробнее про этот анализ?
Ну пересечение цилиндра и луча посчитать очень просто. Также придется делать отсечение внутри круга на произвольной плоскости, что тоже можно сделать.
Но вот инрересно, как из анализа точек Oa, Pa, Pb, Ob можно сделать вывод о пересечении цилиндров? Можно представить себе геометрию, где растояние (Oa, Pa) будет большим (Oa, Pb) и цилиндры не будут при этом пересекаться. Равно как и (Oa, Pa) < (Oa, Pb) и цилиндры пересекаются.
Можно подробнее про этот анализ?
Два выпуклые симметричные тела могут пересекаться только в случае, если точки их центров (Oa, Ob) и пересечений (Pa, Pb) находятся в порядке Oa-Pb-Pa-Ob.
Все остальные случаи расположения точек соответствуют тому, что тела либо не пересекаются, либо одно содержится внутри другого, либо ещё что-нибудь в этом духе.
Два выпуклые симметричные тела могут пересекаться только в случае, если точки их центров (Oa, Ob) и пересечений (Pa, Pb) находятся в порядке Oa-Pb-Pa-Ob.
Все остальные случаи расположения точек соответствуют тому, что тела либо не пересекаются, либо одно содержится внутри другого, либо ещё что-нибудь в этом духе.
что-то я не пойму этого алгоритма... откуда вообще взялось это утверждение?
на прилагаемом рисунке два пересекающихся цилиндра, которые попадают под условие
что-то я не пойму этого алгоритма... откуда вообще взялось это утверждение?
на прилагаемом рисунке два пересекающихся цилиндра, которые попадают под условие
Ё! xelos, Вы, конечно правы. Вчера в метро я тоже представил себе такой рисунок и понял, что [COLOR=red][SIZE=4]всё, что я написал — полная ерунда[/SIZE][/COLOR]. Прошу прощения у всех за потерянное время. :{ Видимо, я вчера был не в себе. Всё из-за Oracle...
Подскажите пожалуйста алгоритм, определяющий имеют ли два цилиндра пересечение (общий объем) в трехмерном пространстве.
Предполагаю примерно такой алгоритм: Найти кратчайшее расстояние между осями цилиндров, если оно больше суммы радиусов, то цилиндры точно не пересекаются. Если меньше, то возможен случай что цилиндры не скрещивающиеся, этот случай в принципе тоже не сложно доработать. Да ещё отдельно следует рассмотреть случай, если прямые осей пересекаются.
Стопроцентной гарантии не дает, но приблизительно можно. Нужно именно точно?
Ребята, тут выше было здравое предложение, вписать их в параллелепипеды. А потом проверять пересение каждой грани параллелепипеда со всеми гранями другого...
Стопроцентной гарантии не дает, но приблизительно можно. Нужно именно точно?
Точнее не в параллелепипеды, а в более многогранные фигуры.
Точнее не в параллелепипеды, а в более многогранные фигуры.
Да, согласен, но это всегда выбор между скоростью и точностью. Поэтому я и спросил насколько нужна точность...