Dr Aleksander Klosow
PWSZ Legnica, 2003
www.strony.wp.pl/wp/klosov/
Algorytmy i Struktury Danych
Wykład 8
GEOMETRIA OBLICZENIOWA
[1] www.binboy.org
[2] www.algorytm.cad.pl
[3] T.Cormen, ..., Wprowadzenie do algorytmów
Algorytmy i Struktury Danych, wykład 8, dr. A.Klosow
PLAN
1. Do czego służy geometria obliczeniowa
2. Wzajemne położenie punktów na płaszczyz
nie
3. Przecinanie się odcinków
4. Budowanie wypukłej otoczki dla zbioru punktów
5. Transformacja obrazów 3-D na 2-D
Algorytmy i Struktury Danych, wykład 8, dr. A.Klosow
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łaszczyz
nie;
- geometrię obliczeniową w przestrzeni 3-wymiarowej;
- geometrię obliczeniową w przestrzeni n-wymiarowej.
Algorytmy i Struktury Danych, wykład 8, dr. A.Klosow
WSPÓA
LINIOWOŚĆ TRZECH PUNKTÓW
A=(xa, ya)
B=(xb, yb)
C=(xc, yc)
xa ya 1
det(A, B,C) = xb yb 1 =
xc yc 1
= (xayb + xbyc + xcya) - (xcyb + xbya + xayc)
Algorytmy i Struktury Danych, wykład 8, dr. A.Klosow
C.D.
det(A,B,C) < 0
det(A,B,C) = 0
det(A,B,C) > 0
Algorytmy i Struktury Danych, wykład 8, dr. A.Klosow
PRZYNALEŻNOŚĆ PUNKTU DO ODCINKA
A=(xa, ya)
B=(xb, yb)
C=(xc, yc)
D=(xd ,yd)
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.
Algorytmy i Struktury Danych, wykład 8, dr. A.Klosow
C.D.
Y
xa ya 1
yb
yc
det(A, B,C) = xb yb 1 = 0
xc yc 1
min(xa, xb) <= xc <= max(xa, xb)
ya
min(ya, yb) <= yc <= max(ya, yb)
0
xa xc xb X
Algorytmy i Struktury Danych, wykład 8, dr. A.Klosow
PRZECINANIE SI
ODCINKÓW
Problem:
Dano zbiór czterech punktów na płaszczyz
nie (p1, p2, p3, p4). Stwierdzić czy
odcinki p1p2 i p3p4 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:
a) punkty p1, p2 leżą po róznych stronach względem odcinka p3p4;
b) punkty p3, p4 leżą po róznych stronach względem odcinka p1p2.
Algorytmy i Struktury Danych, wykład 8, dr. A.Klosow
PRZECINANIE SI
ODCINKÓW
Algorytm
Dano:
p1=(x1, y1), p2=(x2, y2), p3=(x3, y3), p4=(x4 ,y4)
sign(argument) - funkcja zwracająca znak argumentu
if det(p1, p2, p3) = 0 or
det(p1, p2, p4) = 0 or
det(p3, p4, p1) = 0 or
det(p3, p4, p2) = 0
then Przecinają się;
else
if sign(det(p1, p2, p3)) <> sign(det(p1, p2, p4)) and
sign(det(p3, p4, p1)) <> sign(det(p3, p4, p2))
then Przecinają się;
else Nie przecinają się;
Algorytmy i Struktury Danych, wykład 8, dr. A.Klosow
PRZYNALEŻNOŚĆ PUNKTU DO OBSZARU
Dano obszar P = |P1 ... Pn|, Pi = (xi,yi).
Stwierdzić czy punkt A = (xa,ya) należy do obszaru (łącznie z granicą).
Algorytmy i Struktury Danych, wykład 8, dr. A.Klosow
PRZYNALEŻNOŚĆ PUNKTU DO OBSZARU
Rozwiązanie
Wyznaczamy punkt B poza obszarem P taki, że B = (max(Px)+1,ay)
Punkt A należy do obszaru, jeżeli liczba boków przecinających się
z odcinkiem |AB| jest nieparzysta.
Algorytmy i Struktury Danych, wykład 8, dr. A.Klosow
BUDOWANIE OTOCZKI WYPUKA
EJ DLA ZBIORU PUNKTÓW
Dano zbiór punktów P = |P1 ... Pn|, Pi = (xi,yi).
Znalez
ć 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.
Algorytmy i Struktury Danych, wykład 8, dr. A.Klosow
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ą.
Algorytmy i Struktury Danych, wykład 8, dr. A.Klosow
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łaszczyz
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. Jeżeli
skręcamy w prawo, to zdejmujemy punkt P2 ze stosu i przechodzimy do rozpatrywania punktów P2, P3, 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ę.
Algorytmy i Struktury Danych, wykład 8, dr. A.Klosow
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
Algorytmy i Struktury Danych, wykład 8, dr. A.Klosow
CO TRZEBA UMIEĆ NA ZALICZENIE
1. Jak wyznaczyć wzajemne położenie trzech punktów na płaszczyz
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 8, dr. A.Klosow