Algorytmy i struktury danych - 08. ...

[ 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 ]