Térkép Routing, a la Google Maps?

szavazat
19

Mindig is izgatta Térkép Routing, de én soha nem találtam olyan jó bevezető (vagy akár haladó!) Szinten oktató rajta. Van valakinek bármilyen mutatók, tippeket, stb?

Frissítés: Én elsősorban keres mutatókat, hogy hogyan térkép rendszer bevezetése (adatstruktúrák, algoritmusok, stb.).

A kérdést 05/08/2008 21:24
a forrás felhasználó
Más nyelveken...                            


9 válasz

szavazat
14

Vessen egy pillantást a nyílt utcán térkép projekt , hogy milyen ez a fajta dolog fogtak egy truely szabad szoftver projekt kizárólag a felhasználó által megadott adatok és engedélyezett, és van egy wiki tartalmazó dolgot lehet találni érdekes .

Néhány évvel ezelőtt a fiúk részt, ahol nagyon könnyen megy, és válaszol sok kérdés volt, így nem látom okát, hogy miért is nem egy szép csokor.

Válaszolt 05/08/2008 21:27
a forrás felhasználó

szavazat
4

A * valójában sokkal közelebb áll a termelés feltérképezése algoritmusok. Szükség van egy kicsit kisebb, mint a felfedezés Dijikstra eredeti algoritmus.

Válaszolt 25/09/2008 00:19
a forrás felhasználó

szavazat
4

Barry Brumitt, az egyik mérnök a Google maps útvonal megállapítás jellemző, írt egy bejegyzést a témában, hogy érdekes lehet:

Az út jobb útkereső 11/06/2007 03:47:00

Válaszolt 17/09/2008 09:44
a forrás felhasználó

szavazat
4

Térképkészítőktől Routing, akkor azt jelenti megtalálni a legrövidebb utat Egy utcán hálózat?

Dijkstra legrövidebb út algoritmus a legismertebb. Wikipedia nem egy rossz intro: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Van egy Java applet van, ahol láthatjuk, hogy az intézkedés: http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html és a Google akkor vezet, hogy a forráskódot szinte bármilyen nyelv.

Bármilyen tényleges végrehajtása generáló vezetési útvonalak közé egy kicsit az adatok az utcai hálózat, amely leírja a költségek társult áthaladó kapcsolatok és csomópontok úthálózat hierarchia, átlagsebesség, kereszteződés elsőbbségi, jelzőlámpaváltók összekapcsolása, betiltották fordulatok stb

Válaszolt 15/08/2008 05:31
a forrás felhasználó

szavazat
2

Fogalmi szempontból elképzelni csepegtető követ a tóba, és figyeli a hullámok. Az útvonalak képviselné a tó, és a kő a kiinduló helyzetbe.

Természetesen az algoritmus kell keresni valamilyen arányban n ^ 2 utakat a távolság n növekszik. Azt elviszi kiindulási helyzetébe, és ellenőrizze az összes rendelkezésre álló utak attól a ponttól. Majd rekurzívan hívja a pontot a végén az említett utak és így tovább.

Akkor növeli a teljesítményt azáltal, hogy nem dupla hátlap egy utat, hogy nem újra ellenőrzi a útvonalakon egy pont, ha azt már lefedett és feladom utakat szed túl hosszú.

Egy másik módja az, hogy a hangya a feromon megközelítés, amely a hangyák másznak véletlenszerűen egy kezdőpontot, és hagyjuk egy illat nyomvonal, amely felépíti a több hangyák átmenni a megadott útvonalon. Ha egy (elég) hangyák mind a kezdőpont és a végpont, majd végül az utat a legerősebb illata lesz a legrövidebb. Ez azért van, mert a legrövidebb útvonal már látogatott több alkalommal egy adott időszakban, tekintettel arra, hogy a hangyák séta egyenletes ütemben.

EDIT @ Spikie

Egy további magyarázat, hogyan hajtsák végre a tó algoritmus - potenciális adatszerkezetek szükséges kiemelni:

El kell tárolni a térkép egy hálózatot. Ez egyszerűen egy sor nodes, és edgesa kettő között. Egy sor nodesminősül route. Egy él csatlakozik két csomópont (esetleg mindkettő azonos csomópont), és van egy társított cost, például distance, vagy time, hogy áthalad a szélén. Egy él lehet akár akár lehet kétirányú vagy egyirányú. Valószínűleg a legegyszerűbb, hogy csak van egyirányú is, és megduplázza a kétirányú utazási csomópontok között (vagyis az egyik széle A-ból B és egy másikat B-A).

Példaként képzeljünk el három vasútállomásokon elhelyezett, egyenlő oldalú háromszög felfelé. Van még egy további három állomás minden félúton őket. Élek csatlakozzon valamennyi szomszédos állomások együtt, az utolsó rajz lesz fordított háromszög benn a nagyobb háromszöget.

Címke csomópontok kezdve bal alsó, majd balról jobbra, és fel, mint A, B, C, D, E, F (F a tetején).

Tegyük fel, a széleket lehet áthaladni mindkét irányban. Minden vég egy költsége 1 km.

Ok, így szeretnénk útvonalat a bal alsó sarkában egy a felső állomás F. Sok lehetséges útvonalakat, beleértve azokat is, hogy a kettős vissza magukat, pl ABCEBDEF.

Van egy rutin mondjuk NextNode, hogy elfogad egy node, és egy cost, és kéri magát minden egyes csomóponthoz képes utazni.

Nyilvánvaló, ha hagyjuk a rutin távon ez előbb-utóbb felfedezni útvonalakat, beleértve azokat, amelyek potenciálisan végtelen hosszúságú (pl ABABABAB stb.) Mi megállítani ez ne történjen ellenőrzésével szemben cost. Amikor elmegyünk egy csomópontot, amely még nem járt korábban, akkor az mind a költségek, és a csomópont jöttünk ellen csomópontot. Ha egy csomópont már felkeresett, mielőtt megpróbálkozunk a meglévő költség és ha mi olcsóbb, akkor frissítjük a csomópont és folytatni (rekurzív). Ha mi vagyunk a drágább, akkor hagyja ki a csomópontot. Ha minden csomópont kimarad, akkor kilépünk a rutin.

Ha elérünk a cél csomópont akkor lépjen ki a rutin is.

Ily módon minden jövedelmező útvonalak ellenőrzése, de alapvetően csak azokat a legkisebb költséggel. Végére a folyamat minden egyes csomópont lesz a legkisebb költség a szerzés a csomópont, beleértve a cél csomópontot.

Ahhoz, hogy az útvonal dolgozunk visszafelé célunkat csomópontot. Mivel mi tároljuk a csomópont jöttünk mellett a költség, akkor csak hop hátra kiépítése az útvonal. Példánkban mi lenne a végén valami hasonló:

Csomópont A - (teljes) költsége 0 - csomópontból Nincs
B csomópont - Költség 1 - csomópontból A
C csomópont - Költség 2 - tól B csomópont
a D csomópontot - Költség 1 - csomópontból A
Node E - Költség 2 - csomópontból D / költség 2 - tól B csomópont (ez kivétel, mivel egyenlő költség)
Node F - költség 2 - csomópontból D

Így a legrövidebb útvonal ADF.

Válaszolt 26/09/2008 15:05
a forrás felhasználó

szavazat
2

Én még nem talál egy jó tutorial routing de van sok olyan kódot olvasni:

Vannak GPL routing használó alkalmazások Openstreetmap adat, pl Gosmore amely működik Windows (+ mobil) és a Linux. Számos érdekes [alkalmazások ugyanazokat az adatokat, de gosmore néhány hűvös használ pl interfész honlapok .

A legnagyobb probléma a routing rossz adatok, és soha nem lehet elég jó adatokat. Tehát ha azt szeretnénk, hogy próbálja tartani a vizsgálat nagyon helyi így ellenőrzik az adatokat, annál jobb.

Válaszolt 17/09/2008 09:34
a forrás felhasználó

szavazat
2

Ahelyett, hogy a tanulás API-k egyes térkép szolgáltató (mint GMaps, Ymaps api) A jó, hogy megtanulják Mapstraction

„Mapstraction egy könyvtár, amely közös API különböző javascript térképészeti API”

Azt javasoljuk, hogy menjen az URL és tanulni egy általános API-t. Van jó adag útmutató Tos is.

Válaszolt 06/08/2008 14:35
a forrás felhasználó

szavazat
1

Az én munkatapasztalat ezen a területen, az A * ez a munka nagyon jól. Ez (lásd fent) gyorsabb, mint a Dijkstra-algoritmus, de még mindig elég egyszerű egy szokásosan hozzáértő programozó végrehajtására és megérteni.

Épület a útvonalhálózat a legnehezebb része, de lehet bontani egy sor egyszerű lépésből áll: kap minden az utakon; A legújabb pontot a sorrendben; hogy a csoport azonos pontok különböző utak kereszteződések (csomópontok); add ívek mindkét irányban, ahol a csomópontok kapcsolódni (vagy csupán az egyik irányban egy egyirányú út).

Az A * algoritmus maga jól dokumentált a Wikipedia . A legfontosabb hely, hogy optimalizálja a válogatás a legjobb csomópontot a nyitott listát, amelyre szüksége van, egy nagy teljesítményű prioritásos sor. Ha a C ++ segítségével az STL priority_queue adapter.

Testreszabása az algoritmus útvonalon át a különböző részein a hálózat (pl gyalogos, autós, tömegközlekedési, stb) a javára sebesség, távolság vagy egyéb szempontok meglehetősen egyszerű. Ugye, hogy írásban szűrők, hogy mely útszakaszok állnak rendelkezésre, amikor az épület a hálózat, és amely súlyt mindegyik.

Válaszolt 15/07/2012 22:13
a forrás felhasználó

szavazat
1

Tovább gondolat jut az eszembe kapcsolatos költségek az egyes bejárás, de növelné az időt és a feldolgozási teljesítmény kiszámításához szükséges.

Példa: 3 módon tudok venni (ahol élek), hogy menjen az A pont a B szerint a GoogleMaps. Garmin egységet kínál mindegyik 3 utak a Quickestútvonalszámításból. Áthaladás után minden ilyen utak sokszor és átlagoló (nyilván nem lesz hiba függően a napszaktól, koffein mennyiségét, stb), úgy érzem, az algoritmusok is figyelembe véve a több kanyarban az út nagyfokú pontosságot , pl egyenes út 1 mérföld lesz gyorsabb, mint 1 mérföld út éles kanyarok benne . Nem gyakorlati javaslatot, de minden bizonnyal az egyik tudom használni, hogy javítsa az eredmény meg a napi ingázást.

Válaszolt 18/09/2011 22:34
a forrás felhasználó

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