Задача:

Пересекаются ли отрезки. Для двух отрезков [latex]AB[/latex] и [latex]CD[/latex], заданных целочисленными координатами вершин в трёхмерном пространстве, определить имеют ли они общие точки.

Входные данные:

Координаты отрезков [latex]AB[/latex] и [latex]CD[/latex]:

[latex]A(x_1;y_1),B(x_2;y_2),C(x_3;y_3),D(x_4;y_4)[/latex].

Выходные данные:

Расположение отрезков [latex]AB[/latex] и [latex]CD[/latex] относительно друг друга:

1.  Прямые в разных плоскостях,
2.  Прямые параллельны,
3.  Отрезки находятся на одной прямой но не совпадают,
4.  Отрезки совпадают,
5.  Отрезки пересекаются,
6.  Отрезки не пересекаются;

Тесты:

№	Координаты [latex]A(x_1;y_1)B(x_2;y_2)C(x_3;y_3)D(x_4;y_4)[/latex]	Расположение отрезков
1	1 1 1  2 2 2  0 5 0  2 6 -1	Прямые в разных плоскостях
2	1 1 1  -1 -1 -1  0 0 -1  2 2 1	Прямые параллельны
3	1 1 0  2 2 1  4 4 3  5 5 4	Отрезки находятся на одной прямой но не совпадают
4	0 0 0  3 3 6  2 2 4  5 5 10	Отрезки совпадают
5	0 0 0  1 1 1  0 1 1  0 -1 -1	Отрезки пересекаются
6	0 0 1  1 1 1  5 -2 5  4 -1 4	Отрезки не пересекаются
7	1 0 0  1 1 0  0 0 1  1 0 1	Прямые в разных плоскостях
8	1 1 0  1 1 5  2 4 -1  2 4 1	Прямые параллельны
9	1 1 0  2 1 0  5 1 0  6 1 0	Отрезки находятся на одной прямой но не совпадают

 

10	-1 -1 -1  1 1 1  0 0 0  2 2 2	Отрезки совпадают
11	1 1 4  2 2 4  2 1 4  1 2 4	Отрезки пересекаются
12	1 0 3  1 3 3 2 2 3  4 4 3	Отрезки не пересекаются

Алгоритм решения:

Для решения задачи нам понадобятся следующие функции:

1.[latex]Mixed[/latex] — функция возвращающая значение смешанного произведения векторов

(Основная формула [latex]a_xb_yc_z+a_yb_zc_x+a_zb_xc_y-a_zb_yc_x-a_yb_xc_z-a_xb_zc_y [/latex])

2.[latex]Collinear[/latex] — функция принимающая координаты векторов, задаваемых отрезками, и возвращающая логическое значение true, если они коллинеарны, и false в противном случае.

(Основная формула [latex]\frac{a_x}{b_x}=\frac{a_y}{b_y}= \frac{a_z}{b_z}[/latex]  )

3.[latex]VectorEquation[/latex] — Функция принимающая координаты двух точек принадлежащих разным прямым и координаты направляющего вектора, и возвращающая логическое значение true, если они принадлежат одной прямой, и false в противном случае.

(Основная формула [latex]\frac{x — x_0}{V_x} =\frac{y — y_0}{V_y} = \frac{z — z_0}{V_z}[/latex] )

4.[latex]Min[/latex] — возвращает минимум двух чисел.

5.[latex]Max[/latex] –  возвращает максимум двух чисел.

6.[latex]CollinearforPerp[/latex] — функция принимающая координаты векторов, и возвращающая логическое значение true, если они коллинеарны, и false в противном случае. Используется в случае для формулы коллинеарности [latex]\frac{a_x}{b_x}=\frac{a_y}{b_y}= \frac{a_z}{b_z}[/latex] при [latex]b_x=0[/latex] , [latex]b_y=0[/latex] или [latex]b_z=0[/latex].

(Основная формула [latex]a_yb_z-a_zb_y = a_zb_x-a_xb_y = a_xb_y-a_yb_x = 0[/latex] )

Для удобства, заведем переменные для координат векторов соответствующих отрезкам. Первая проверка определяет чему равно смешанное произведение векторов. Если произведение равно [latex]0[/latex] то  векторы находятся в одной плоскости, в противном случае — в разных.

Далее проверяем является ли какой либо вектор перпендикулярным какой-либо оси. Это необходимо так как в таком случае координаты вектора [latex] \vec{CD}[/latex] равны нулю, что недопустимо при делении функций на координаты данного вектора.

В случае если какой либо вектор перпендикулярный какой-либо оси, проверяем их коллинеарность по формуле [latex]CollinearforPerp[/latex]:

[latex]a_yb_z-a_zb_y = a_zb_x-a_xb_y = a_xb_y-a_yb_x = 0[/latex]

 

Если векторы коллинеарны то они параллельны в том случае, если координата вектора перпендикулярного некой оси не равна координате другого вектора той же оси [latex](X_c=X_d and X_a \neq X_c)[/latex] [latex]||[/latex] [latex](Y_c=Y_d and Y_a \neq Y_c)[/latex] [latex]||[/latex] [latex](Z_c=Z_d and Z_a \neq Z_c)[/latex] . В противном случае прямые совпадают. Отрезки также совпадают если одна из координат одного отрезка находится между большим и меньшем значением координат другого отрезка, для всех осей:

[latex](Min(X_a,X_b)[/latex] [latex]\le[/latex] [latex]X_c and Max(X_a,X-b)[/latex] [latex]\ge[/latex] [latex]X_c)[/latex] [latex]||[/latex] [latex](Min(X_a,X_b)[/latex] [latex]\le[/latex] [latex]X_d and Max(X_a,X_b)[/latex] [latex]\ge[/latex] [latex]X_d)[/latex] [latex]||[/latex] [latex](Min(X_c,X_d)[/latex] [latex]\le[/latex] [latex]X_a and Max(X_c,X_d)[/latex] [latex]\ge[/latex] [latex]X_a)[/latex] [latex]||[/latex] [latex](Min(X_c,X_d)[/latex] [latex]\le[/latex] [latex]X_b and Max(X_c,X_d)[/latex] [latex]\ge[/latex] [latex]X_b)[/latex]

 

В противном случае отрезки находятся на одной прямой но не совпадают.

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

[latex](Min(X_a,X_b)[/latex][latex]\le[/latex][latex]X_c and Max(X_a,X_b)[/latex] [latex]\ge[/latex] [latex]X_c)[/latex] [latex]||[/latex] [latex](Min(X_a,X_b)[/latex] [latex]\le[/latex] [latex]X_d and Max(X_a,X_b)[/latex] [latex]\ge[/latex] [latex]X_d)[/latex] [latex]||[/latex] [latex](Min(X_c,X_d)[/latex] [latex]\le[/latex] [latex]X_a and Max(X_c,X_d)[/latex] [latex]\ge[/latex] [latex]X_a)[/latex] [latex]||[/latex] [latex](Min(X_c,X_d)[/latex] [latex]\le[/latex] [latex]X_b and Max(X_c,X_d)[/latex] [latex]\ge[/latex] [latex]X_b)[/latex]

 

Если же ни один вектор не перпендикулярен ни одной оси, проверяем вектора на коллинеарность стандартным способом ([latex]\frac{a_x}{b_x}=\frac{a_y}{b_y}= \frac{a_z}{b_z}[/latex])

Для коллинеарных векторов используем функцию VectorEquation которая возвращает логическое значение true, если точка одного отрезка принадлежит прямой другому, и false если векторы перпендикулярны. Проверка на совпадение отрезков проводиться аналогично первому случаю.

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

 

Ссылка на код программы

Ссылка на условие задачи

Related Images: