Krótki wstęp do algorytmów geometrycznych
09.12.2009 - Dominik Rusak
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 i ( (czyli ) do tegoż środka. Wystarczy przyjąć i odjąć współrzędne od i (zatem by uczynić wektorami, przesuwamy o wektor). Wtedy ich wzajemne położenie nie ulegnie zmianie:
Jeśli skręcamy w lewo, to leży zgodnie z ruchem wskazówek zegara względem . Gdy kierujemy kroki w prawo, leży on przeciwnie do tegoż ruchu. Wystarczy zatem sprowadzić i 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 <> (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 , przechodzimy kolejno po odcinkach , ,..., ,. 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.
(13 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com