Sprawdzenie, czy dwa odcinki przecinają się

powrót

Artykuł przedstawia algorytm sprawdzający, czy dwa odcinki przecinają się. Żeby dwa odcinki przecinały się musi zachodzić jeden z dwóch przypadków:

1. Odcinki przecinają się wtedy i tylko wtedy gdy pierwszy odcinek przecina prostą zawierającą drugi odcinek oraz drugi odcinek przecina prostą zawierającą pierwszy odcinek.
2. Druga sytuacja to taka, w której jeden z końców odcinka leży na drugim odcinku.

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;
}