Помощь - Поиск - Пользователи - Календарь
Полная версия: Пересечение отрезков
Форум «Всё о Паскале» > Образование и наука > Математика
Isaev
Вот переклинило меня на простой задаче:
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!
Isaev
Неужели никто не знает... Там вроде не сложно совсем... формулы забыл просто
Берётся 3 вектора
1. A1-A2
2. B3-B4
3. A2-B3
Затем их смешанное произведение - если оно равно нулю, то векторы пересекаются - если нет, то нет.
Студенты, помогите!
Michael_Rybak
Сначала проверяем, что они в одной плоскости - для этого вычисляем объем тетраэдра A1A2B3B4. Если в одной, решаем систему чтобы узнать, пересекаются ли.

Формулы можно нагуглить.
Isaev
Цитата(Michael_Rybak @ 3.10.2007 2:11) *

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

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


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

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

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 - в уравнение второй), получаем ответ.


Isaev
Цитата(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)?
Michael_Rybak
Цитата(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. На всякий случай еще раз: если определитель равен нулю, это еще не значит, что точка пересечения точно есть. А если точка пересечения *прямых* есть, это еще не значит, что *отрезки* пересекаются.

Пожалуйста, перечитай внимательно весь мой предыдущий пост.
Isaev
Цитата(Michael_Rybak @ 3.10.2007 17:09) *

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

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

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

на что это может повлиять?
Michael_Rybak
Цитата(Isaev @ 3.10.2007 20:38) *

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


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


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

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

Если же такая ситуация гарантированно невозможна, то можно заведомо отбросить *любое* из трех уравнений, потому что каждое является в таком случае следствием двух других (из-за того, что максимальный ранг равен 2, и нет нулевых строк).
Isaev
Наконец-то реализовал...
Всем огромное спасибо!

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