Krótki wstęp do algorytmów geometrycznych

09.12.2009 - Dominik Rusak
Trudność

       Stosując inną metodę, moglibyśmy obliczyć w jakiś sposób kąt między tymi wektorami. Jego znak dawałby tę samą informację, co znak iloczynu wektorowego. Jednak do wyliczenia tego drugiego potrzebujemy tylko dwóch mnożeń i jednego odejmowania! Co jednak zrobić, gdy zadane odcinki są skierowane, lecz nie są wektorami? Wystarczy zrobić coś, by się nimi stały. Skoro wektory mają wspólny początek w środku układu współrzednych, sprowadźmy  wspólny poczatek $ (p_0,p_1) $ i ($ p_0,p_2) $ (czyli $ p_0 $) do tegoż środka. Wystarczy przyjąć $ p_0 = (0,0) $ i odjąć współrzędne $ p_0 $ od $ p_1 $ i $ p_2 $ (zatem by uczynić wektorami, przesuwamy o wektor). Wtedy ich wzajemne położenie nie ulegnie zmianie:

                  Przed przesunięciem.                  Po przesunięciu

 
Współrzędne nowopowstałych wektorów to:
$ p'_1 = (x_1 - x_0, y_1 - y_0) $, $ p'_2 = (x_2 - x_0, y_2 - y_0) $.
Zatem iloczyn wektorowy przedstawia się następująco:
$ p'_1 \times p'_2 = (x_1- x_0)(y_2 - y_0) - (x_2 - x_0)(y_1 - y_0). $
Patrzymy na znak i odczytujemy bezcenną informację o tym, jak leżą sobie razem odcinek $ (p_0,p_1) $ z odcinkiem $ (p_0,p_2) $.
Powstaje pytanie: co z tego? Przejdźmy się zatem "po odcinkach", by znaleźć pierwsze tego zastosowanie. 


    Załóżmy, że "spacerujemy" sobie po odcinku $ (p_0,p_1) $ i docieramy do $ p_1 $, gdzie łaczy się on z  odcinkiem $ (p_1,p_2) $. Zadajemy sobie pytanie, czy przechodząc do tego odcinka, skręcamy w lewo, w prawo, czy nadal dziarsko maszerujemy naprzód?  Zobaczmy, jak to wygląda na płaszczyźnie i spójżmy, co się stanie, gdy połaczymy $ p_0 $ i $ p_2 $, tworzac odcinek skierowany $ (p_0,p_2) $:


                          

 

Jeśli skręcamy w lewo, to $ (p_0,p_1) $ leży zgodnie z ruchem wskazówek zegara względem $ (p_0,p_2) $. Gdy kierujemy kroki w prawo, leży on przeciwnie do tegoż ruchu. Wystarczy zatem sprowadzić $ (p_0,p_1) $ i $ (p_0,p_2) $ do wektorów i obliczyć ich iloczyn wektorowy. Ujemny mówi nam: skręcilismy w prawo, dodatni - w lewo, zerowy - wciąż do przodu! Znów pytanie: po co nam to całe "chodzenie po odcinkach". Przydaje się ono chociażby w algorytmie Grahama znajdowania wypukłej otoczki zbioru punktów (to zagadnienie wykracza jednak poza ramy tego artykułu). Możemy w ten sposób sprawdzać również, czy dany wielokąt jest wypukły. Jeśli jest on przedstawiony jako ciag punktów <$ p_0,p_1,...,p_{n-1} $> (zakładamy, że żadne trzy kolejne wierzchołki na obwodzie nie są współliniowe), podanych w kolejności przeciwnej do ruchu wskazówek zegara na obwodzie, możemy postępować następująco:   

Startując z punktu $ p_0 $, przechodzimy kolejno po odcinkach $ (p_0,p_1) $, $ (p_1,p_2) $,..., $ (p_{n-2},p_{n-1}) $,$ (p_{n-1},p_0), (p_0,p_1) $. Jeżeli za każdym razem podczas takiego spaceru skręcalismy w lewo, wielokąt jest wypukły. Inaczej niestety nie! Podobnie, gdy punkty podane są zgodnie z ruchem wskazówek zegara, musimy sprawdzić, czy skręcamy zawsze w prawo.

  

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com