Na seznam struktury Voron´eho bunˇek lze nahl´ıˇzet jako na orientovan´y graf s kladn´ym ohodnocen´ım hran (d´elka hrany). Pro nalezen´ı nejkratˇs´ı cesty ze startovn´ıho do c´ılov´eho vrcholu byl pouˇzit Dijkstr˚uv algoritmus [7]. V´ysledn´a napl´anovan´a cesta je pak pˇrevedena na B-spline kˇrivku, kter´a je vyuˇzita jako poˇc´ateˇcn´ı trajektorie pro optimalizaci.
2.3.1 Pˇrevod Voron´eho bunˇek pro pl´anovac´ı algoritmus
Vstupem pl´anovac´ıho algoritmu je seznam vˇsech vrchol˚u, kter´e definuj´ı stˇeny Voron´eho bunˇek ˇc´ast´ı pˇrek´aˇzek. Prvky seznamu vˇsech vrchol˚u jsou pops´any strukturou, kter´a
ob-Obr´azek 7: Nezpracovan´e stˇeny Voron´eho buˇnky
sahuje id vrcholu v seznamu, souˇradnice vrcholu a seznam v´yskytu dan´eho vrcholu v jed-notliv´ych buˇnk´ach a id tohoto vrcholu v konkr´etn´ı Voron´eho buˇnce. Identifik´ator vrcholu v konkr´etn´ı buˇnce je k´odov´an pomoc´ı vztahu
id=ic·1000000 +iv, (5)
kde ic je id Voron´eho buˇnky a iv je id vrcholu v r´amci Voron´eho buˇnky. Vztah (5) klade omezen´ı na poˇcet vrchol˚u v jedn´e buˇnce, kter´y nem˚uˇze b´yt vetˇs´ı jak jeden milion, protoˇze by pak negeneroval jednoznaˇcn´e id.
Postup vytv´aˇren´ı seznamu vrchol˚u pro pl´anovaˇc popisuje algoritmus 5. Na ˇr´adc´ıch 1 aˇz 6 se vytv´aˇr´ı seznam vˇsech vrchol˚u, kter´e tvoˇr´ı Voron´eho buˇnky. Na ˇr´adc´ıch 7 aˇz 13 se urˇc´ı v´yskyty jednotliv´ych vrchol˚u ve vˇsech buˇnk´ach. Na ˇr´adku 16 se vytv´aˇr´ı poloˇzkan seznamu vˇsech vrchol˚u sv, do kter´e se pˇridaj´ı ´udaje o souˇradnic´ıch vrcholu a seznam v´yskyt˚u z k.
Na ˇr´adku 18 se ze seznamuspodstan´ı prvky, kter´e jsou v seznamu v´yskyt˚u prvkun. T´ımto postupem je zajiˇstˇeno, ˇze v seznam sv budou vˇsechny vrcholy pouze jednou.
Napl´anovan´a cesta nesm´ı proch´azet pˇrek´aˇzkami, k tomuto ´uˇcelu byly oznaˇceny vˇsechny hrany, kter´e m´ıˇr´ı z pˇrek´aˇzky nebo do pˇrek´aˇzky. Pˇri hled´an´ı tˇechto hran se vyuˇzilo faktu, ˇ
ze tyto hrany zaˇc´ınaj´ı, respektive konˇc´ı, bl´ızko vrchol˚u pˇrek´aˇzek. V seznamu vˇsech vrchol˚u se najdou vrcholy, kter´e jsou dan´emu vrcholu pˇrek´aˇzky nejbl´ıˇze. Pro tyto vrcholy se urˇc´ı hrany, kter´ym se nastav´ı logick´y pˇr´ıznak.
Logick´y pˇr´ıznak kolize je tak´e nastaven hran´am, kter´e leˇz´ı v ohraniˇcen´ı cel´e mapy pˇrek´aˇzek nebo do nˇeho smˇeˇruj´ı. Nejprve se urˇc´ı stˇeny Voron´eho bunˇek, kter´e vytv´aˇr´ı hranici s ohraniˇcen´ım. Hran´am, kter´e zaˇc´ınaj´ı,respektive konˇc´ı, ve vrcholech tˇechto stˇen se opˇet
Vstup: seznam Voron´eho bunˇek sc
V´ystup: seznam vˇsech vrchol˚u sv ze seznamu Voron´eho bunˇek sc
1: for all Voron´eho buˇnkub zsc do
2: for all Vrchol v ze seznamu vrchol˚u buˇnky b do
3: Vytvoˇr poloˇzku seznamu sp jednotliv´ych vrchol˚u v.
4: Pˇridej poloˇzku do seznamu sp.
5: end for
6: end for
7: for all Poloˇzku s1 seznamu sp do
8: for all Poloˇzkus2 seznamusp do
9: if |s1s2|< mez then
10: Pˇridej poloˇzce s1 do seznamu v´yskytu identifik´ator s2.
11: end if
12: end for
13: end for
14: while sp nen´ı pr´azdn´y do
15: Vezmi posledn´ı prvek k z sp.
16: Vytvoˇr nov´y prvekn.
17: Do n pˇridej seznam v´yskyt˚u z k.
18: Odstraˇn z sp prvky, ve kter´ych se vyskytujen.
19: Pˇridejn do seznamu sv.
20: end while
Algoritmus 5: Algoritmus vytvoˇren´ı seznamu vrchol˚u pro pl´anovaˇc
nastav´ı pˇr´ıznak kolize. Tato ´uprava zajist´ı, ˇze napl´anovan´a cesta nevede po ohraniˇcen´ı cel´e mapy.
Algoritmus 6 popisuje Dijkstr˚uv algoritmus, kter´y slouˇz´ı k nalezen´ı nejkratˇs´ı cesty.
Na zaˇc´atku algoritmu 6 se vytvoˇr´ı prioritn´ı halda, kter´a m´a na zaˇc´atku vrchol s nejmenˇs´ı vzd´alenost´ı od startu. Pˇri inicializaci se vˇsem vrchol˚um nastav´ı vzd´alenost na nekoneˇcno.
Seznam pˇredku prev slouˇz´ı ke zpˇetn´emu urˇcen´ı nalezen´e cesty. Startovn´ı vrchol m´a pˇred-ka −1, coˇz je vyuˇzito pro ukonˇcen´ı zpˇetn´eho hled´an´ı cesty. V kaˇzd´em kroku se odebere jeden vrchol v prioritn´ı haldˇe, coˇz zajiˇst’uje koneˇcnost Dijkstrova algoritmu. Na ˇr´adku 10 je poˇc´ıt´ana nov´a vzd´alenost expandovan´eho vrcholu, kter´a vznikne seˇcten´ım dosavadn´ı vzd´alenosti expandovan´eho vrcholu a vzd´alenost´ı mezi expandovan´ym vrcholem a jeho po-tomkem. Pokud je nov´a vzd´alenost menˇs´ı jak vzd´alenost, kterou m´a potomek, tak se
po-Vstup: startovn´ı vrchols, c´ılov´y vrcholc, seznam vrchol˚u sv, seznam Voron´eho bunˇek sc
V´ystup: seznam vrchol˚u cestysvc
1: Vytvoˇr prioritn´ı haldu h seznamu sv.
2: Inicializuj prioritn´ı fronty, seznam˚u vzd´alenost´ıdist a pˇredkuprev.
3: dist[start] = 0; h.update(start, 0)
4: repeat
5: vrcholv s nejmenˇs´ı vzd´alenost´ı z h
6: Odstraˇnv z h.
7: if v! =cthen
8: Expanduj vrchol v do seznamu ex.
9: for all Poloˇzku ex0 seznamu ex do
21: Do seznamu svc pˇridej na zaˇc´atek c´ılov´y vrcholc.
22: u=prev[c]
23: while u! =−1do
24: Pˇrideju na zaˇc´atek seznamusvc
25: u=prev[u]
26: end while
Algoritmus 6: Dijkstr˚uv algoritmus
tomkovi nastav´ı nov´a vzd´alenost, expandovan´y vrchol jako rodiˇc a aktualizuje se hodnota vzd´alenosti potomka v prioritn´ı haldˇe.
Algoritmus 7 popisuje postup expanze vrcholu, kter´y vrac´ı seznam vrchol˚u potomk˚u.
Seznam Voron´eho bunˇek slouˇz´ı k filtraci pˇrechodu, kter´e by vedly po kolizn´ı hranˇe z
ex-pandovan´eho vrcholu do vrcholu potomka.
Vstup: expandovan´y vrchol ev, seznam vrchol˚u sv, seznam Voron´eho bunˇeksc V´ystup: seznam potomk˚u sp
1: Vezmi seznam v´yskytu vrchol˚usvv vrcholuev z sv.
2: for all poloˇzku ex0 seznamu svv do
3: Vezmi seznam hran h vrcholuex0.
4: for all Poloˇzkuh0 seznamu h do
5: if h0.twin nesmˇeˇruje do pˇrek´aˇzky then
6: Pˇridejh0.twin.vrchol do pomocn´eho seznamu psv
7: end if
8: end for
9: end for
10: for all poloˇzku psv0 seznamu psv do
11: Pˇridej do seznamusp vrchol z sv, kter´y odpov´ıd´a vrcholu psv0.
12: end for
13: Odstraˇn duplicitn´ı vrcholy v sp
Algoritmus 7: Expanze vrcholu pro Dijkstr˚uv algoritmus
Na obr´azku 8 je zobrazen v´ysledek pl´anov´an´ı pro mapu se dvˇema pˇrek´aˇzkami na vrcho-lech Voron´eho bunˇek. Zelen´a kuliˇcka oznaˇcuje startovn´ı vrchol a ˇcerven´a kuliˇcka oznaˇcuje c´ılov´y vrchol.
V dalˇs´ı f´azi se pˇrevede napl´anovan´a cesta do B-spline kˇrivky, kter´a se n´aslednˇe podle diskutovan´ych poˇzadavk˚u optimalizuje.