Téma t4: Komprese mapových dat (20 b)

Zadáno v čísle 22.2.

Zadání

Aplikace pro navigaci má dnes skoro každý na mobilu. Není problém mít v mobilu půlku Evropy a mít tak mapy všude po ruce. Jak ale taková rozsáhlá data ukládat, aby nebyla příliš velká a dala se snadno používat? Cílem tohoto tématu je zkusit vymyslet a realizovat algoritmy na efektivní ukládání mapových dat. Pro naše účely se budou mapy skládat jen z jednoduchých objektů –bodů, lomených čar a ploch. Každý bod má souřadnice, čáry a plochy jsou popsány souřadnicemi bodů, kterými procházejí, a plochy jsou navíc uzavřené. Pro ty, kteří chtějí své nápady i prakticky realizovat, jsme připravili testovací data, na kterých si mohou efektivitu svých algoritmů vyzkoušet.

Zkuste vymyslet (a případně realizovat) způsob, jak uložit mapová data, aby zabírala co nejméně prostoru a splňovala některou z následujících podmínek:

žádné další podmínky nejsou

byla lokálně dekomprimovatelná – pokud chci znát mapu v okolí daných souřadnic, stačí mi rozbalit jen vhodnou část dat a  nemusím je nejprve rozbalit všechna

byla editovatelná – pokud chci přidat nebo změnit bod, čáru či plochu, nemusím nejprve vše rozbalit a pak opět zabalit

byla postupně komprimovatelná – objekty dostávám postupně a všechny se mi naráz nevejdou do paměti, proto je chci průběžně komprimovat a zapisovat na disk. Pořadí objektů si mohu předepsat.

Jak se budou vaše algoritmy chovat, pokud dostaneme mapu hustě osídlené oblasti s množstvím objektů na malé ploše? Budou stejně efektivní i pro řídké mapy venkovských oblastí?

Pro ty, které baví programovat, jsme připravili i praktická data z města i krajiny. Na odkazu http://mam.mff.cuni.cz/media/tema/22/tema4/brno.txt si můžete stáhnout mapu středu Brna, na odkazu http://mam.mff.cuni.cz/media/tema/22/tema4/jestrebi.txt si můžete stáhnout mapu vesnických oblastí okolo Jestřebí. Soubor je textový v následujícím formátu:

b c p
sy1 sx1
sy2 sx2
...
syb sxb
c1l sc11y sc11x sc12y sc12y ... sc1ly sc1lx
...
ccl scc1y scc1x scc2y scc2y ... sccly scclx
p1l sp11y sp11x sp12y sp12y ... sp1ly sp1lx sp11y sp11x
...
ppl spp1y spp1x spp2y spp2y ... spply spplx spp1y spp1x

Na prvním řádku je uveden počet bodů, cest a ploch. Po nich následují body, cesty a plochy, vždy jeden objekt na jeden řádek. Body obsahují nejprve zeměpisnou šířku a pak zeměpisnou délku ve stupních. Cesty a plochy jsou popsané hraničními body a obsahují nejprve počet bodů na cestě/ploše a pak souřadnice jednotlivých bodů na ní. U ploch je poslední bod shodný s prvním.

Pokud budete váš algoritmus implementovat, důkladně ho vysvětlete a okomentujte a napište současně program pro kompresi i dekompresi dat, ať ho můžeme vyzkoušet na různých datech.