Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Математика _ Пересечение отрезков

Автор: Isaev 2.10.2007 2:42

Вот переклинило меня на простой задаче:
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.10.2007 1:41

Неужели никто не знает... Там вроде не сложно совсем... формулы забыл просто
Берётся 3 вектора
1. A1-A2
2. B3-B4
3. A2-B3
Затем их смешанное произведение - если оно равно нулю, то векторы пересекаются - если нет, то нет.
Студенты, помогите!

Автор: Michael_Rybak 3.10.2007 7:11

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

Формулы можно нагуглить.

Автор: Isaev 3.10.2007 9:23

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

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

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

Автор: Michael_Rybak 3.10.2007 19:28

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


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

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

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 3.10.2007 21:43

Цитата(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 3.10.2007 22:09

Цитата(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 4.10.2007 0:38

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

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

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

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

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

Автор: Michael_Rybak 4.10.2007 4:31

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

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


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


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

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

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

Автор: Isaev 4.10.2007 5:40

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

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

Автор: Lapp 5.10.2007 8:03

Чтоб не флеймить в теме 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 5.10.2007 18:44

smile.gif