Nemáte někdo algoritmus na redukci počtu bodů v trase? Tj když posloupnost zlomových bodů tvoří (skoro) přímku, tak aby to nadbytečné body zredukovalo. Tušim že podobnou funkci má třeba Mapsource, ale já bych potřeboval přímo nějaký algoritmus.
edit: upřesnění předmětu tématu
Mapsource to neumí. Tedy ne automaticky, jen ručně, po jednom bodu. Zpočátku jsem to občas dělal, ale teď spíš odstraňuji jen úlety, kdy GPS změřila evidentní nesmysly.
Aby se to nezvrhlo v diskuzi o Mapsource nebo jiném sw. Pište jen pokud někdo nějaký rozumný algoritmus znáte. Děkuji za spolupráci.
Ja mam pocit, ze jsem to kdysi v MapSource automaticky delal. Juknu na to a kdyz tak sem napisu, pokud na to zase prijdu.
Redukoval jsem body timto stylem, kdyz jsem chtel zmensit velikost tracklogu. Ale dnes uz mne velikost tracklogu netrapi, takze jsem to dlouho nepotreboval resit.
Prosím neřešte tu vlastnosti programů, na to si založte vlastní téma (Pravidla - Bod 7). Otázka se týkala znalosti příslušného algoritmu.
Děkuji.
No, to zní tak jednoduše, že by to mělo jít napsat po chvilce přemýšlení. Pokud totiž vzdálenost mezi body nepřesáhne desítky kilometrů, tak se může zanedbat, že je to v nějaké projekci, a můžeme se tvářit, že data jsou v rovině. Potom už jen stačí vymyslet kritéria, podle kterých se mají body vyhazovat. Napadají mne dvě kritéria:
a) blízkost (když stojim na místě a gpska loguje každou sekundu…).
b*) úhel (když je to skoro rovně, tak tam ten bod nemusí být).
Tato kritéria lze eventuelně nějak skombinovat.
Teda pokud se nechce aby trasa odpovídala i časově. To se pak pohybujeme ve třírozměrném (nebo čtyřrozmšrném, pokud máme i výšku) prostoru, ve kterém ale tato dvě kritéria stále dávají smysl (když zahrnují i časovou souřadnici).
Algoritmus, resp. prográmek se můžu pokusit napsat v nějakém skriptovacím jazyce.
- bez hvězdičky to udělalo smajlík !!! (to není moc dobré)
Jednoduše to zní, ale nějak nemám čas ani energii vymýšlet už vymyšlené.
Na mapě postavené na amapy api jsem zkoušel využít routing z google maps api. Jenže když google maps api nekreslí do přímo do vlastní mapy, ale nechám si jen poslat lomenou čáru, tak ta má třeba několik tisíc zlomových bodů a to je problém bez redukce zobrazit.
Je to jen takový experiment.
Dobře, co třeba tohle: aproximace cesty podle zadané přesnosti.
Parametr: přesnost = r
Výstup: redukovaná cesta, která se neodchýlí o více než r.
Vezmu první bod. Ten přijmu. Pomocnou výseč nastavím na plných 360°. Pomocnou vzdálenost nastavím na 0.
Cyklus:
Vezmu další bod:
-
Pokud neleží v pomocné výseči, přijmu předchozí bod.
-
Pokud je blíž než pomocná vzdálenost - r od poslednímho přijatého bodu,
přijmu předchozí bod. -
Pokud je blíž než r od posledního přijatého bodu, ignoruji tento bod.
(to musím, abych dále jako vstup arccos() měl číslo menší než 1) -
Pokud nenastal ani jeden z předchozích případů, zjistím výseč přesnosti
definovanou tímto novým bodem a udělám průnik s pomocnou výsečí.
Pokud je zkoumaný bod dál než pomocná vzdálenost od posl. přijatého, tak pomocnou vzdálenost zvětším na tuto vzdálenost.Výseč přesnosti:
alfa = směr od posledního přijatého bodu k tomuto bodu
d = vzdálenost
beta=arccos(r/d)
výseč: alfa-beta až alfa + beta
Je to jen nápad, výhoda je, že bere body po jednom, a projde je jen jednou, t.j. složitost je lineární v počtu bodů. Nevýhoda je, že nedává žádnou garanci na počet bodů výsledku.
Pořád platí nabídka že to v něčem napíšu (PHP, Javascript, perl…).
Kdysi jsem si na to napsal aplikaci. Pracuje nad .plt z OziExploreru a obecně funguje tak, že pokud bod leží na přímé spojnici mezi sousedními body s maximální odchylkou N metrů, tak se zahodí. Ač je to jednoduché, funguje to docela spolehlivě a vyhodí to překvapivě mnoho bodů. Použil jsem to na konverzi OziExplorerových tracků do mapy tak, aby ty křivky neměly nekonečně mnoho uzlů.
Mohu zaslat.
Nevím jak přesně vypadá algoritmus pana Hroudy, ale pokud vezme tři posobě jdoucí body a vyhodí prostřední pokud je od spojnice blíž než N metrů, tak na cestě která má body po méně než N metrech nejspíše vyhodí všechny body kromě prvního a posledního, i přesto, že body uprostřed leží daleko od spojnice prvního a posledního. A to proto, že 2. leží dost blízko 3., tedy i blízko spojnice 1. a 3.. Po jeho vyhození leží (bývalý) 3. dost blízko (bývalého) 4. a tak dál.
Nee. Pokud jdeš po rovné cestě, tak skutečně vyhází všechny mezi startem a cílem. Pokud ale zatáčíš, tak zredukuje počet bodů na klíčové uzly. Bere se vždy odchylka bodu od přímé spojnice mezi posledním ponechaným bodem a bodem následujícím za tím, co se právě zkoumá.
Furt tomu nerozumím. Dejme tomu že mám na vstupu body A B C D E F, u každého vnitřního bodu zatočím o 45 stupňú vlevo a vzdálenost mezi sousedními je 9. Přesnost nastavím na 10. Je jasné, že od spojnice A a F jsou C a D daleko (konkrétně 9+9/1,4142 = cca 15)
Přijmu bod A.
Zkoumám B: Bod C je od spojnice AB méně než deset (cca 6), přeskočím.
Zkoumám C: Bod D je od spojnice AC méně než deset (cca 8), přeskočím.
Zkoumám D: Bod E je od AD méně než deset (přesně 9), přeskočím.
Zkoumám E: Bod F je od AE méně než deset (cca 8), přeskočím (ale C je od AE cca 10, a od AF cca 15!).
Zbylo mi AF.
Leda že by jste to myslel tak, že kontrolujete VŠECHNY body (i již vyhozené) mezi posledním přijatým a právě zkoumaným bodem na vzdálenost od spojnice těchto dvou bodů. A přijmete poslední zkoumaný který vyhovuje. To pak má kvadratickou složitost (tedy udělá konstanta*(počet bodů)^2 operací). Mé řešení má lineární složitost (udělá (větší konstanta)*(počet bodů)) operací, to znamená, že by měl být můj algoritmus rychlejší pro cesty s mnoha body.
Teda ebik, ty seš docela bedna!
Ja bych prijal A
Pak bych sel na C a zkontroloval vzdalenost B od AC
Pak na D a zkontroloval B a C od AD
Pak AE, AF atd.
Pokracoval bych tak dlouho, dokud by nejaky vnitrni bod nebyl pres limitni odchylku (napr D od AF)
Vypustil bych vnitrni body (v priklade tedy B a C), spojil AD a zacal od D znovu principem jako by to bylo A
To me teda ted napadlo - neco mi rika, ze bych se mel ridit spis interpolaci nez extrapolaci.
Ted koukam, ze to vlastne napsal uz Hrouda. Sorac.
No, právě, že nenapsal.
Kdyby to napsal, tak to pochopim hned. Ono to totiž je todle:
Pan Hrouda psal vždy jen o kontrole jednoho bodu, a ne všech mezi. Respektive jsem to tak pochopil v kontextu mých předchozích příspěvků.
No víš, já studuju a bádám v oboru teoretická informatika. Takže takový věci prostě vědět musim.
OK, jasne, ze to tam mas. Ja se spis soustredil na ten tvuj postup bod po bodu a ten dovetek jsem jen prelitnul, bo sem nechtel, aby mi utekla myslenka. Snad je tedy zaklad principu na svete. Gdo se na to vlastne ptal ;-)? H.
Počítat odchylku bodu od spojnice sousednich bodu je blbost, protoze nebudete brat v uvahu urazenou vzdalenost. Kdyztak pocitejte uhly, a vyhazujte body ktere jsou prilis blizko primemu uhlu (lze pouzit skalarni soucin, normovany soucinem vektoru- da to cos alfa). Dalsi moznost je pocitat plochu trojuhelniku, a kdyz je plocha trojuhelniku prilis mala, tak stredni vrchol vyhodit (lze pouzit absolutni hodnotu vektoroveho soucinu).
To není pravda. Zadání (jestli jsem ho pochopil správně) ve skutečnosti zní tak, že google dodá cestu s obrovským počtem bodů. A my jí chceme aproximovat tak, aby na mapě vypadala dobře. Takže dává smysl proložit tu cestu čárou co se na té mapě odchýlí od původní "husté" čáry na určitý počet metrů (zvolený třeba podle zoomu).
Když vyhodím bod, na kterém se odchýlím o stupeň od předchozího směru, a náhodou bude na dlouhé čáře, tak v mapě ta čára od toho bodu uhne o hodně. Myslím si, že naopak chceme aproximovat původní čáru s určitou přesností (v metrech), nehledě na to jak dlouhé jsou úseky mezi body.