Задача:
Пересекаются ли отрезки. Для двух отрезков [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] относительно друг друга:
- Прямые в разных плоскостях,
- Прямые параллельны,
- Отрезки находятся на одной прямой но не совпадают,
- Отрезки совпадают,
- Отрезки пересекаются,
- Отрезки не пересекаются;
Тесты:
№ | Координаты [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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
#include <iostream> using namespace std; double Mixed(double ax, double ay, double az, double bx, double by, double bz, double cx, double cy, double cz){ return (ax*by*cz)+(ay*bz*cx)+(az*bx*cy)-(az*by*cx)-(ay*bx*cz)-(ax*bz*cy); // Формула смешаного произведения, если = 0, то одна плоскость } bool Collinear(double ax, double bx, double ay, double by, double az, double bz){ return ((ax/bx) == (ay/by) && (ay/by) == (az/bz)) ? true:false; // Коллинеарность } bool VectorEquation(double x, double x0, double y, double y0, double z, double z0, double Vx, double Vy, double Vz){ return (x - x0)/Vx == (y - y0)/Vy && (y - y0)/Vy == (z - z0)/Vz ? true:false; // уравнение прямой в пространстве } double Min(double X1, double X2){ return X1 < X2 ? X1:X2; } double Max(double X1, double X2){ return X1 > X2 ? X1:X2; } bool CollinearforPerp(double ax, double ay, double az, double bx, double by, double bz){ // Условие коллинеарности при bx,by,bz=0 return ((ay*bz-az*by == 0) && (az*bx-ax*by == 0) && (ax*by-ay*bx == 0)) ? true:false; } int main() { double Xa, Ya, Za, Xb, Yb, Zb, Xc, Yc, Zc, Xd, Yd, Zd; // Координаты концов отрезков cin >> Xa >> Ya >> Za >> Xb >> Yb >> Zb >> Xc >> Yc >> Zc >> Xd >> Yd >> Zd; double VectorABx, VectorABy, VectorABz, VectorCDx, VectorCDy, VectorCDz, VectorACx, VectorACy, VectorACz; //Координаты векторов VectorABx = Xb-Xa; VectorABy = Yb-Ya; VectorABz = Zb-Za; VectorCDx = Xd-Xc; VectorCDy = Yd-Yc; VectorCDz = Zd-Zc; VectorACx = Xc-Xa; VectorACy = Yc-Ya; VectorACz = Zc-Za; if (Mixed(VectorABx, VectorABy, VectorABz, VectorCDx, VectorCDy, VectorCDz, VectorACx, VectorACy, VectorACz) == 0){ // Смешанное произведение if(Xc == Xd || Yc == Yd || Zc == Zd){ // Частный случай, если прямая перпендикулярна какой-либо оси if(CollinearforPerp(VectorABx,VectorABy,VectorABz,VectorCDx,VectorCDy,VectorCDz)){ // Прямые Коллинеарны if((Xc == Xd && Xa != Xc) || (Yc == Yd && Ya != Yc) || (Zc == Zd && Za != Zd)){ // Условие параллельности cout << "Прямые параллельны" << endl; } else{ if(((Min(Xa,Xb) <= Xc && Max(Xa,Xb) >= Xc) ||(Min(Xa,Xb) <= Xd && Max(Xa,Xb) >= Xd))||(((Min(Xc,Xd) <= Xa && Max(Xc,Xd) >= Xa) ||(Min(Xc,Xd) <= Xb && Max(Xc,Xd) >= Xb)))){ if(((Min(Ya,Yb) <= Yc && Max(Ya,Yb) >= Yc) ||(Min(Ya,Yb) <= Yd && Max(Ya,Yb) >= Yd))||(((Min(Yc,Yd) <= Ya && Max(Yc,Yd) >= Ya) ||(Min(Yc,Yd) <= Yb && Max(Yc,Yd) >= Yb)))){ if(((Min(Za,Zb) <= Zc && Max(Za,Zb) >= Zc) ||(Min(Za,Zb) <= Yd && Max(Za,Zb) >= Zd))||(((Min(Zc,Zd) <= Za && Max(Zc,Zd) >= Ya) ||(Min(Zc,Zd) <= Zb && Max(Zc,Zd) >= Zb)))){ cout << "Отрезки совпадают" << endl; // Пресечение отрезков } else cout << "Отрезки находятся на одной прямой но не совпадают" << endl; } else cout << "Отрезки находятся на одной прямой но не совпадают" << endl; } else cout << "Отрезки находятся на одной прямой но не совпадают" << endl; } } else{ if(((Min(Xa,Xb) <= Xc && Max(Xa,Xb) >= Xc) ||(Min(Xa,Xb) <= Xd && Max(Xa,Xb) >= Xd))||(((Min(Xc,Xd) <= Xa && Max(Xc,Xd) >= Xa) ||(Min(Xc,Xd) <= Xb && Max(Xc,Xd) >= Xb)))){ if(((Min(Ya,Yb) <= Yc && Max(Ya,Yb) >= Yc) ||(Min(Ya,Yb) <= Yd && Max(Ya,Yb) >= Yd))||(((Min(Yc,Yd) <= Ya && Max(Yc,Yd) >= Ya) ||(Min(Yc,Yd) <= Yb && Max(Yc,Yd) >= Yb)))){ if(((Min(Za,Zb) <= Zc && Max(Za,Zb) >= Zc) ||(Min(Za,Zb) <= Yd && Max(Za,Zb) >= Zd))||(((Min(Zc,Zd) <= Za && Max(Zc,Zd) >= Ya) ||(Min(Zc,Zd) <= Zb && Max(Zc,Zd) >= Zb)))){ cout << "Отрезки пересекаются" << endl; } else cout << "Отрезки не пересекаются" << endl; } else cout << "Отрезки не пересекаются" << endl; } else cout << "Отрезки не пересекаются" << endl; } return 0; } else{ if (Collinear(VectorABx, VectorCDx, VectorABy, VectorCDy, VectorABz, VectorCDz)){ // Прямые коллинеарны if(VectorEquation(Xa, Xc, Ya, Yc, Za, Zc, VectorCDx, VectorCDy, VectorCDz)){ // Совпадение прямых if((Min(Xa,Xb) <= Xc && Max(Xa,Xb) >= Xc) ||(Min(Xa,Xb) <= Xd && Max(Xa,Xb) >= Xd)){ // Совпадение отрезков cout<< "Отрезки совпадают" << endl; } else{ cout << "Отрезки на одной прямой но не совпадают" << endl; } } else{ cout << "Прямые параллельны" << endl; } } else{ if(((Min(Xa,Xb) <= Xc && Max(Xa,Xb) >= Xc) || (Min(Xa,Xb) <= Xd && Max(Xa,Xb) >= Xd))||(((Min(Xc,Xd) <= Xa && Max(Xc,Xd) >= Xa) ||(Min(Xc,Xd) <= Xb && Max(Xc,Xd) >= Xb)))){ cout << "Отрезки пересекаются" << endl; } else cout << "Отрезки не пересекаются" << endl; } } } else{ cout << "Прямые в разных плоскостях" << endl; } return 0; } |
Алгоритм решения:
Для решения задачи нам понадобятся следующие функции:
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 если векторы перпендикулярны. Проверка на совпадение отрезков проводиться аналогично первому случаю.
Когда вектора не коллинеарны, прямые пересекаются. Проверка на пересечение отрезков проводиться аналогично первому случаю.