Dr Oleksandr Klosov

PWSZ Legnica,

Algorytmy i Struktury Danych

Wykład

GEOMETRIA OBLICZENIOWA

[1] www.binboy.org

[2] www.algorytm.pl

[3] T.Cormen, ..., Wprowadzenie do algorytmów

PLAN

1. Do czego służy geometria obliczeniowa

2. Wzajemne położenie punktów na płaszczyźnie

3. Przecinanie się odcinków

4. Budowanie wypukłej otoczki dla zbioru punktów

5. Transformacja obrazów 3-D na 2-D

WPROWADZENIE

Geometria obliczeniowa - dział informatyki zajmujący się algorytmami, które rozwiązują problemy geometryczne i znajdują swoje zastosowanie w:

• grafice komputerowej;

• projektowaniu układów VLSI;

• robotyce;

• systemach CAD;

• statystyce.

Rozwiązywane problemy można podzielić na:

• geometrię obliczeniową na płaszczyźnie;

• geometrię obliczeniową w przestrzeni 3-wymiarowej;

• geometrię obliczeniową w przestrzeni n-wymiarowej.

WSPÓŁLINIOWOŚĆ TRZECH PUNKTÓW

A=(x_a, y_a)

B=(x_b, y_b)

C=(x_c, y_c)

= (x_ay_b + x_by_c + x_cy_a) - (x_cy_b + x_by_a + x_ay_c)

ALG1

det(A,B,C) < 0

det(A,B,C) = 0

det(A,B,C) > 0

PRZYNALEŻNOŚĆ PUNKTU DO ODCINKA

A=(x_a, y_a)

B=(x_b, y_b)

C=(x_c, y_c)

D=(x_d ,y_d)

Udowodnienie, że punkt C należy do odcinka |AB|:

1 krok. Udowodnić, że punkty A,B i C leżą na jednej linii (det = 0)

2 krok. Pokazać, że współżędne x, y punktu C mieszczą się w projekcjach

odcinka AB odpowiednio na oś X oraz Y.

ALG2

min(x_a, x_b) <= x_c <= max(x_a, x_b)

min(y_a, y_b) <= y_c <= max(y_a, y_b)

PRZECINANIE SIĘ ODCINKÓW

Problem:

Dano zbiór czterech punktów na płaszczyźnie (p₁, p₂, p₃, p₄). Stwierdzić czy odcinki p₁p₂ i p₃p₄ się przecinają.

Rozwiązanie:

1. Odcinki się przecinaja, jeżeli dowolny koniec jednego odcinka należy do drugiego odcinka;

2. Odcinki się przecinaja, jeżeli jednocześnie spełnia się dwa warunki:

1. 
   punkty p₁, p₂ leżą po róznych stronach względem odcinka p₃p₄;

2. 
   punkty p₃, p₄ leżą po róznych stronach względem odcinka p₁p₂.

PRZECINANIE SIĘ ODCINKÓW

ALG3

Dano:

p₁=(x₁, y₁), p₂=(x₂, y₂), p₃=(x₃, y₃), p₄=(x₄ ,y₄)

sign(argument) - funkcja zwracająca znak argumentu

if należy(p₁, p₂, p₃) or

należy(p₁, p₂, p₄) or

należy(p₃, p₄, p₁) or

należy(p₃, p₄, p₂)

then Przecinają się;

else

if sign(det(p₁, p₂, p₃)) <> sign(det(p₁, p₂, p₄)) and

sign(det(p₃, p₄, p₁)) <> sign(det(p₃, p₄, p₂))

then Przecinają się;

else Nie przecinają się;

PRZYNALEŻNOŚĆ PUNKTU DO OBSZARU

Dano obszar P = |P₁ ... P_n|, P_i = (x_i,y_i).

Stwierdzić czy punkt A = (x_a,y_a) należy do obszaru (łącznie z granicą).

PRZYNALEŻNOŚĆ PUNKTU DO OBSZARU

Rozwiązanie

Wyznaczamy punkt B poza obszarem P taki, że B = (max(P_x)+1,a_y)

Punkt A należy do obszaru, jeżeli liczba boków przecinających się

z odcinkiem |AB| jest nieparzysta.

Budowanie otoczki wypukłej dla zbioru punktów

Dano zbiór punktów P = |P₁ ... P_n|, P_i = (x_i,y_i).

Znaleźć otoczkę wypukłą - najmniejszy wielokąt wypukły taki, że każdy punkt zbioru P leży albo na brzegu wielokąta albo w jego wnętrzu.

ROZWIĄZANIE PROBLEMU

Algorytm Grahama Algorytm Jarvisa

O(n lg n) O(nh)

Każdy z algorytmów wykorzystuję przetwarzanie punktów w kolejności występowania kątów jakie tworzą z ustalonym punktem a przechodzącą przez niego osią.

OPIS ALGORYTMÓW

Algorytm Grahama

Algorytm wykorzystuję strukturę typu stos. Wszystkie punkty znajdujące się na stosie pod koniec algorytmu stanowią poszukiwaną otoczkę wypukłą. Na początku wyznacza się punkt startowy P1, jako najniżej położony na płaszczyźnie punkt. Następnie oblicza się kąty nachylenia pozostałych punktów względem P1, co ustala kolejność rozpatrywania punktów.

Punkt P2 jest brany do otoczki bezwarunkowo i odkładany na stos.

W kolejnych krokach algorytmu rozpatrywane są trzy kolejne punkty, n.p. P1, P2, P3. Jeżeli wektor P2P3 oznacza skręt w lewo względem wektora P1P2, to punkt P3 odkładamy na stos, jest on traktowany jako kandydat do otoczki. Rozpatrujemy kolejne punkty P2, P3, P4. Jeżeli wektor P3P4 skręca w prawo, to zdejmujemy punkt P3 ze stosu i przechodzimy do rozpatrywania punktów P1, P2, P4.

Algorytm kończy działanie kiedy przejdziemy przez wszystkie punkty.

Algorytm Jarvisa

Algorytm posługuje się metodą znaną jako owijanie. Po wyznaczeniu punktu początkowego, jak w poprzedniej metodzie, algorytm wykonuje powtarzające się kroki polegające na: a) wyznaczeniu kątów nachylenia punktów względem punktu bieżącego; b) wybraniu punktu o najmniejszym kącie jako punktu bieżącego oraz zaliczeniu go do otoczki.

Ponieważ po osiągnięciu w pewnym momencie najwyżej położonego punktu kąty nachylenia będą ujemne, dalsze działania opierają się na wyznaczeniu największego kąta (lub najmniejszego ujemnego). Tak powstają dwa łańcuchy: prawy, rozpoczynający się w punkcie początkowym oraz lewy, kończący się w tym punkcie, które stanowią poszukiwaną otoczkę.

KONWERSJA OBRAZÓW 3D na 2D

XP = XV + (XV - X) * ZV / (Z - ZV)

YP = YV + (YV - Y) * ZV / (Z - ZV)

gdzie:

X,Y,Z - współrzędne punktu w trzech wymiarach

XP,YP - współrzędne po konwersji na 2D

XV,YV,ZV - położenie obserwatora

CO TRZEBA UMIEĆ NA ZALICZENIE

1. Jak wyznaczyć wzajemne położenie trzech punktów na płaszczyźnie

2. Jak wyznaczyć czy dwa odcinki się przecinają

3. Jak działają algorytmy Grahama oraz Jarvisa

4. 
   Opisać koncepcję wyznaczenia przynależności punktu do obszaru

Algorytmy i Struktury Danych, wykład, dr. O.Klosow

x_a x_c x_b X

Y

y_b

y_c

y_a

0

P1

P2

P3

P4

---