Mapa Routing, jen Google Maps la?

hlasů
19

Vždycky jsem byl zaujat Mapa směrování, ale nikdy jsem našel nějaké dobré úvodní (nebo i pokročilé!) Úroveň výukových programů na něm. Má někdo nějaké odkazy, rady, atd?

UPDATE: Já jsem v první řadě hledají ukazatele, jak je implementován mapy systém (datové struktury, algoritmy, atd).

Položena 05/08/2008 v 21:24
zdroj uživatelem
V jiných jazycích...                            


9 odpovědí

hlasů
14

Podívejte se na otevřené ulici mapě projektu vidět, jak něco takového je řešen Truely projekt svobodného software používat pouze uživatel dodávány a licencovány dat a mají wiki obsahuje věci, které by vás mohly najít zajímavé .

Před několika lety se lidé účastní, kde docela snadné jít a odpověděl na mnoho otázek, které jsem měl, takže nevidím důvod, proč oni ještě nejsou pěkné parta.

Odpovězeno 05/08/2008 v 21:27
zdroj uživatelem

hlasů
4

A * je ve skutečnosti mnohem blíže k mapování výroba algoritmů. To vyžaduje trochu menší průzkum v porovnání s Dijikstra původní algoritmus.

Odpovězeno 25/09/2008 v 00:19
zdroj uživatelem

hlasů
4

Barry Brumitt, jeden z inženýrů mapu Google nález cesta funkce, napsal příspěvek na téma, které by Vás mohly zajímat:

Cesta k lepší cesta ke zjištění 11/06/2007 03:47:00 PM

Odpovězeno 17/09/2008 v 09:44
zdroj uživatelem

hlasů
4

Na mapě směrování, myslíš najít nejkratší cestu podél uliční sítě?

Dijkstra algoritmus nejkratší cesta je nejznámější. Wikipedia nemá špatný úvod: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

K dispozici je Java applet tady, kde ji můžete vidět v akci: http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html a Google vám vás vést k zdrojového kódu v téměř jakýkoli Jazyk.

Jakékoli skutečné implementace pro generování jízdní trasy budou obsahovat trochu dat o silniční síti, který popisuje spolupracovník náklady s pojezdovými odkazy a uzly v terénu hierarchii sítě, průměrnou rychlost, priorita křižovatky, dopravní signalizace propojení, zakázaných zatáčkách atd

Odpovězeno 15/08/2008 v 05:31
zdroj uživatelem

hlasů
2

Z koncepčního hlediska představit klesá kámen do rybníka a pozoroval vlnky. Tyto trasy by představoval rybník a kamenný svou startovní pozici.

Samozřejmě, že algoritmus bude muset hledat nějaký podíl n ^ 2 cestách, jako je zvýšení n vzdálenosti. Ty by vás výchozí polohy a nechte si zobrazit všechny dostupné cesty od tohoto bodu. Pak rekurzivně zavolá bodů na konci těchto cest a tak dále.

Můžete zvýšit výkon tím, že ne dvojího podporou na cestě, tím, že znovu kontrolu trasy v místě, pokud již byly zahrnuty i tím, že se na cesty, které jsou příliš dlouho.

Alternativním způsobem je použití ant feromon přístup, kde mravenci procházet náhodně z výchozího bodu a zanechat pachovou stopu, který se tvoří, tím více mravenci přejet danou cestu. Pokud budete posílat (dost) mravenci jak z počátečního bodu a koncového bodu pak nakonec cestu s nejsilnějším pachem bude co nejkratší. Důvodem je, že nejkratší cesta bude byly navštívil vícekrát v daném časovém období, vzhledem k tomu, že mravenci chodit na jednotné tempem.

EDIT @ Spikie

Jako další vysvětlení, jak implementovat algoritmus Rybník - potenciální datové struktury potřebné jsou zvýrazněny:

Budete muset uložit mapu jako síť. To je prostě soubor nodesa edgesmezi nimi. Soubor nodestvoří route. Hrana spojuje dva uzly (případně oba stejné uzlu), a má související cost, jako je distance, nebo timeprocházet okraj. Hrana může buď být buď obousměrná nebo jednosměrná. Pravděpodobně nejjednodušší, aby se jen ty jednosměrné a zdvojnásobit pro obousměrné cesty mezi uzly (tj jednoho okraje z A do B a jinou pro B do A).

Jako příklad si představit tři železničních stanic, uspořádaných v rovnostranném trojúhelníku směřuje nahoru. K dispozici jsou také další tři stanice každý na půl cesty mezi nimi. Hrany spojit všechny sousední stanice dohromady, konečné schéma bude mít obrácený trojúhelník sedí uvnitř větší trojúhelníku.

Označení uzly již od vlevo dole, které jdou zleva doprava a nahoru, jako A, B, C, D, E, F (F nahoře).

Předpokládejme, že hrany mohou být posunut v obou směrech. Každá hrana má náklady na 1 km.

Ok, takže chceme, aby na cestě z levé dolní části A do horní stanice F. Existuje mnoho možných cest, včetně těch, které zdvojnásobí zpět na sebe, např ABCEBDEF.

Máme rutinní vyjádřit, NextNode, která přijímá nodea A costa volá sám pro každý uzel může cestovat.

Je jasné, kdybychom tuto rutinní běh bude nakonec zjistit všechny trasy, včetně těch, které jsou potenciálně nekonečné délky (např ABABABAB atd). My tomu zabránit kontrolou proti cost. Kdykoliv jsme se navštívit uzel, který nebyl dříve navštívili, jsme dali jak nákladů a uzel jsme přišli proti tomuto uzlu. Pokud uzel byl již dříve navštívili jsme zkontrolovat proti stávající cenu a když budeme mít levnější pak aktualizovat uzlu a pokračovat (rekurzi). Pokud budeme mít dražší, pak bychom vynechat uzel. Jsou-li vynechány všechny uzly a pak opustíme rutinu.

Budeme-li zasáhnout naši cílovou uzel pak opustíme rutinu taky.

Tímto způsobem všechny životaschopnými cesty jsou kontrolovány, ale zásadně jen ty s co nejnižšími náklady. Na konci tohoto procesu každý uzel bude mít nejnižší náklady na získání do tohoto uzlu, včetně našeho cílového uzlu.

Chcete-li získat trasu pracujeme zpět od našeho cílového uzlu. Protože jsme skladovat uzel jsme přišli spolu s náklady, my prostě hop zpět vybudování trasy. Pro náš příklad bychom skončit s něčím, jako je:

Uzel A - (celkem) náklady 0 - z uzlu Žádný
uzel B - náklady 1 - z uzlu A
uzel C - náklady 2 - z uzlu B
uzlu D - náklady 1 - z uzlu A
uzel E - náklady 2 - od uzlu D / náklady 2 - z uzlu B (to je výjimkou, že se rovná náklady)
uzel F - náklady 2 - od uzlu D

Takže nejkratší cesta je ADF.

Odpovězeno 26/09/2008 v 15:05
zdroj uživatelem

hlasů
2

Ještě jsem najít dobrý návod na směrování, ale existuje spousta kódu číst:

Existuje GPL směrování aplikace, které využívají dat OpenStreetMap, např Gosmore který pracuje na systému Windows (+ Mobile) a Linux. Existuje celá řada zajímavých [aplikací využívajících stejná data, ale gosmore má nějaké chladné používá např rozhraní s webovými stránkami .

Největším problémem při směrování je chybná data, a vy nikdy dost dobrá data. Takže pokud si chcete vyzkoušet, že udržet svůj test velmi lokální, takže můžete kontrolovat data lépe.

Odpovězeno 17/09/2008 v 09:34
zdroj uživatelem

hlasů
2

Místo toho, aby učení API každého poskytovatele satelitní služby (jako GMaps, Ymaps API) jeho dobré naučit Mapstraction

„Mapstraction je knihovna, která poskytuje společné API pro různé javascript mapování API“

Navrhoval bych vám jít na URL a naučit obecné API. Tam je dobré množství návody taky.

Odpovězeno 06/08/2008 v 14:35
zdroj uživatelem

hlasů
1

Z mé zkušenosti s prací v této oblasti, A * dělá svou práci velmi dobře. To je (jak je uvedeno výše), rychleji než Dijkstrův algoritmus, ale je stále ještě dostatečně jednoduché pro běžně příslušný programátor implementovat a pochopit.

Budování sítě trasy je ta nejtěžší část, ale které mohou být rozděleny do několika jednoduchých krocích: dostat všechny silnice; třídit body do pořadí; aby skupiny identických bodů na různých cestách do průsečíků (uzly); přidat oblouky v obou směrech, kdy uzly spojují (nebo pouze v jednom směru pro jednosměrný silnici).

A * algoritmus sám je dobře zdokumentováno na Wikipedii . Klíčovým místem k optimalizaci je výběr toho nejlepšího uzlu z otevřeného seznamu, pro které budete potřebovat vysoce výkonný prioritní fronty a. Pokud používáte C ++ můžete použít STL priority_queue adaptér.

Přizpůsobení algoritmus pro směrování přes různých částech sítě (např chodec, automobil, veřejná doprava, atd.), Rychlosti, vzdálenosti prospěch nebo jiných kritérií je poměrně snadné. Uděláte to písemně filtrů pro řízení, které segmenty trasy jsou k dispozici při vytváření sítě, a která váha je přiřazen ke každé z nich.

Odpovězeno 15/07/2012 v 22:13
zdroj uživatelem

hlasů
1

Další myšlenka se mi, pokud jde o náklady na každý průchod, ale zvýší čas a výpočetní výkon potřebný pro výpočet.

Příklad: K dispozici jsou 3 způsoby, jak mohu vzít (kde bydlím) jít z bodu A do bodu B, v závislosti na GoogleMaps. Garmin jednotky nabízejí každý z těchto 3 tras ve Quickestvýpočtu trasy. Po křížení každé z těchto cest mnohokrát a průměrování (zřejmě bude chyby v závislosti na denní době, množství kofeinu atd), mám pocit, že algoritmy mohl vzít v úvahu počet ohybů v cestě za vysokou přesností , například rovné silnici 1 míli bude rychlejší než 1 mil silnici s ostrými zatáčkami v něm . Nejedná se o praktický návrh, ale určitě ten, který jsem použít k zlepšení sadu výsledků mé každodenní dojíždění.

Odpovězeno 18/09/2011 v 22:34
zdroj uživatelem

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more