IPB
ЛогинПароль:

> Компиляция правил для данного раздела

1. Заголовок темы должен быть информативным. В противном случае тема закрывается и удаляется ...
2. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
3. Одна тема - один вопрос (задача)
4. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Пересечение отрезков, в 3D - пространстве
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 7
Пол: Мужской
Реальное имя: Isaev

Репутация: -  0  +


Вот переклинило меня на простой задаче:
3D пространство, 2 отрезка, заданные 4мя точками...
отрезок A, точки - A1(x1,y1,z1), A2(x2,y2,z2)
отрезок B, точки - B3(x3,y3,z3), B4(x4,y4,z4)
Как узнать:
1. пересекаются ли они?
2. если да, то найти точку пересечения C(x5,y5,z5)

Тривиальная задачка, но за 10 лет забыл всё нахрен
Помогите, please!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2





Группа: Пользователи
Сообщений: 7
Пол: Мужской
Реальное имя: Isaev

Репутация: -  0  +


Неужели никто не знает... Там вроде не сложно совсем... формулы забыл просто
Берётся 3 вектора
1. A1-A2
2. B3-B4
3. A2-B3
Затем их смешанное произведение - если оно равно нулю, то векторы пересекаются - если нет, то нет.
Студенты, помогите!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Сначала проверяем, что они в одной плоскости - для этого вычисляем объем тетраэдра A1A2B3B4. Если в одной, решаем систему чтобы узнать, пересекаются ли.

Формулы можно нагуглить.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4





Группа: Пользователи
Сообщений: 7
Пол: Мужской
Реальное имя: Isaev

Репутация: -  0  +


Цитата(Michael_Rybak @ 3.10.2007 2:11) *

Сначала проверяем, что они в одной плоскости - для этого вычисляем объем тетраэдра A1A2B3B4.

Это будет определитель 3-го порядка. Столбцами (строками) в этом определителе будут координаты трех, вышеуказанных векторов.
Вычислили... Теперь знаем, есть ли точка пересечения...
Как найти её координаты?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата
Вычислили... Теперь знаем, есть ли точка пересечения...


Не совсем. Если не в одной плоскости, то точки пересечения точно нет, если в одной - то может и есть.

Чтобы узнать, задаем прямые, содержащие отрезки, параметрически; для первой прямой:

x = A.x + (B.x - A.x) * t
y = A.y + (B.y - A.y) * t
z = A.z + (B.z - A.z) * t

Для второй аналогично.

Получаем систему:

A.x + (B.x - A.x) * t1 = C.x + (D.x - C.x) * t2
A.y + (B.y - A.y) * t1 = C.y + (D.y - C.y) * t2
A.z + (B.z - A.z) * t1 = C.z + (D.z - C.z) * t2

3 уравнения, 2 неизвестных. Система избыточна, но все три уравнения нужны на случай, если обе прямые параллельны какой-то из осевых плоскостей.

Решать ее лучше не вручную (если первое уравение имеет вид const = const то если константы разные, то решения нет, а иначе выбрасываем уравнение; а если один из коэффициентов (B.x - A.x) или (D.x - C.x) равен нулю, то сразу вычисляем соответственно t2 или t1 и смотрим куда подставить и т.д и т.д и т.д.), а просто полностью реализовать метод Гаусса.

Если решения нет - прямые параллельны. Если решений бесконечно много - прямые совпадают, и можно, например, проверить каждый конец каждого отрезка на принадлежность другому отрезку. Если решение единственно - прямые пересекаются, теперь проверяем условие 0 <= t1, t2 <= 1 чтобы узнать, принадлежит ли точка пересечения обоим отрезкам. Если да, подставляем t1 в параметрическое уравнение первой прямой (или t2 - в уравнение второй), получаем ответ.


 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6





Группа: Пользователи
Сообщений: 7
Пол: Мужской
Реальное имя: Isaev

Репутация: -  0  +


Цитата(Michael_Rybak @ 3.10.2007 14:28) *

Не совсем. Если не в одной плоскости, то точки пересечения точно нет, если в одной - то может и есть.

Ну так если определитель 3 порядка (он же "объем тетраэдра A1A2B3B4") равен нулю, значит полюбому в одной плоскости...
Цитата(Michael_Rybak @ 3.10.2007 14:28) *

Если решения нет - прямые параллельны.

Я бы сказал лежат в параллельных плоскостях

Система жестокая получилась...
Если допустить, что решение существует и причём только одно, как это свернётся?
Частный случай: A(5;7;4) B(9;17;16) C(7;14;2) D(7;10;18)
Если это нарисовать, то видим точку пересечения E(7;12;10)
Векторы: AB(4;10;12) CB(2;3;14) CD(0;-4;16)
Определитель 3 порядка: 4*(-4)*14+10*16*2+0*3*12-2*(-4)*12-0*10*14-3*16*4=-224+320+96-192=0 (точка пересечения точно есть)
Как выйти на её координаты E(7;12;10)?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата(Isaev @ 3.10.2007 17:43) *

Ну так если определитель 3 порядка (он же "объем тетраэдра A1A2B3B4") равен нулю, значит полюбому в одной плоскости...

Ну да. По-любому в одной. Но это совсем ведь не значит, что отрезки имеют общие точки.

Цитата(Isaev @ 3.10.2007 17:43) *

Я бы сказал лежат в параллельных плоскостях

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

Цитата(Isaev @ 3.10.2007 17:43) *

Система жестокая получилась...
Если допустить, что решение существует и причём только одно, как это свернётся?
Частный случай: A(5;7;4) B(9;17;16) C(7;14;2) D(7;10;18)
Если это нарисовать, то видим точку пересечения E(7;12;10)
Векторы: AB(4;10;12) CB(2;3;14) CD(0;-4;16)
Определитель 3 порядка: 4*(-4)*14+10*16*2+0*3*12-2*(-4)*12-0*10*14-3*16*4=-224+320+96-192=0 (точка пересечения точно есть)
Как выйти на её координаты E(7;12;10)?

Я уже на это ответил. Решить систему относительно t1 и t2 методом Гаусса и подставить значение t1 в параметрическое уравнение первой прямой. Откуда вообще система взялась понятно?

P.S. На всякий случай еще раз: если определитель равен нулю, это еще не значит, что точка пересечения точно есть. А если точка пересечения *прямых* есть, это еще не значит, что *отрезки* пересекаются.

Пожалуйста, перечитай внимательно весь мой предыдущий пост.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8





Группа: Пользователи
Сообщений: 7
Пол: Мужской
Реальное имя: Isaev

Репутация: -  0  +


Цитата(Michael_Rybak @ 3.10.2007 17:09) *

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

Перечитал... Всё, разобрался...

только не понял:
Цитата(Michael_Rybak @ 3.10.2007 17:09) *
3 уравнения, 2 неизвестных. Система избыточна, но все три уравнения нужны на случай, если обе прямые параллельны какой-то из осевых плоскостей.

на что это может повлиять?

Сообщение отредактировано: Isaev -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата(Isaev @ 3.10.2007 20:38) *

Цитата
3 уравнения, 2 неизвестных. Система избыточна, но все три уравнения нужны на случай, если обе прямые параллельны какой-то из осевых плоскостей.


на что это может повлиять?


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

Дело в том, что если обе прямые параллельны какой-то из осевых плоскостей, соответствующее уравнение в системе примет вид const = const, т.к. коэффициенты при t1 и t2 обратятся в 0. И тогда очевидно, что отбрасывать нужно именно его - если отбросить одно из двух других, система станет неполной вообще.

Если же такая ситуация гарантированно невозможна, то можно заведомо отбросить *любое* из трех уравнений, потому что каждое является в таком случае следствием двух других (из-за того, что максимальный ранг равен 2, и нет нулевых строк).
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10





Группа: Пользователи
Сообщений: 7
Пол: Мужской
Реальное имя: Isaev

Репутация: -  0  +


Наконец-то реализовал...
Всем огромное спасибо!

Просьба к Модераторам!
Поднять репутацию Michael_Rybak за подробный, развёрнутый ответ...
Сам не могу, т.к. маленький ещё smile.gif

Сообщение отредактировано: Isaev -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Чтоб не флеймить в теме smile.gif, внесу свои 5 копеек:
Цитата(Isaev @ 3.10.2007 18:43) *
Я бы сказал лежат в параллельных плоскостях
- две любые прямые в пространстве всегда лежат в параллельных плоскостях.
Цитата(Isaev @ 4.10.2007 2:40) *
Просьба к Модераторам!
Поднять репутацию Michael_Rybak за подробный, развёрнутый ответ...
Сам не могу, т.к. маленький ещё smile.gif
А ты давай, эта.. расти! smile.gif
А вообще, я сам хотел повысить репу Рыбаку пока читал, уже в середине темы. А в конце встретил твою просьбу, коюю и выполняю.. smile.gif Сделано..


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 23.09.2020 11:43
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name