Wpisany przez Michał Knasiecki,
03 sierpnia 2005 22:44
Zrozumienie tego algorytmu wymaga zaznajomienia się ze wstępem do geometrii obliczeniowej
Niech dane będą cztery punkty określone współrzędnymi: A=(x1,y1), B=(x2,y2), C=(x3,y3) i D=(x4,y4).
Istnieje bardzo prosty sposób sprawdzenia, czy odcinki |AB| i |CD| przecinają się, są dwie możliwości:
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:
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(x1, x2) <= x3 <= max(x1, x2) oraz min(y1, y2)<= y3 <= (y1, y2). 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ę.
Niech dane będą cztery punkty określone współrzędnymi: A=(x1,y1), B=(x2,y2), C=(x3,y3) i D=(x4,y4).
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|
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
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(x1, x2) <= x3 <= max(x1, x2) oraz min(y1, y2)<= y3 <= (y1, y2). 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ę.
Implementacje
Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
Tomasz Lubiński | Ada | .ada | .ada | ***** / 2 | |
Michał Knasiecki | C/C++ | .cpp | .cpp | ***** / 18 | |
Michał Knasiecki | Delphi/Pascal | Borland Delphi 5 | .pas | .pas | ***** / 3 |
Tomasz Lubiński | Java | .java | .java | ***** / 4 | |
Damian Frańczuk | Php | .php | .php | ***** / 0 |
Poprawiony: 28 sierpnia 2012 19:48
A: 1,0
B: 5,4
C: 3,0
D: 4,2
odcinki sie nie przecinają, powyższe zasady jak i program mowi, że się przecinają.
np.
A(a,b) B(c,d) i a == c lub b == d
i drugi odcinek ma punkt po przeciwnych stronach A i B.
Przykład:
A(1,4) B(4,1)
C(3,3) D(5,5)