Algorytmy geometryczne

Содержание

Слайд 2

Geometria obliczeniowa Dział informatyki zajmujący się algorytmami geometrycznymi nazywamy geometrią obliczeniową.

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:

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

Podstawowe fakty z geometrii obliczeniowej na płaszczyźnie

Слайд 5

Podstawowe fakty z geometrii obliczeniowej na płaszczyźnie Punkt r leży po

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

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ę?

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

Problem przynależności do wielokąta wypukłego

 

Слайд 9

Problem przynależności do wielokąta wypukłego Algorytm I Wykonaj dowolną trinagulację wielokąta

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

p

w0

w1

w2

w3

w4

w5

w6

w7

Слайд 10

Problem przynależności do wielokąta wypukłego Algorytm II Posługujemy się metodą wyszukiwania

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

p

w0

w1

w2

w3

w4

w5

w6

w7

Слайд 11

Problem przynależności punktu do dowolnego wielokąta Dane: n – liczba naturalna

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?

p

Слайд 12

W czasie liniowym umiemy sprawdzić, czy p należy do któregoś z

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

l

p

Слайд 13

Problem przynależności - obserwacja Może zdarzyć się, że l przecina brzeg

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

l

p

Слайд 14

Problem przynależności - przypadki Rozważamy dwa przypadki (i wszystkie analogiczne do

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.

l

p

l

p

Liczba punktów przecięcia
nie zmienia się.

Liczba punktów przecięcia
zwiększa się o jeden.

Слайд 15

Wypukła otoczka Dane: n – liczba punktów na płaszczyźnie Zbiór n

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

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

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

nie należy do otoczki

Слайд 18

Wypukła otoczka – algorytm naiwny Krok 1. Znaleźć wszystkie wierzchołki wypukłej

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

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

0

x

y

Слайд 20

Wypukła otoczka – sortowanie biegunowe x y 0 x2 x1 y2 y1


Wypukła otoczka – sortowanie biegunowe

x

y

0

x2

x1

y2

y1

Слайд 21

Algorytm Grahama W algorytmie Grahama używamy stosu, który zawiera kandydatów na

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 0 x y p1 p1

Algorytm Grahama

0

x

y

p1

p1

Слайд 23

Algorytm Grahama 0 x y p2 p0 p1 p3 p4 p5

Algorytm Grahama

0

x

y

p2

p0

p1

p3

p4

p5

p6

p7

p8

p9

p10

p11

Слайд 24

Algorytm Grahama 0 x y p2 p0 p1 STOS p0 p1

Algorytm Grahama

0

x

y

p2

p0

p1

STOS

p0

p1

p2

p3

p4

p5

p6

p7

p8

p9

p10

p11

Слайд 25

Algorytm Grahama 0 x y p2 p0 p1 STOS p0 p1

Algorytm Grahama

0

x

y

p2

p0

p1

STOS

p0

p1

p3

p3

p4

p5

p6

p7

p8

p9

p10

p11

Слайд 26

Algorytm Grahama 0 x y p2 p0 p1 STOS p0 p1

Algorytm Grahama

0

x

y

p2

p0

p1

STOS

p0

p1

p3

p3

p4

p5

p6

p7

p8

p9

p10

p11

p4

Слайд 27

Algorytm Grahama 0 x y p2 p0 p1 STOS p0 p1

Algorytm Grahama

0

x

y

p2

p0

p1

STOS

p0

p1

p3

p3

p4

p5

p6

p7

p8

p9

p10

p11

p5

Слайд 28

Algorytm Grahama 0 x y p2 p0 p1 STOS p0 p1

Algorytm Grahama

0

x

y

p2

p0

p1

STOS

p0

p1

p3

p3

p4

p5

p6

p7

p8

p9

p10

p11

p6

Слайд 29

Algorytm Grahama 0 x y p2 p0 p1 STOS p0 p1

Algorytm Grahama

0

x

y

p2

p0

p1

STOS

p0

p1

p3

p3

p4

p5

p6

p7

p8

p9

p10

p11

p6

p7

Слайд 30

Algorytm Grahama 0 x y p2 p0 p1 STOS p0 p1

Algorytm Grahama

0

x

y

p2

p0

p1

STOS

p0

p1

p3

p3

p4

p5

p6

p7

p8

p9

p10

p11

p6

p8

Слайд 31

Algorytm Grahama 0 x y p2 p0 p1 STOS p0 p1

Algorytm Grahama

0

x

y

p2

p0

p1

STOS

p0

p1

p3

p3

p4

p5

p6

p7

p8

p9

p10

p11

p6

p9

Слайд 32

Algorytm Grahama 0 x y p2 p0 p1 STOS p0 p1

Algorytm Grahama

0

x

y

p2

p0

p1

STOS

p0

p1

p3

p3

p4

p5

p6

p7

p8

p9

p10

p11

p6

p9

p10

Слайд 33

Algorytm Grahama 0 x y p2 p0 p1 STOS p0 p1

Algorytm Grahama

0

x

y

p2

p0

p1

STOS

p0

p1

p3

p3

p4

p5

p6

p7

p8

p9

p10

p11

p6

p9

p11

Слайд 34

Algorytm Grahama 0 x y p2 p0 p1 STOS p0 p1

Algorytm Grahama

0

x

y

p2

p0

p1

STOS

p0

p1

p3

p3

p4

p5

p6

p7

p8

p9

p10

p11

p6

p9

p11

O złożoności decyduje sortowanie, który można wykonać w O(n

logn). Pozostałe kroki są wykonywane w czasie liniowym.
Слайд 35

Algorytm Grahama Niech p0 będzie punktem o najmniejszej współrzędnej y, jeśli

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

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.

0

x

y

p0

Слайд 37

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

Algorytm Jarvisa

Weź dowolny punkt różny od p0

0

x

y

p0

Слайд 38

Algorytm Jarvisa Powtarzaj dla punktów, które jeszcze nie są w otoczce:

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.

0

x

y

p0

Слайд 39

Algorytm Jarvisa Powtarzaj dla punktów, które jeszcze nie są w otoczce:

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.

0

x

y

p0

Слайд 40

Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę. 0 x y p0 p1

Algorytm Jarvisa

Powtarzaj, aż znajdziesz całą otoczkę.

0

x

y

p0

p1

Слайд 41

Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę. 0 x y p0 p1

Algorytm Jarvisa

Powtarzaj, aż znajdziesz całą otoczkę.

0

x

y

p0

p1

Слайд 42

AlgorytmJarvisa Powtarzaj, aż znajdziesz całą otoczkę. 0 x y p0 p1

AlgorytmJarvisa

Powtarzaj, aż znajdziesz całą otoczkę.

0

x

y

p0

p1

Слайд 43

Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę. 0 x y p0 p1

Algorytm Jarvisa

Powtarzaj, aż znajdziesz całą otoczkę.

0

x

y

p0

p1

Слайд 44

Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę. 0 x y p0 p1

Algorytm Jarvisa

Powtarzaj, aż znajdziesz całą otoczkę.

0

x

y

p0

p1

Слайд 45

Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę. 0 x y p0 p1

Algorytm Jarvisa

Powtarzaj, aż znajdziesz całą otoczkę.

0

x

y

p0

p1

Слайд 46

Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę. 0 x y p0 p1

Algorytm Jarvisa

Powtarzaj, aż znajdziesz całą otoczkę.

0

x

y

p0

p1

Слайд 47

Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę. 0 x y p0 p1

Algorytm Jarvisa

Powtarzaj, aż znajdziesz całą otoczkę.

0

x

y

p0

p1

Слайд 48

Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę. 0 x y p0 p1

Algorytm Jarvisa

Powtarzaj, aż znajdziesz całą otoczkę.

0

x

y

p0

p1

Слайд 49

Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę. 0 x y p0 p1

Algorytm Jarvisa

Powtarzaj, aż znajdziesz całą otoczkę.

0

x

y

p0

p1

Слайд 50

Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę. 0 x y p0 p1

Algorytm Jarvisa

Powtarzaj, aż znajdziesz całą otoczkę.

0

x

y

p0

p1

Слайд 51

Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę. 0 x y p0 p1

Algorytm Jarvisa

Powtarzaj, aż znajdziesz całą otoczkę.

0

x

y

p0

p1

Слайд 52

Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę. 0 x y p0 p1

Algorytm Jarvisa

Powtarzaj, aż znajdziesz całą otoczkę.

0

x

y

p0

p1

Слайд 53

Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę. 0 x y p0 p1

Algorytm Jarvisa

Powtarzaj, aż znajdziesz całą otoczkę.

0

x

y

p0

p1

Слайд 54

Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę. 0 x y p0 p1

Algorytm Jarvisa

Powtarzaj, aż znajdziesz całą otoczkę.

0

x

y

p0

p1

Слайд 55

Algorytm Jarvisa Powtarzaj, aż znajdziesz całą otoczkę. Złożoność obliczeniowa algorytmu Grahama

Algorytm Jarvisa

Powtarzaj, aż znajdziesz całą otoczkę. Złożoność obliczeniowa algorytmu Grahama

to 0(nk), gdzie k jest liczba punktów na otoczce.

0

x

y

p0

p1

Слайд 56

Dane: n – liczba odcinków n par punktów tworzących odcinki, nie


Dane:
n – liczba odcinków
n par punktów tworzących odcinki, nie rozpatrujemy odcinków

równoległych do osi współrzędnych, każdy odcinek przecina się z innym co najwyżej raz
Wynik:
Odpowiedź na pytanie: czy wśród odcinków są co najmniej dwa przecinające się?

Przecinanie się par odcinków

b

a

c

d

e

f

Слайд 57

Przecinanie się par odcinków b a c d e b miotła

Przecinanie się par odcinków

b

a

c

d

e

b
miotła
Algorytm korzysta z metody przez zamiatanie i polega

na tym, że:
sortujemy odcinki niemalejąco względem współrzędnych x początków odcinków.
prowadzimy miotłę po tych współrzędnych.

f

Слайд 58

Przecinanie się par odcinków b a c d e b c

Przecinanie się par odcinków

b

a

c

d

e

b

c

b
Rozpoczynający się odcinek wkładamy do miotły binarnie, zgodnie

z relacją leżenia po lewej/prawej – po lewej wyżej, po prawej niżej. Sprawdzamy czy sąsiadujące odcinki nie przecinają się.

f

Слайд 59

Przecinanie się par odcinków b a c d e b c

Przecinanie się par odcinków

b

a

c

d

e

b

c

b

c

Gdy odcinek się kończy, wyrzucamy go zmiotły i

sprawdzamy, czy jego dwaj sąsiedzi nie przecinają się.

f

Слайд 60

Przecinanie się par odcinków b a c d e b c b c a c f

Przecinanie się par odcinków

b

a

c

d

e

b

c

b

c

a

c

f

Слайд 61

Przecinanie się par odcinków b a c d e b c

Przecinanie się par odcinków

b

a

c

d

e

b

c

b

c

a

e

c

a

c

f

Слайд 62

Przecinanie się par odcinków b a c d e b c

Przecinanie się par odcinków

b

a

c

d

e

b

c

b

c

a

e

c

a

c

e

c

a

f

f

Слайд 63

Przecinanie się par odcinków b a c d e b c

Przecinanie się par odcinków

b

a

c

d

e

b

c

b

c

a

e

c

a

c

e

c

a

f

f

e

c

a

f

d

- Предыдущая
Проблемы культуры 20 века
Следующая -
Пути формирования лексикона у дошкольников с ОНР

Похожие презентации

Таблиця множення числа 6
Эта многоликая парабола
Весёлые клоуны. «Интерактивная мозаика»
Логарифмы. Их применение в ТОРАТ. Мансуров
Решение задач с помощью уравнений (6 класс)
Координатная плоскость. Рене Декарт
Краткий обзор методов статистического анализа количественных переменных
Интерполирование функций. Интерполяционный многочлен Лагранжа
Формулы пути
Призма. Элементы призмы. Площадь полной поверхности
Искусственный интеллект – наука и технология создания интеллектуальных машин
Работа по теме « Средняя линия трапеции» Ученика 9-2 класса Школы №593 Андреева Георгия Преподаватель : Петрова Наталья Васильевн
Модуль Финские технологии в обучении математике
Нам радостно, нам весело! Смеемся мы с утра. Но вот пришло мгновенье, Серьезным быть пора. Глазки прикрыли, ручки сложили, Головки
Работа учителя лицея №58 Красковой И.В.
Вписанные и центральные углы
Оси симметрии фигуры
Презентация на тему Аукцион «Продажа имения старой графини» ( математическая игра для 10-11 классов)
Формула Тейлора
Классический способ расчета ПФ одногруппных сквозных поездов. (Тема 5)
Умножение и деление.Задачи
Образование чисел второго десятка Подготовила учитель начальных классов Чернышова Светлана Олеговна
Статистика населения
Вписанная и описанная окружности
Признак равенства прямоугольных треугольников (по гипотенузе и катету)
Решение линейных уравнений с параметром и модулем
Блочная система обучения математике
Презентация на тему Многочлен и его стандартный вид
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть