algorytm.org

Przecinanie się odcinków



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Przecinanie się odcinków
Ocena użytkowników:***** / 45
SłabyŚwietny 
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:
  • 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

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
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiAda
.ada
.ada
***** / 2
Michał KnasieckiC/C++
.cpp
.cpp
***** / 18
Michał KnasieckiDelphi/PascalBorland Delphi 5
.pas
.pas
***** / 3
Tomasz LubińskiJava
.java
.java
***** / 4
Damian FrańczukPhp
.php
.php
***** / 0
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 28 sierpnia 2012 19:48
Komentarze
photo
-8 # MnK 2010-05-08 11:26
implementacja jest błędna, pomysł z resztą też. Dla przykłądu weźmy:
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ą.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+7 # MnK leszcz 2010-07-10 12:38
algorytm jest ok. autor powinien tylko napisac ze jesli warunek 1 nie jest prawdziwy nalezy przeskoczyc do warunku 3. MnK pomysl troszke.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-1 # Gość 2011-07-05 19:07
jaka jest definicja funkcji 'det' ?? jak to liczyć?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-1 # gora 2011-10-08 16:11
to wskaźnik macierzy...
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-4 # Inżynier 2011-11-15 11:45
Algorytm jest zły. Zapomniano o sytuacji, gdzie jeden odcinek jest linią prostą tzn.
np.
A(a,b) B(c,d) i a == c lub b == d
i drugi odcinek ma punkt po przeciwnych stronach A i B.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-1 # maciej84 2013-04-21 00:54
Algorytm nie uwzględnia wszystkich przypadków, więc jest bezużyteczny.
Przykład:
A(1,4) B(4,1)
C(3,3) D(5,5)
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # Adi 2014-02-12 20:13
Ej to te odcinki sie przecinają ??? :)
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz