Algorytmy geometryczne - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Algorytmy geometryczne. Доклад-сообщение содержит 64 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Algorytmy geometryczne dr Anna Beata Kwiatkowska

Слайд 2

Описание слайда:

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.

Слайд 3

Описание слайда:

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.

Слайд 4

Описание слайда:

Podstawowe fakty z geometrii obliczeniowej na płaszczyźnie

Слайд 5

Описание слайда:

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.

Слайд 6

Описание слайда:

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)

Слайд 7

Описание слайда:

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.

Слайд 8

Описание слайда:

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:

Слайд 9

Описание слайда:

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).

Слайд 10

Описание слайда:

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).

Слайд 11

Описание слайда:

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?

Слайд 12

Описание слайда:

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.

Слайд 13

Описание слайда:

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. .

Слайд 14

Описание слайда:

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.

Слайд 15

Описание слайда:

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).

Слайд 16

Описание слайда:

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).

Слайд 17

Описание слайда:

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).

Слайд 18

Описание слайда:

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).

Слайд 19

Описание слайда:

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).

Слайд 20

Описание слайда:

Wypukła otoczka – sortowanie biegunowe

Слайд 21

Описание слайда:

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.

Слайд 22

Описание слайда:

Algorytm Grahama

Слайд 23

Описание слайда:

Algorytm Grahama

Слайд 24

Описание слайда:

Algorytm Grahama

Слайд 25

Описание слайда:

Algorytm Grahama

Слайд 26

Описание слайда:

Algorytm Grahama

Слайд 27

Описание слайда:

Algorytm Grahama

Слайд 28

Описание слайда:

Algorytm Grahama

Слайд 29

Описание слайда:

Algorytm Grahama

Слайд 30

Описание слайда:

Algorytm Grahama

Слайд 31

Описание слайда:

Algorytm Grahama

Слайд 32

Описание слайда:

Algorytm Grahama

Слайд 33

Описание слайда:

Algorytm Grahama

Слайд 34

Описание слайда:

Algorytm Grahama

Слайд 35

Описание слайда:

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.

Слайд 36

Описание слайда:

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.

Слайд 37

Описание слайда:

Algorytm Jarvisa Weź dowolny punkt różny od p0

Слайд 38

Описание слайда:

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.

Слайд 39

Описание слайда:

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.