Krótki wstęp do algorytmów geometrycznych

09.12.2009 - Dominik Rusak
Trudność


    Przejdźmy do czegoś jeszcze ciekawszego. Chcemy odpowiadać na pytanie, czy dwa dane odcinki się przecinają. Można to zrobić bezpośrednio - wyznaczyć równania prostych, przechodzących przez te odcinki, znaleźć punkt ich przecięcia i zobaczyć, czy należy on do obu odcinków. Jednak będziemy musieli wtedy dzielić przy próbie znalezienia punktu przecięcia tych prostych. Problemy mogą się pojawić też, gdy jeden lub oba odcinki są równoległe do osi Y. Dzielenie jest kosztowną operacją, pojawiają się też często przy jego wykonywaniu błędy zaokrągleń, związane z reprezentacją liczb w komputerze. Jeżeli odcinki są prawie równoległe, komputer może stwierdzić, że tak obliczone proste je zawierające są dosłownie równoległe, i nie znaleźć ewentualnego punktu przecięcia.

    Wolelibyśmy zatem ograniczyć się do dokładniejszych operacji, takich jak dodawanie, odejmowanie, mnożenie i porównywanie. Zastanówmy się zatem, co w obliczu omówionych już zagadnień oznacza przecinanie się odcinków? Zakładamy, że odcinki przecinają się, gdy mają co najmniej jeden punkt wspólny (mogą mieć nieskończenie dużo takich punktów wspólnych).
Zauważmy, że odcinki $ (p_1,p_2) $ i $ (p_3,p_4) $ przecinają się, gdy każdy z nich przecina prostą, zawierającą drugi. Odcinek przecina prostą, gdy jego końce są po przeciwnych stronach tej prostej.

                                           "Czyste przecięcie"

Uznamy też, że przecina on prostą, gdy jeden lub oba jego końce leżą na tej prostej:

                                           


Są to niestety wspomniane "przypadki brzegowe", do których będziemy musieli podejść z wzmożoną czujnością. Okazuje się, że znów będziemy potrzebowali określić wzajemne położenie pewnych odcinków skierowanych. Weźmy przykładowe położenie dwóch odcinków:

                                          

By sprawdzić po której stronie prostej zawierającej $ (p_1,p_2) $ znajduje się punkt $ p_3 $, wystarczy sprawdzić, po której stronie $ (p_1,p_2) $ znajduje sie ten punkt. Tak samo należy uczynić dla $ p_4 $. Liczyć będziemy zatem iloczyny wektorowe $  S_1 = (p_3 - p_1) \times (p_2 - p_1) $ i $ S_2 = (p_4 - p_1) \times (p_2 - p_1) $. Podobnie sytuacja wyglądać będzie dla określenia, czy $ (p_1,p_2) $ przecina prostą zawierającą $ (p_3,p_4) $. Obliczymy iloczyny  $ S_3 = (p_1 - p_3) \times (p_4 - p_3) $ i $ S_4 = (p_2 - p_3) \times (p_4 - p_3) $

                                           
Zauważmy, że gdy $ S_1 $ i $ S_2 $ mają przeciwne znaki (żaden nie jest zerem) i sytuacja wygląda analogicznie dla $ S_3 $ i $ S_4 $, to zachodzi sytuacja "czystego przecięcia", bez końca pewnego odcinka na drugim odcinku. Wtedy z całą mocą można stwierdzić, że odcinki przecinają się.  Co jednak, gdy pewien z tych iloczynów jest równy zeru? Oznacza to, że koniec jednego z odcinków (zależny od indeksu iloczynu, np. gdy $ S_1 = 0 $ wiemy, że $ p_1 $,$ p_2 $ i $ p_3 $ są współliniowe, więc $ p_3 $ leży na prostej, zawierającej $ (p_1, p_2) $) leży na prostej zawierającej drugi. Trzeba zatem wtedy sprawdzić, czy ten punkt leży na drugim odcinku. Jest to proste sprawdzenie - wiedząc, że punkty są współliniowe, musimy tylko zbadać, czy jedna ze współrzędnych tego punktu (np. $ x $) znajduje się między odpowiadającymi współrzednymi końców tego odcinka. Dla takich odcinka $ (a_1,a_2) $ i punktu $ a_3 $ wystarczy zatem sprawdzić, czy:

$  a_3 \geq min(a_1,a_2) $ i $ a_3 \leq max(a_1,a_2) $.


      Jeżeli to sprawdzenie da odpowiedź przeczącą, nie przesądza to jeszcze o tym, że odcinki się nie przecinają. Nalezy przeprowadzić test dla wszystkich tych $ S_i, i=1,2,3,4 $, które wyniosą zero. Poniższy przykład ilustruje, że jedno sprawdzenie nie zawsze wystarczy:

                                          
Widzimy, że przykładowe odcinki $ (p_1,p_2) $ i $ (p_3,p_4) $ przecinają się w nieskończonej ilości punktów. Przypuśćmy, że obliczylismy $ S_1 = 0 $. Okazało się zatem, że przykład nie kwalifikuje się do "czystego przecięcia". Sprawdzamy więc, czy $ p_3 $ leży między $ p_1 $ i $ p_2 $. Okazuje się, że nie. Przerywając teraz procedurę z odpowiedzią : "Nie przecinają się!", popełnilibyśmy błąd. Mamy bowiem: $ S_2 = 0 $ i $ p_4 $ leży pomiedzy $ p_1 $ i $ p_2 $. By sformułować dokładny algorytm, zdefiniujmy w pseudokodzie funkcje:

 

iloczyn(punkt p1, punkt p2, punkt p3) {
return (x2 - x1)(y3 - y1) - (x3 - x1)(y2 - y1)    //zwracamy iloczyn skalarny wektorów (p2-p1) i (p3-p1)
}

 

lezy_miedzy(punkt p1, punkt p2, punkt p3) {
if min{x1,x2} =< x_3 =< max{x1,x2} return true   //zakładamy, że p1,p2 i p3 są współliniowe
else return false  
}


Wtedy możemy zdefiniować funkcję:

przecinaja_się(punkt p1, punkt p2, punkt p3, punkt p4) {  //rozważamy odcinki (p1,p2) i (p3,p4)
S_1 = iloczyn(p1, p3, p2)
S_2 = iloczyn(p1, p4, p2)
S_3 = iloczyn(p3, p1, p4)
S_4 = iloczyn(p3, p2, p4)
if ((S_1 > 0 i S_2 < 0) lub (S_1 < 0 i S_2 > 0)) i ((S_3 < 0 i S_4 > 0) lub (S_3 > 0 i S_4 < 0)) return true
else if S_1 = 0 i lezy_miedzy(p1, p2, p3) return true
else if S_2 = 0 i lezy_miedzy(p1, p2, p4) return true
else if S_3 = 0 i lezy_miedzy(p3, p4, p1) return true
else if S_4 = 0 i lezy_miedzy(p3, p4, p2) return true
else return false

}

 
       Zauważmy, że ten algorytm sprawdza zarówno, czy odcinki "przecinają się czysto", jak i czy nie zachodzi "przypadek brzegowy". Tak zdefiniowana funkcja przecinaja_sie może być bardzo przydatna przy innych algorytmach geometrycznych, na przykład takich, jak sprawdzanie, czy punkt należy do wielokąta (wypukłego bądź nie). Tyle w tym artykule. Zapraszam do robienia zadań na następnej stronie!

4.615385
Twoja ocena: Brak Ocena: 4.6 (13 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com