Algorytmy i struktury danych - 08. Algorytmy geometryczne, Studia podyplomowe - mechatronika i coś tam jeszcze, ...
[ Pobierz całość w formacie PDF ]
Algorytmy i Struktury danych, wer. C/C++, Lekcja 8: Algorytmy geom...
1
Lekcja 8: Algorytmy geometryczne
Wst
ħ
p
Na zako
ı
czenie tego kursu proponujemy Wam krótk
Ģ
lekcje przegl
Ģ
dow
Ģ
na temat najbardziej popularnych algorytmów
geometrycznych. Tym razem nie b
ħ
dzie szczegółowego, precyzyjnego opisu algorytmów, a raczej krótki rzut oka na problemy,
jakie w tej dziedzinie wyst
ħ
puj
Ģ
, z wykorzystaniem przygotowanych przez naszych studentów apletów i odwołaniem si
ħ
do
ciekawych zasobów sieciowych. Zwrócimy uwag
ħ
na znane ju
Ň
Wam kategorie algorytmów i struktury danych szczególnie
przydatne w geometrycznych implementacjach.
Otoczka wypukła i triangulacja Delaunaya
Poszukiwanie otoczki wypukłej zbioru punktów stanowi jeden z najbardziej popularnych algorytmów geometrii obliczeniowej.
Przez otoczk
ħ
wypukł
Ģ
zbioru punktów na płaszczy
Ņ
nie rozumie si
ħ
najmniejszy wielok
Ģ
t wypukły taki,
Ň
e wszystkie punkty
zbioru le
ŇĢ
albo wewn
Ģ
trz wielok
Ģ
ta, albo na jego brzegu. Zadanie to bywa
Ň
artobliwie nazywane "ogradzaniem
Ļ
pi
Ģ
cych
tygrysów". Znanych jest kilka ró
Ň
nych metod, które potrafi
Ģ
poradzi
ę
sobie z tym zadaniem w czasie rz
ħ
du O(n lg n). Jedn
Ģ
z
najbardziej znanych jest
algorytm Grahama
, u
Ň
ywaj
Ģ
cy stosu, na którym przej
Ļ
ciowo składane s
Ģ
punkty b
ħ
d
Ģ
ce kandydatami
na wierzchołki otoczki, i w razie potrzeby s
Ģ
one ze stosu zdejmowane. Wszystkie punkty s
Ģ
sortowane ze wzgl
ħ
du na
współrz
ħ
dn
Ģ
k
Ģ
tow
Ģ
ich poło
Ň
enia (liczonego w kierunku przeciwnym do ruchu wskazówek zegara) wzgl
ħ
dem punktu o
minimalnej współrz
ħ
dnej y.Umiej
ħ
tno
Ļę
implementacji algorytmu zwi
Ģ
zana jest z konieczno
Ļ
ci
Ģ
uwzgl
ħ
dniania rozmaitych
przypadków szczególnych, których w geometrii obliczeniowej jest du
Ň
o. Przykład implementacji mo
Ň
ecie obejrze
ę
na
zał
Ģ
czonym aplecie:
Triangulacja Delaunaya jest to taki podział przestrzeni wyznaczonej zbiorem punktów na płaszczy
Ņ
nie, który dzieli otoczk
ħ
wypukł
Ģ
zbioru punktów na trójk
Ģ
ty w taki sposób,
Ň
e
Ň
aden punkt nie le
Ň
y wewn
Ģ
trz okr
ħ
gu opisanego na dowolnym trójk
Ģ
cie:
2008-04-13 01:39
Algorytmy i Struktury danych, wer. C/C++, Lekcja 8: Algorytmy geom...
2
Tak uzyskany podział na trójk
Ģ
ty ma t
ħ
własno
Ļę
,
Ň
e maksymalizuje minimalny k
Ģ
t spo
Ļ
ród wszystkich trójk
Ģ
tów nale
ŇĢ
cych do
triangulacji. Dzi
ħ
ki temu w maksymalnie mo
Ň
liwym stopniu unika si
ħ
trójk
Ģ
tów o małych k
Ģ
tach, czyli "długich i w
Ģ
skich".
Triangulacja Delunaya znajduje zastosowanie w wielu ró
Ň
nych dziedzinach wymagaj
Ģ
cych zast
Ģ
pienia zbioru punktów siatk
Ģ
trójk
Ģ
tów. Najprostszy algorytm triangulacji jest algorytmem
przyrostowym
, polegaj
Ģ
cym na dodawaniu kolejnych punktów do
zbioru trójk
Ģ
tów, sprawdzaniu otoczenia dodawanego punktu i retriangulacji tego otoczenia w razie potrzeby. Algorytm ma
zło
Ň
ono
Ļę
obliczeniow
Ģ
O(n
2
) i mo
Ň
e by
ę
przyspieszony z wykorzystaniem algorytmu
zamiatania płaszczyzny
, pokazanego w
rozdziale nast
ħ
pnym.
Inn
Ģ
metod
Ģ
, która pozwala na obni
Ň
enie zło
Ň
ono
Ļ
ci do poziomu O(n lg n), jest metoda
"dziel i zwyci
ħŇ
aj"
, która rekurencyjnie
dzieli zbiór punktów na dwa zbiory, dla ka
Ň
dego wyznacza triangulacj
ħ
Delaunaya, a nast
ħ
pnie ł
Ģ
czy obie triangulacje w jedn
Ģ
wynikow
Ģ
. Jak zwykle, etap ł
Ģ
czenia jest to najtrudniejszy krok tego algorytmu, szczególnie trudny w aspekcie oblicze
ı
geometrycznych.
Kolejny bardzo ciekawy pomysł wyznaczenia triangulacji Delaunaya polega na wykorzystaniu faktu,
Ň
e jest ona rzutem otoczki
wypukłej 3D wyznaczonej dla punktów o współrz
ħ
dnych (x, y, x
2
+y
2
), gdzie punkty (x,y) tworz
Ģ
zbiór zadany. Ten wła
Ļ
nie
algorytm został zaimplementowany w oryginalny sposób w aplecie, który prezentujemy poni
Ň
ej; mo
Ň
ecie tu w bardzo wygodny
sposób dorzuca
ę
punkty do zbioru i obserwowa
ę
otoczk
ħ
3D zbudowan
Ģ
na paraboloidzie (bardzo plastycznie zwizualizowan
Ģ
)-
oraz efekt ko
ı
cowy, czyli wyznaczan
Ģ
w trybie on-line triangulacj
ħ
Delaunaya.
2008-04-13 01:39
Algorytmy i Struktury danych, wer. C/C++, Lekcja 8: Algorytmy geom...
3
Bardzo ciekawe aplety, które porównuj
Ģ
czasy działania i stopie
ı
zło
Ň
ono
Ļ
ci ró
Ň
nych algorytmów wyznaczaj
Ģ
cych triangulacj
ħ
Delaunaya, mo
Ň
ecie znale
Ņę
tutaj
oraz
tutaj
Z triangulacj
Ģ
Delaunaya nierozerwalnie zwi
Ģ
zany jest (jako tzw. jej graf dualny)
diagram Voronoi
, czyli taki podział przestrzeni
na obszary wokół zadanych punktów zbioru,
Ň
e wszystkie punkty obszaru le
Ģ
bli
Ň
ej zadanego punktu zbioru ni
Ň
wzgl
ħ
dem
jakiegokolwiek innego punktu tego zbioru. Przykładem zastosowania jest podział terenu na obszary le
ŇĢ
ce w jak najbli
Ň
szej
odległo
Ļ
ci wokół masztów nadajników sieci komórkowych. Przykład diagramu wygenerowanego jednym z powy
Ň
szych apletów
przedstawia rysunek:
Metoda zamiatania płaszczyzny
Metoda zamiatania płaszczyzny (ang.
sweeping plane
) jest cz
ħ
sto spotykana w algorytmach geometrii obliczeniowej.
Zastosowanie jej pozwala zmniejszy
ę
zło
Ň
ono
Ļę
obliczeniow
Ģ
wielu algorytmów z poziomu O(n
2
) do poziomu O(n lg n).
Typowym przykładem zastosowania jest zagadnienie wyznaczania par przecinaj
Ģ
cych si
ħ
odcinków.
Pionowa prosta przesuwaj
Ģ
ca si
ħ
na płaszczy
Ņ
nie od strony lewej do prawej pełni rol
ħ
miotły, która pozwala systematycznie
przegl
Ģ
da
ę
pojawiaj
Ģ
ce si
ħ
podczas przesuwania obiekty geometryczne i sprawdza
ę
zachodz
Ģ
ce mi
ħ
dzy nimi zale
Ň
no
Ļ
ci.
Zatrzymania miotły nast
ħ
puj
Ģ
tylko w w tych charakterystycznych miejscach okre
Ļ
lonych współrz
ħ
dn
Ģ
x i pełni
Ģ
rol
ħ
zdarze
ı
.
2008-04-13 01:39
Algorytmy i Struktury danych, wer. C/C++, Lekcja 8: Algorytmy geom...
4
W przypadku algorytmu sprawdzania przecinania si
ħ
odcinków zaczyna si
ħ
od uporz
Ģ
dkowania zbioru ko
ı
ców odcinków
wzgl
ħ
dem współrz
ħ
dnej x (trzeba przy tym rozstrzygn
Ģę
problem, który si
ħ
pojawia, gdy dwa ko
ı
ce maj
Ģ
tak
Ģ
sam
Ģ
współrz
ħ
dn
Ģ
). Odcinki przechowywane s
Ģ
w strukturze
drzewa czerwono-czarnego
, która pozwala na efektywne (w czasie O(lg
n)) operacje dodawania odcinków do zbioru, gdy miotła napotyka jego lewy koniec, i usuwania go ze struktury, gdy napotyka
prawy koniec. Sprawdzenie przecinania si
ħ
dwóch odcinków nast
ħ
puje wtedy, gdy po raz pierwszy staj
Ģ
si
ħ
one s
Ģ
siadami w
liniowo uporz
Ģ
dkowanym (poprzez struktur
ħ
drzewa czerwono-czarnego) zbiorze odcinków.
Okazuje si
ħ
,
Ň
e zagadnienie wyznaczenia triangulacji Delaunaya i diagramu Voronoi równie
Ň
mo
Ň
e by
ę
rozwi
Ģ
zane metod
Ģ
zamiatania płaszczyzny. Znakomity aplet, który obrazowo pokazuje ide
ħ
tej metody, mo
Ň
ecie uaktywnic klikaj
Ģ
c w poni
Ň
szy
obrazek,
bedacy
zrzutem
ekranu
z
tego
apletu,
dost
ħ
pnego
na
stronie
Struktura half-edge w reprezentacji brył
Na zako
ı
czenie tej lekcji poka
Ň
emy Wam przykład zło
Ň
onej struktury listowej budowanej na wska
Ņ
nikach, która ma du
Ň
e
praktyczne znaczenie w reprezentacji brył. Chodzi o tak
Ģ
reprezentacj
ħ
, w której bryła jest aproksymowana ci
Ģ
giem płaskich
Ļ
cian. W wielu przypadkach tak
Ģ
struktur
ħ
zapami
ħ
tuje si
ħ
bardzo prosto - jako list
ħ
wszystkich wierzchołków i list
ħ
Ļ
cian, z
których ka
Ň
da okre
Ļ
lona jest przez adresy wierzchołków:
2008-04-13 01:39
Algorytmy i Struktury danych, wer. C/C++, Lekcja 8: Algorytmy geom...
5
Bardziej zło
Ň
one struktury polegaj
Ģ
na tworzeniu dodatkowo listy kraw
ħ
dzi, dzi
ħ
ki czemu kraw
ħ
dzie przy wy
Ļ
wietlaniu nie s
Ģ
rysowane dwukrotnie (dla ka
Ň
dej przyległej
Ļ
ciany osobno); lambda na rysunku oznacza wska
Ň
nik NULL/
nil
.
Tu jednak chcemy pokaza
ę
struktur
ħ
jeszcze bardziej zło
Ň
on
Ģ
. Popatrzcie na rysunek:
W tym przypadku ka
Ň
da kraw
ħ
d
Ņ
jest reprezentowana przez dwie bli
Ņ
niacze półkraw
ħ
dzie, zwrócone w kierunkach przeciwnych.
Ka
Ň
da półkraw
ħ
d
Ņ
(half-edge), zaznaczona tu na czerwono, zawiera wska
Ņ
nik na:
półkraw
ħ
d
Ņ
przeciwn
Ģ
do danej
wierzchołek ko
ı
cowy półkraw
ħ
dzi danej
Ļ
cian
ħ
przyległ
Ģ
do danej półkraw
ħ
dzi
nast
ħ
pn
Ģ
półkraw
ħ
d
Ņ
tej
Ļ
ciany, liczon
Ģ
w kierunku przeciwnym do ruchu wskazówek zegara
poprzedni
Ģ
półkraw
ħ
d
Ņ
tej
Ļ
ciany.
Jest to typowa, aczkolwiek nie minimalna reprezentacja struktury powszechnie zwanej
half-edge
. Minimalna posta
ę
half-edge
zawiera tylko wska
Ņ
nik na półkraw
ħ
d
Ņ
przeciwn
Ģ
i nast
ħ
pn
Ģ
, wygodniejsza w u
Ň
yciu jest jednak struktura taka jak pokazali
Ļ
my,
2008-04-13 01:39
[ Pobierz całość w formacie PDF ]
