Презентация Algorytmy geometryczne онлайн

Содержание слайда: Algorytmy geometryczne dr Anna Beata Kwiatkowska

Содержание слайда: Geometria obliczeniowa Dział informatyki zajmujący się algorytmami geometrycznymi nazywamy geometrią obliczeniową. Najczęściej rozpatrywane są problemy: Na płaszczyźnie podstawowe problemy: Kiedy dwa odcinki przecinają się? Kiedy punkt przynależy do wielokąta? Jak znaleźć wypukłą otoczkę zbioru punktów na płaszczyźnie? Jak stwierdzić, czy istnieją przecinające się pary odcinków? mają zastosowanie także do problemów w przestrzeni. W przestrzeni problemy ważne ze względu na zastosowanie w animacji komputerowej. Zakładamy, że mamy do dyspozycji tylko cztery działania +, -, *, /. Nie korzystamy z funkcji trygonometrycznych. Mamy bardzo dokładne obliczenia – nieskończona precyzja.

Содержание слайда: Geometria obliczeniowa Rozważania ograniczamy do geometrii na płaszczyźnie. Podstawowe obiekty geometryczne: punkt p reprezentujemy parą współrzędnych p=(x, y) w ustalonym wcześniej układzie współrzędnych kartezjańskich odcinek wyznaczony przez parę punktów p, q oznaczamy przez p−q wektor o początku w punkcie p i końcu w punkcie q oznaczamy przez pq prosta będzie reprezentowana przez zawarty w niej odcinek lub wektor.

Содержание слайда: Podstawowe fakty z geometrii obliczeniowej na płaszczyźnie

Содержание слайда: Podstawowe fakty z geometrii obliczeniowej na płaszczyźnie Punkt r leży po lewej stronie wektora pq. Punkty p, q, r są współliniowe. Punkt r leży po prawej stronie wektora pq.

Содержание слайда: Elementarne algorytmy Zadanie Sprawdzić, czy punkty r i s leżą po tej samej stronie prostej p−q. Odpowiedź Wystarczy sprawdzić czy sgn(det(p, q, r))= sgn(det(p, q, s)). Zadanie Zbadać, czy punkt r należy do odcinka p−q. Odpowiedz Trzeba zbadać, czy punkty p, q, r są współliniowe oraz czy min(xp,xq) ≤ xr ≤max (xp, xq) i min(yp,yq) ≤ yr ≤max (yp, yq)

Содержание слайда: Elementarne algorytmy Zadanie Kiedy dwa odcinki p−q i r−s przecinają się? Odpowiedź Gdy p i q leżą po przeciwnych stronach prostej r−s, a punkty r i s po przeciwnych stronach prostej p−q. Zadanie Kiedy punkt p należy do trójkąta? Odpowiedź W czasie stałym można sprawdzić, czy punkt p należy do brzegu trójkąta. Jeśli jest inaczej, P musi leżeć po tej samej stronie wszystkich boków trójkąta. Wszystkie powyższe problemy są rozwiązywane w czasie stałym i tylko z użyciem operacji arytmetycznych.

Содержание слайда: Problem przynależności do wielokąta wypukłego Dane: n – liczba naturalna, n≥0 punkty w0, …, wn-1 reprezentujące kolejne na obwodzie wierzchołki wielokąta wypukłego W, punkt p. Wynik: Odpowiedź na pytanie: czy pW? Przypomnienie: Wielokąt jest wypukły wtedy i tylko wtedy, gdy każdy odcinek o końcach należących do wielokąta jest w nim całkowicie zawarty. Trinagulacja wielokąta – podział wielokąta na trójkąty nieprzecinającymi się przekątnymi. Dla wielokąta wypukłego o n wierzchołkach liczba trójkątów w triangulacji jest równa n-2, liczba sposobów podziału na trójkąty jest równa liczbie Catalana:

Содержание слайда: Problem przynależności do wielokąta wypukłego Algorytm I Wykonaj dowolną trinagulację wielokąta W. Dla każdego trójkąta sprawdź, czy p należy do niego. W czasie stałym można sprawdzić przynależność punktu do trójkąta. Jest n-1 trójkątów, dlatego złożoność obliczeniowa tego algorytmu to O(n).

Содержание слайда: Problem przynależności do wielokąta wypukłego Algorytm II Posługujemy się metodą wyszukiwania binarnego. Niech wielokąt ma wierzchołki numerowane od k do s. Są trzy możliwości: p leży na odcinku wk−w(s+k)/2 , wtedy badamy przynależność do odcinka p leży po lewej stronie, wtedy rekurencyjnie badamy wielokąt po lewej. p leży po prawej stronie, wtedy rekurencyjnie badamy wielokąt po prawej. W czasie stałym można sprawdzić przynależność punktu do trójkąta. Złożoność tego algorytmu to O(log n).

Содержание слайда: Problem przynależności punktu do dowolnego wielokąta Dane: n – liczba naturalna n punktów w0, …, wn-1 reprezentujących kolejne wierzchołki wielokąta W punkt p. Wynik: Odpowiedź na pytanie: czy pW?

Содержание слайда: Problem przynależności - algorytm W czasie liniowym umiemy sprawdzić, czy p należy do któregoś z boków wielokąta. Jeśli jest inaczej, wyznaczamy półprostą l o początku w p. W przypadku, gdy żaden z wierzchołków wielokąta nie leży na tej półprostej, punkt p leży wewnątrz wielokąta W wtedy i tylko wtedy, gdy przecina brzeg W nieparzystą liczbę razy.

Содержание слайда: Problem przynależności - obserwacja Może zdarzyć się, że l przecina brzeg wielokąta w wierzchołkach lub zawiera krawędź wielokąta. Obserwacja: Każdą półprostą o początku w punkcie p można tak obrócić dookoła p o niewielki kąt, żeby otrzymać półprostą nie przecinającą W w wierzchołkach. .

Содержание слайда: Problem przynależności - przypadki Rozważamy dwa przypadki (i wszystkie analogiczne do nich): Złożoność O(n) – koszt obliczeń związany z każdym wierzchołkiem i bokiem jest stały, a mamy n wierzchołków.

Содержание слайда: Wypukła otoczka Dane: n – liczba punktów na płaszczyźnie Zbiór n punktów S = {(xi, yi) dla 0  i, j  n-1}, punkty zadane są przez współrzędne kartezjańskie. Wynik: Kolejne punkty wypukłej otoczki zbioru S (najmniejszy wielokąt wypukły zawierający S).

Содержание слайда: Wypukła otoczka Dane: n – liczba punktów na płaszczyźnie Zbiór n punktów S = {xi, yi dla 0  i, j  n-1}, punkty zadane są przez współrzędne kartezjańskie. Wynik: Kolejne punkty wypukłej otoczki zbioru S (najmniejszy wielokąt wypukły zawierający S).

Содержание слайда: Wypukła otoczka Dane: n – liczba punktów na płaszczyźnie Zbiór punktów S = { pi= (xi, yi) dla 0  i, j  n-1}, punkty zadane są przez współrzędne kartezjańskie. Wynik: Kolejne punkty wypukłej otoczki zbioru S (najmniejszy wielokąt wypukły zawierający S).

Содержание слайда: Wypukła otoczka – algorytm naiwny Krok 1. Znaleźć wszystkie wierzchołki wypukłej otoczki zbioru S. Krok 2. Uporządkować w kolejności występowania na obwodzie wypukłej otoczki. Fakt Punkt p nie jest wierzchołkiem wypukłej otoczki wtedy i tylko wtedy, gdy leży wewnątrz pewnego trójkąta o wierzchołkach z S, różnych od p, lub należy do odcinka łączącego dwa punkty z S różne od p. Ponieważ dla n punktów mamy co najwyżej różnych trójkątów. Dlatego realizacja kroku1. zabiera czas O(n4). Czy musimy sprawdzać wszystkie trójkąty? Można wybrać punkt, np. c - centroid, i uznać go za początek układu współrzędnych. Rozpatrujemy wtedy trójkąty o wierzchołkach c, pi, pi+1. Algorytm ma wtedy złożoność O(n2).

Содержание слайда: Wypukła otoczka – sortowanie biegunowe Układ współrzędnych polarnych – układ współrzędnych na płaszczyźnie wyznaczony przez pewien punkt O zwany biegunem oraz półprostą o początku w punkcie O zwaną osią biegunową. Sortowanie biegunowe – sortowanie względem współrzędnych biegunowych wektorów (promień i kąt nachylenia do osi OX).

Содержание слайда: Wypukła otoczka – sortowanie biegunowe

Содержание слайда: Algorytm Grahama W algorytmie Grahama używamy stosu, który zawiera kandydatów na wierzchołki otoczki. Każdy punkt z wejściowego zbioru jest raz wkładany na stos, natomiast punkty nie będące wierzchołkami otoczki są ze stosu zdejmowane. W momencie zakończenia działania algorytmu stos zawiera punkty występujące na otoczce w kolejności odwrotnej do ruchu wskazówek zegara.

Содержание слайда: Algorytm Grahama

Содержание слайда: Algorytm Grahama

Содержание слайда: Algorytm Grahama

Содержание слайда: Algorytm Grahama

Содержание слайда: Algorytm Grahama

Содержание слайда: Algorytm Grahama

Содержание слайда: Algorytm Grahama

Содержание слайда: Algorytm Grahama

Содержание слайда: Algorytm Grahama

Содержание слайда: Algorytm Grahama

Содержание слайда: Algorytm Grahama

Содержание слайда: Algorytm Grahama

Содержание слайда: Algorytm Grahama

Содержание слайда: Algorytm Grahama Niech p0 będzie punktem o najmniejszej współrzędnej y, jeśli takich jest kilka, bierzemy ten o najmniejszej współrzędnej x. Punkt ten uznajemy za początek układu współrzędnych. Sortujemy pozostałe punkty niemalejąco względem współrzędnych polarnych. Włóż na stos S punkty p0, p1, p2. Dla punktów od 3 do n-1: tak długo, jak kolejny punkt pi jest na prawo od wektora utworzonego z przedostatniego i ostatniego wierzchołka na stosie zamień na stosie ostatni element na pi włóż pi na stos. Wynikiem są punkty na stosie. O złożoności decyduje punkt 2, który można wykonać w O(n logn). Kroki 1. i 4. (zasada magazynu) są wykonywane w czasie liniowym.

Содержание слайда: Algorytm Jarvisa Niech p0 będzie punktem o najmniejszej współrzędnej y, jeśli takich jest kilka, bierzemy ten o najmniejszej współrzędnej x.

Содержание слайда: Algorytm Jarvisa Weź dowolny punkt różny od p0

Содержание слайда: Algorytm Jarvisa Powtarzaj dla punktów, które jeszcze nie są w otoczce: Dla punktów pi, jeśli pi leży na prawo od wektora, weź go jako koniec wektora.

Содержание слайда: Algorytm Jarvisa Powtarzaj dla punktów, które jeszcze nie są w otoczce: Dla punktów pi, jeśli pi leży na prawo od wektora, weź go jako koniec wektora.

Содержание слайда: Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę.

Содержание слайда: Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę.

Содержание слайда: AlgorytmJarvisa Powtarzaj, aż znajdziesz całą otoczkę.

Содержание слайда: Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę.

Содержание слайда: Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę.

Содержание слайда: Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę.

Содержание слайда: Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę.

Содержание слайда: Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę.

Содержание слайда: Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę.

Содержание слайда: Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę.

Содержание слайда: Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę.

Содержание слайда: Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę.

Содержание слайда: Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę.

Содержание слайда: Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę.

Содержание слайда: Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę.

Содержание слайда: Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę. Złożoność obliczeniowa algorytmu Grahama to 0(nk), gdzie k jest liczba punktów na otoczce.

Содержание слайда: Przecinanie się par odcinków

Содержание слайда: Przecinanie się par odcinków

Содержание слайда: Przecinanie się par odcinków

Содержание слайда: Przecinanie się par odcinków

Содержание слайда: Przecinanie się par odcinków

Содержание слайда: Przecinanie się par odcinków

Содержание слайда: Przecinanie się par odcinków

Содержание слайда: Przecinanie się par odcinków

Содержание слайда: Przecinanie się par odcinków