Zrozumienie tego algorytmu wymaga zaznajomienia się ze wstępem do geometrii obliczeniowej
Niech dane będą cztery punkty określone współrzędnymi: A=(x₁,y₁), B=(x₂,y₂), C=(x₃,y₃) i D=(x₄,y₄).
Istnieje bardzo prosty sposób sprawdzenia, czy odcinki |AB| i |CD| przecinają się, są dwie możliwości:

• któryś z końców jednego odcinka należy do drugiego lub
• jeżeli odcinek |AB| przecina odcinek |CD| to punkty A i B leżą po przeciwnych stronach odcinka |CD| i punkty C i D leżą po przeciwnych stronch odcinka |AB|, jeżeli zaś odcinki te nie przecinają się, to punkty A i B leżą po tej samej stronie odcinka |CD| lub punktu C i D leżą po tej samej odcinka |AB|

Pierwszym krokiem jest więc zbadanie, czy jeden z końców jednego odcinka należy do drugiego odcinka (zob. przynależność punktu do odcinka). Jeżeli tak jest, to odcinki te się przecinają
W przeciwnym wypadku należy sprawdzić czy oba końce jednego z odcinków leżą po tej samej, czy po przeciwnych stronach drugiego odcinka. Łatwo to zrobić porównując znaki wyznaczników det(A,B,C) i det(A,B,D), jeżeli:

• sign[det(A,B,C)] = sign[det(A,B,D)] to punkty C i D leżą po tej samej stronie odcinka |AB| - odcinki nie przecinają się
• sign[det(A,B,C)] <> sign[det(A,B,D)] to punkty C i D leżą po przeciwnych stronach odcinka |AB| - odcinki przecinają się

sign(x) oznacza znak liczby x

Przeanalizujmy teraz przykład:
Dane są odcinki |AB| i |CD|, gdzie A=(2,2), B=(10,7), C=(3,8), D=(8,1). Mamy sprawdzić, czy odcinki się przecinają.
W pierwszym kroku musimy sprawdzić, czy punkty żadnego z odcinków nie należą do drugiego odcinka, w tym celu sprawdzamy najpierw dla każdego punktu obu odcinków, czy jest on współliniowy z drugim odcinkiem, czyli wyliczamy wyznaczniki det(A,B,C), det(A,B,D), det(C,D,A) oraz det(C,D,B). W naszym przykładzie żaden z wyznaczników nie miał wartości 0, nie ma więc współliniowości punktów żadnego z odcinków z żadnym punktem drugiego odcinka. Przechodzimy więc do sprawdzania dwóch nierówności (także dla każdych trzech punktów):
min(x₁, x₂) <= x₃ <= max(x₁, x₂) oraz min(y₁, y₂)<= y₃ <= (y₁, y₂). Także ten warunek nie został spełniony. Wiemy więc, że żaden z punktów naszych odcinków nie należy do drugiego odcinka.
Teraz możemy zbadać, czy punktu C i D znajdują się po tej samej stronie, czy po przeciwnych stronach odcinka |AB| oraz, czy punkty A i B leżą po tej samej, czy po przeciwnych stronach odcinka |CD|. Obliczamy więc wyznaczniki det(A,B,C) i det(A,B,D) by porównać ich znaki, to samo robimy z wyznacznikami det(C,D,A) i det(C,D,B). Okazuje się, że det(A,B,C)=43 a det(A,B,D)=-38, czyli wyznaczniki mają przeciwne znaki, więc punkt C i D leżą po przeciwnych stronach odcinka |AB| Również druga para wyznaczników ma przeciwne znaki: det(C,D,A)=-37, det(C,D,B)=44, punkty A i B leżą po przeciwnych stronach odcinka |CD|. Wynika z tego, że odcinki |AB| i |CD| przecinają się.

Komentarze