Krótki wstęp do algorytmów geometrycznych

09.12.2009 - Dominik Rusak
Trudność

    Geometria jest dziedziną matematyki, która zazwyczaj budzi rozmaite, najcześciej przeciwstawne uczucia. Jedni uważają ja za nudną - tym się dziwię. Inni dostrzegają piękno zajmowania się obiektami geometrycznymi, wymagającego pomysłowości, cierpliwości i nieraz chwili iluminacji. Wiele zadań geometrycznych da się rozwiązać w sposób żmudny i siłowy, lecz chwila olśnienia lub obycie w temacie pozwala odkryć "królewską drogę", prowadzącą szybko i błyskotliwie do rozwiązania.

     Geometria ma swoje miejsce też i w informatyce. Problemy geometryczne pojawiają się w grafice komputerowej, robotyce, statystyce i wielu innych dziedzinach. Przydatną  jest zatem umiejetność stosowania algorytmów, pozwalających zautomatyzować działania wykonywane na obiektach geometrycznych. Dział informatyki zajmujący się takimi algorytmami zwie się geometria obliczeniową. Nadmienić należy, że zautomatyzowania takich działań nie należy zaliczać do wspomnianych "rozwiązań żmudnych i siłowych". Jest nie lada sztuką w sposób optymalny przetwarzać obiekty geometryczne. Wymaga to znajdowania i uogólniania "dróg królewskich", co wiąże się często z potrzebą dowiedzenia poprawności dla przypadku ogólnego. Częstokroć problemy geometryczne naszpikowane są "przypadkami brzegowymi", które należy z zegarmistrzowską precyzją wyławiać i rozpatrywać osobno.


    Celem tego artykułu jest przybliżenie Czytelnikowi bardzo podstawowych metod, pozwalających odpowiadać na proste pytania dotyczące odcinków na płaszczyźnie. Ich poznanie pozwala w dłuższej perspektywie na zrozumienie, stosowanie i konstruowanie bardziej skomplikowanych algorytmów geometrycznych.
    Badając własności odcinków, musimy przyjąć dla nich pewną reprezentację. Punkt p będziemy oczywiście reprezentować jako parę współrzędnych $ x $ i $ y $ i zapisywać jako $ p = (x,y) $ . Sumą dwóch punktów $ p_1 $ i $ p_2 $ jest punkt  $ p_1+p_2 $ o współrzędnych $ (x_1+x_2,y_1+y_2) $. Odcinek będzie przedstawiony jako para punktów, będących jego końcami. Mówiąc, że punkt $ a_3 = (x_3,y_3) $ leży na prostej pomiędzy punktami $ a_1 = (x_1,y_1) $ i $ a_2 = (x_2,y_2) $ (wszystkie trzy są współliniowe), nie będziemy zakładać, że $  x_1 \leq x_3 \leq x_2 $, lecz, że $ min(x_1,x_2) \leq x_3 \leq max(x_1,x_2) $. Innymi słowy nie zakładamy wtedy, że to $ a_1 $ jest początkiem odcinka, patrząc od lewej strony.  Odcinek skierowany będzie to  uporządkowana para punktów. Wektorem nazwiemy odcinek uporządkowany, którego pierwszy punkt jest środkiem układu współrzędnych.  Zanim przejdziemy do właściwej części artykułu, musimy odpowiedzieć na pytanie: czym właściwie jest odcinek na płaszczyźnie?


Wygląda na to, że jest to zbiór punktów leżących na jednej prostej z $ p_1 $ i $ p_2 $ pomiędzy tymi punktami (lub będących jednym z nich).
Wprowadźmy też pojęcie kombinacji wypukłej dwóch punktów $ p_1 = (x_1,y_1) $ i $ p_2 = (x_2,y_2) $. Jest to dowolny punkt $ p_3 = (x_3,y_3) $ ,taki, że dla pewnej liczby $ \alpha $ z przedziału $ 0 \leq \alpha \leq 1 $  zachodzi: $ x_3 = \alpha x_1 + (1-\alpha)x_2 $$ y_3 = \alpha y_1 + (1-\alpha)y_2 $. Wygląda to dziwnie, lecz odcinek $ (p_1,p_2) $ jest właśnie zbiorem kombinacji wypukłych $ p_1 $ i $ p_2 $. Dowód pozostawiam Czytelnikowi jako zadanie. Należy pokazać, że każda kombinacja wypukła $ p_1 $ i $ p_2 $ leży na odcinku $ (p_1,p_2) $, i, że każdy punkt z tego odcinka jest kombinacją wypukłą $ p_1 $ i $ p_2 $.

    Będziemy badać rozmaite interakcje między odcinkami. Najpierw zastanowimy się, jak w łatwy sposób odpowiadać na pytanie, czy dla dwóch odcinków skierowanych o wspólnym początku pierwszy z nich jest położony zgodnie czy przeciwnie do ruchu wskazówek zegara względem drugiego. 

                             Rysunek 1

Informacja o takim wzajemnym położeniu dwóch odcinków jest bardzo ważna, gdyż pozwoli nam później powiedzieć coś o  "chodzeniu po odcinkach", lub stwierdzić, czy pewne odcinki przecinają się. Zagadnienie to związane jest z polem takiego równoległoboku:

 

                                      

Spróbujmy obliczyć to pole, mając dane współrzędne punktów $ p_1 $ i $ p_2 $ (zatem i $ p_1 $+$ p_2 $).
Zauważmy, że  otrzymać je możemy poprzez odjęcie od pola zaznaczonego prostokąta pól dwóch zaznaczonych trapezów i dwóch trójkątów. Ich pola są równe:

$ t_1 = \frac{x_1y_1}{2} $,    $ t_2 = \frac{x_2y_2}{2} $,   $ T_1 = x_2\frac{2y_1 + y_2}{2} $,

$ T_2 = y_1\frac{2x_2 + x_1}{2} $.

Pole prostokąta to $ (x_1 + x_2)(y_1 + y_2) $, zatem po elementarnych obliczeniach okazuje się, że pole równoległoboku wynosi $ x_1y_2 - x_2y_1 $. Zauważmy, że wynika z tego, iż może ono być ujemne. Okazuje się, że taką samą wartość przyjmuje iloczyn wektorowy wektorów $ p_1 $ i $ p_2 $, zapisywany jako $ p_1 \times p_2 $. Gdy jest on ujemny, punkt $ p_1 $ położony jest przeciwnie do ruchu wskazówek zegara względem $ p_2 $,  zgodnie zaś, gdy jest dodatni. Gdyby okazał się być zerem, oznacza to, że wektory $ p_1 $ i $ p_2 $ są współliniowe (tylko wtedy pole równoległoboku mogłoby być zerem). 

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com