English
Wpisy na blogu
22:28
Algorytmy geometryczne
Wstępny artykuł prezentujący podstawowe informacje o algorytmach geometrycznych. Napisany na potrzeby przedmiotu 'Algorytmy i struktury danych'.
Dział informatyki, który zajmuje się problematyką algorytmów geometrycznych nazywamy geometrią obliczeniową. We współczesnej inżynierii i matematyce geometria obliczeniowa znajduje zastosowanie między innymi w grafice komputerowej, robotyce, systemach projektowania wspomaganego komputerowo i statystyce. Danymi wejściowymi zazwyczaj są punkty, odcinki, czy wierzchołki wielokąta. Rozwiązaniami są często odpowiedzi na pytania dotyczące obiektów: czy którekolwiek z danych prostych się przecinają, albo np. wypukła otoczka zbioru punktów. Podstawowymi obiektami geometrycznymi o których będę tu mówić są punkt, odcinek, wektor, prosta. Przez sgn(x) oznaczamy znak liczby x, a przez det(p,q,r) wyznacznik macierzy:
gdzie p,q,r, są różnymi punktami: p = (x,y), q = (x',y'), r=(x,y).
Powiemy, że punkt r:
- leży po lewej stronie wektora p->q, jeżeli det(p,q,r) > 0;
- leży po prawej stronie wektora p->q jeżeli det(p,q,r) < 0;
- jest współliniowy z wektorem p->q jeżeli det(p,q,r) = 0;
Przedstawianie algorytmów geometrycznych rozpocznę od prezentacji trzech bardzo prostych, ale istotnych problemów, które często są podstawą w bardziej zaawansowanych algorytmach geometrycznych.
Sprawdzić, czy punkty p1 i p2 leża po tej samej stronie prostej p-q.
Aby rozwiązać ten problem należy wyliczyć wyznacznik det(p,q,p1) i det(p,q,p2), a następnie sprawdzić, czy znaki przy wyznacznikach są takie same: sgn(det(p,q,p1)) == sgn(det(p,q,p2))
Sprawdzić, czy punkt r należy do odcinka p-q
Aby rozwiązać ten problem należy najpierw z rzutować punkty p,q,r na osie OX i OY. Następnie sprawdzamy, czy rzut punktu r na oś OX znajduje się między rzutami punktów p i q i tak samo w przypadku rzutu na oś OY. Kolejnym krokiem jest sprawdzenie, czy punkty p,q,r są współliniowe.
Gdy wszystkie warunki są spełnione oznacza to, że punkt r należy do odcinka p-q.
Sprawdzić, czy dwa odcinki p-q i s-r się przecinają.
Należy tutaj zauważyć, że dwa odcinki przecinają się, wtedy, gdy punkty p,q leżą po przeciwnych stronach odcinka r-s, a punkty r,s po przeciwnych stronach odcinka p-q.
W przypadku spełniania obu warunków oznaczać to będzie, że proste się przecinają.
Problem przynależności
Jest to jeden z najczęściej spotykanych problemów w geometrii obliczeniowej. Dany jest obiekt geometryczny W oraz punkt p. Mamy zbadać, czy p należy do W. Przyjmijmy, że W jest dowolnym wielokątem. Aby wykazać, że punkt p znajduje się wewnątrz wielokąta należy poprowadzić półprostą l wzdłuż osi OX, która swój początek ma w punkcie p. Dla uproszczenia przyjmijmy, że prosta nie przecina wielokąta w żadnym z wierzchołków. Jeżeli półprosta przecina się z bokami wielokąta nieparzystą ilość razy wtedy można powiedzieć, że punkt p znajduje się wewnątrz wielokąta, w przeciwnym wypadku jest on na zewnątrz. Aby sprawdzić, czy półprosta przecina się z danym bokiem, wystarczy zastosować algorytm zaprezentowany wcześniej, który sprawdzania, czy dwa dane odcinki się przecinają. Jeżeli współrzędne y na końcach odcinka są sobie równe, wtedy wiadomo, że dany odcinek nie przecina się z prostą l (jest do niej równoległy). W przeciwnym wypadku należy ograniczyć półprostą z jednej strony do punktu:
i sprawdzić, czy:
Źródła
- L. Banachowski - "Algorytmy i struktury danych" - Wydawnictwa Naukowo-Techniczne, 2003r
- T. Cormen - "Wprowadzenie do algorytmów" - Wydawnictwa Naukowo-Techniczne, 2001r
Dodaj komentarz:
Nazywam się Tomasz Chudyk i witam na mojej stronie. Z zawodu jestem programistą. Moje zainteresowania krążą głównie wokół open-source, Linuksa i technologi internetowych.
