Artykuł przedstawia algorytm sprawdzający, czy dwa odcinki przecinają się. Żeby dwa odcinki przecinały się musi zachodzić jeden z dwóch przypadków:
Do rozwiązania problemu przedstawiającego pierwszy podpunkt wykorzystamy iloczyn wektorowy. Jak w czasie stałym sprawdzić, czy dwa odcinki się przecinają?
Tworzymy wektor z odcinka AB, gdzie
$$A = (x_A, y_A), B = (x_B, y_B)$$
w następujący sposób:
$$\overrightarrow{AB}=[x_B-x_A, y_B-y_A]$$
gdzie $$[x_B-x_A, y_B-y_A]$$ to współrzędne wektora $$\overrightarrow{AB}$$. Następnie sprawdzamy, czy początek odcinka CD leży po jednej stronie prostej zawierającej odcinek AB a koniec po drugiej stronie. W tym celu wykorzystamy iloczyn wektorowy. Tworzymy dwa dodatkowe wektory $$\overrightarrow{AC}$$ oraz $$\overrightarrow{AD}$$. Jeśli punkty C i D będą leżały po przeciwnych stronach prostej AB iloczyny wektorowe $$\overrightarrow{AB}x\overrightarrow{AC}$$ oraz $$\overrightarrow{AB}x\overrightarrow{AD}$$ muszą być przeciwnych znaków, a więc ich iloczyn musi być liczbą ujemną. Następnie sprawdzamy, czy zachodzi ta sama sytuacja dla wektora $$\overrightarrow{CD}$$ i końców odcinka AB.
Jak liczymy iloczyn wektorowy? Załóżmy, że mamy wektor $$\overrightarrow{u}=[x_u,y_u]$$ oraz $$\overrightarrow{v}=[x_v,y_v]$$. Iloczyn wektorowy $$\overrightarrow{u}x\overrightarrow{v}$$ jest równy wyznacznikowi:
$$det \begin{vmatrix}x_u & x_v\\ y_u & y_v\end{vmatrix}=x_uy_v-x_vy_u$$
Jeśli iloczyn wektorowy jest równy zero, oznacza to, że rozpatrywane trzy punkty są współliniowe. Jedyne co należy sprawdzić w takiej sytuacji, to czy koniec jednego odcinka leży na drugim.
Rozwiązanie w C++
//algorytm.edu.pl
#include<iostream>
#define pkt pair<int, int>
using namespace std;
int iloczyn_wektorowy(pkt X, pkt Y, pkt Z)
{
int x1 = Z.first - X.first, y1 = Z.second - X.second,
x2 = Y.first - X.first, y2 = Y.second - X.second;
return x1*y2 - x2*y1;
}
//sprawdzenie, czy punkt Z(koniec odcinka pierwszego)
//leży na odcinku XY
bool sprawdz(pkt X, pkt Y, pkt Z)
{
return min(X.first, Y.first) <= Z.first && Z.first <= max(X.first, Y.first)
&& min(X.second, Y.second) <= Z.second && Z.second <= max(X.second, Y.second);
}
bool czy_przecinaja(pkt A, pkt B, pkt C, pkt D)
{
int v1 = iloczyn_wektorowy(C, D, A),
v2 = iloczyn_wektorowy(C, D, B),
v3 = iloczyn_wektorowy(A, B, C),
v4 = iloczyn_wektorowy(A, B, D);
//sprawdzenie czy się przecinają - dla niedużych liczb
//if(v1*v2 < 0 && v3*v4 < 0) return 1;
//sprawdzenie czy się przecinają - dla większych liczb
if((v1>0&&v2<0||v1<0&&v2>0)&&(v3>0&&v4<0||v3<0&&v4>0)) return 1;
//sprawdzenie, czy koniec odcinka leży na drugim
if(v1 == 0 && sprawdz(C, D, A)) return 1;
if(v2 == 0 && sprawdz(C, D, B)) return 1;
if(v3 == 0 && sprawdz(A, B, C)) return 1;
if(v4 == 0 && sprawdz(A, B, D)) return 1;
//odcinki nie mają punktów wspólnych
return 0;
}
int main()
{
pair<int, int> A, B, C, D;
//definiujemy dwa odcinki skierowane A->B oraz C->D
cout<<"Podaj wspólrzedne punktu A: ";
cin>>A.first>>A.second;
cout<<"Podaj wspólrzedne punktu B: ";
cin>>B.first>>B.second;
cout<<"Podaj wspólrzedne punktu C: ";
cin>>C.first>>C.second;
cout<<"Podaj wspólrzedne punktu D: ";
cin>>D.first>>D.second;
if(czy_przecinaja(A, B, C, D))
cout<<"Odcinki sie przecinaja\n";
else
cout<<"Odcinki sie nie przecinaja\n";
return 0;
}