+- Elektroonikafoorum.com (https://elektroonikafoorum.com)
+-- Foorum: Arutelud (https://elektroonikafoorum.com/forum-3.html)
+--- Foorum: Programmeerimine (https://elektroonikafoorum.com/forum-5.html)
+--- Teema: GPSi jadast tänavanime tuletamine (/thread-275.html)
GPSi jadast tänavanime tuletamine - felch - 22-03-2011
Mul on vaja GPSi koordinaatidest tuletada lähima tänava nimi. Loomulikult peab kasutama veel mingit faili, kus nimed ja koordinaadid olemas on. Tekib küsimus, mis algoritmiga seda ülesannet tavaliselt lahendatakse? Rakendus peaks jooksma PIC protsessoril (sest seda tunnen veidi). Igasugu pisikesed navigaatorid ei sisalda ka (vist) võimsaid Pentiume, seega peaks olema võimalik leida tulemus mõistliku aja vältel ka lihtsama prosega.
Mida soovitate, miliseid kaardifaile võiks kasutada?
Ma võin kaardi info eelnevalt PC peal omale mugavamaks teisendada.
RE: GPSi jadast tänavanime tuletamine - andrei - 22-03-2011
Hulgast sirgjoontest antud asukohale l2hima leidmine on keskkooli matemaatika ja mitte v2ga keeruline. Kahjuks ilmselt k6ikidele t2navatele Sa seda reaalajas teha ei j6ua.
Sirgjoonte hulga v2hendamiseks kasutatakse klassikalist kahendotsingupuud, veidi t2iendatuna.
Sirgjoonte otspunktide koordinaatidest koostad 4-kordse kahendotsingupuu (tasemel 0 otsing x1 j2rgi, tasemel 1 otsing y1 j2rgi, ... tasemel 3 otsing y2 j2rgi ja seej2rel kordub). Sellises puus on kahendotsinguga v6imalik leida jooksva asukoha j2rgi leida t2navad, mille otspunktidest moodustatud ruudus on jooksev asukoht.
Kirjutasin v2ga lyhidalt, et ei j22ks mulje, et see on liiga keeruline
RE: GPSi jadast tänavanime tuletamine - andrei - 23-03-2011
Sellised otsingud kuuluvad nn. arvutusliku geomeetria alla. Hea raamat on näiteks de Berg, Cheong, van Kreveld, Overmars:
Computational Geometry: Algorithms and Applications ja sealt peatükk "Orthogonal Range Searching".
P.S. TTÜ sisevõrgust peaks see raamat olema Springeri võrgulehelt loetav.