Viac

Nájdenie najkratšej cesty a vyhýbanie sa mnohouholníkovým funkciám


Vyvíjam rozšírenie do ArcMap, kde mám sadu statických, konkávnych mnohouholníkových prvkov a pokúšam sa nájsť najkratšiu cestu medzi 2 bodmi bez toho, aby som prekročil ktorýkoľvek z mnohouholníkov.

Existuje na to algoritmus?


Ak máte rozšírenie Spatial Analyst a nevadí vám pracovať s rastrovými reprezentáciami vašich údajov, môžete použiť Analýzu nákladovej cesty. Podrobnosti a ďalšie možnosti nájdete v téme pomocníka a príslušnom bočnom paneli pomocníka.


Raz som implementoval algoritmus, ktorý počíta polygón, ktorý zahŕňa plochu roviny (s polygonálnymi prekážkami), ktorú je možné dosiahnuť v určitej vzdialenosti. Najviac mi pomohlo, že som si to uvedomil problémy s najkratšou cestou v lietadle vyhýbajúcom sa prekážkam možno považovať za problémy s viditeľnosťou. Aj keď sa to v kontexte GIS často nehovorí, problémy s viditeľnosťou sú veľmi populárne a dobre dokumentované vo výpočtovej geometrii.

Na vyriešenie problému môžete použiť dva prístupy:

  1. Najkratšiu cestu môžete nájsť iba pomocou polygónov, ktoré sú relevantné, pomocou priestorového indexu, akým je napríklad strom R, aby vaše polygóny urýchlili prácu.

  2. Môžete vytvoriť graf pre všetky svoje polygóny a potom v ňom nájsť najkratšiu cestu.

Prístup 1. je lepší, ak nemôžete udržať vnútorný stav medzi časom, keď sa použije váš algoritmus. Ak musíte vypočítať veľa najkratších ciest a polygóny zostanú rovnaké, je lepší 2. prístup.

Prístup 1. je to, čo som urobil pre svoj algoritmus. To, čo som urobil, je v zásade toto:

  1. Nakreslite čiaru medzi počiatočným bodom a koncovým bodom.
  2. Pozrite sa, či pretína vnútro aspoň jedného mnohouholníka. Ak sa nepretína, je to vaša najkratšia cesta.
  3. Ak sa pretína, vezmite pretínajúci sa segment mnohouholníka, ktorý je najbližšie k počiatočnému bodu.
  4. Opakujte cez vrcholy mnohouholníka doľava a doprava, kým sa čiara medzi vrcholom a koncovým bodom nepretne s vnútornosťou mnohouholníka alebo kým sa priama čiara medzi vrcholom nepretne s iným mnohouholníkom. Ak sa pretnete s iným mnohouholníkom, prejdite na krok 2 s týmto mnohouholníkom. Ak nie, prejdite na krok 1 a zapamätajte si dĺžku medzi počiatočným bodom a vrcholom, ktorý je teraz novým počiatočným bodom.

Prístup 2. je pravdepodobne lepšie vhodný pre tu popísaný problém a mal by byť jednoduchšie implementovateľný.

Graf, ktorý potrebujete na smerovanie v rovine s mnohouholníkmi ako prekážkami, je graf viditeľnosti. Spôsob stavby hrubou silou je veľmi jednoduchý. Najprv vypočítajte konvexný trup svojich polygónov. Vrcholy, ktoré nie sú na konvexnom trupu, nemusia byť súčasťou grafu viditeľnosti. Vrcholy na konvexnom trupu sú uzly grafu viditeľnosti. Nakreslite čiaru medzi všetkými pármi vrcholov a zistite, či táto čiara pretína vnútro mnohouholníka. Ak čiara nepretína jeden z polygónov, je to hrana v grafe viditeľnosti.

Do grafu viditeľnosti musíte pridať svoj počiatočný a koncový bod. Potom môžete použiť algoritmus najkratšej cesty vážený z jedného zdroja. Dijkstrov algoritmus túto úlohu zvládne v pohode. Ak očakávate veľa otázok o najkratších cestách, môže stáť za to použiť algoritmus, ktorý vypočíta všetky najkratšie cesty a vopred vypočíta najkratšie cesty medzi všetkými pármi uzlov v grafe viditeľnosti.

Graf viditeľnosti je samozrejme možné použiť s existujúcimi nástrojmi smerovania, takže ak máte prístup k takémuto nástroju, nemusíte implementovať algoritmus najkratšej cesty. (Stále máte problém s tým, že musíte pridať počiatočný a koncový bod, ak ešte nie sú súčasťou siete)


Tu je ukážkový kód pomocou ArcObjects na nájdenie najkratšej cesty (pomocou RasterDistanceOP). Možno to nie je presne to, čo chcete, ale môže vám to poskytnúť východiskový bod.

Ako nájsť najkratšiu cestu pomocou RasterDistanceOp


Prvé myšlienky, ktoré mi napadli, sú tieto:

  1. Určte maximálne hranice všetkých funkcií, vrátane počiatočných a koncových bodov, trochu ich zafixujte, aby ste sa presvedčili, že okolo všetkých funkcií je priestor. Vytvorte obdĺžnikový prvok, b, od týchto hraníc.
  2. Odčítajte blokovacie funkcie od b.
  3. Tesselate b do trojuholníkov a uistite sa, že počiatočné a koncové vrcholy sú vrcholy v tejto novej trojuholníkovej sieti, m.
  4. Generujte Voronoiove polygóny, t (čo by mali byť všetky trojuholníky) z m.
  5. Okraje t Vytvorte sieť, na ktorej môžete spustiť algoritmus najkratšej cesty.

To nemusí generovať najlepšiu najkratšiu cestu, pretože to závisí od toho, ako tesselator vykonáva svoju prácu, a v každom prípade bude mať stredovú čiaru, nie závodnú. Je však mysliteľné, že po vygenerovaní najkratšej cesty môžete vrcholy presúvať alebo odstraňovať, pričom každý dotknutý okraj otestujete na priesečník s funkciami blokovania a ak sa operácia pretína, operáciu zrušíte.


Problém je komplikovaný. Existuje nová generická implementácia: Euklidovský algoritmus najkratšej cesty

Funguje to pre všetky sady predmetov zo sieťovaného povrchu


Ak vám nevadí prekladať nejaké C, môžete skript vyskúšať na http://alienryderflex.com/shortest_path/