Brzi algoritam za generaciju kontinuiranih kartograma
Kartogrami su poznata tehnika za prikaz geografski vezanih statističkih informacija kao što su populacijski, demografijski i epidemiologijski podaci. Cilj kartograma je da se deformira mapa tako da se promjene veličine regije u odnosu na neki statistički parametar, ali tako da karta ostane prepoznatljiva. Pokazat će se kako, u općem slučaju, nisu rješive čak i jednostavne varijante generacije kartograma. Heuristika je potrebna za rješavanje jer su izvedive varijante problema NP rješive. Da bi kartogram bio prepoznatljiv, važno je da se očuva globalni oblik ili da se obilježi ulazna mapa. Radi toga ciljna funkcija za iscrtavanje kartograma uključuje očuvanje globalnog i lokalnog oblika. Za mjerenje stupnja očuvanja oblika predlaže se funkcija za sličnost oblika koja je bazirana na razlici između funkcija zakrivljenosti poligona. Brzina izvođenja u ovoj aplikaciji nije toliko važna jer je dovoljno da se algoritam za izračun kartograma obavi jednom nakon unošenja novih podatkovnih točaka, ali se ovom metodom postižu veće brzine izvođenja nego što je to kod nekih drugih tehnika. Ova metoda se obavlja uz pomoć učinkovitog iterativnog algoritma linije uzorkovanja (engl. Scanline Algorithm) za pomicanje vrhova uz očuvanje lokalnog i globalnog oblika. Linije uzorkovanja se mogu generirati automatski ili se mogu unositi interaktivno kako bi se bolje vodila optimizacija procesa. Algoritam se primjenjuje na nekoliko primjera različitih podatkovnih točaka.
Kartogrami
Kartografi i geografi su morali koristiti kartograme još mnogo ranije nego što su računala bila dostupna za prikazivanje. Osnovna ideja za kartograme je da se deformira mapa tako da se promijene veličine regija po nekom geografski određenom parametru. Zbog toga što su kartogrami komplicirani za izradu rukom, izučavanje programa koji bi ih crtali postaje interesantno.
Kartogram se može gledati kao generalizacija običnih geografskih karti. Kod takvih karti se vektor statističkih parametara namjeravane veličine regija kartograma zadaje tako da je on proporcionalan s površinama tih regija. U ovom slučaju vektor statističkih parametara se zadaje brojem podatkovnih točaka koje ta regija sadrži jer su one često koncentrirane u gusto naseljenim područjima, a malo ih se širi kroz rijetko naseljena područja. Tako kartogrami zapravo prikazuju površine regija u relaciji s nekim dodatnim parametrom, kao što je to naseljenost ili broj podatkovnih točaka. Uzorci se tada mogu prikazati u proporciji s tim parametrom umjesto čiste veličine područja. Na slici 1 je prikazan kartogram baziran na populaciji koji prikazuje da se mogu dobiti različiti utisci pogledom na kartogram u usporedbi s originalnim geografskim kartama.
Slika 1: Kartogram osnovan na podacima o naseljenosti.
Na lijevoj strani je originalna karta, a na desnoj kartogram.
Da bi kartogram bio efektivan, čovjek mora moći brzo razumjeti prikazane podatke i povezati ih s originalnim geografskim modelom. Prepoznatljivost ovisi o osnovnim svojstvima očuvanja kao što su to oblik, orijentacija i udaljenost. Ovo je, naime, teško postići u općem slučaju jer je nemoguće ostvariti idealno rješenje uz očuvanje topologije. Većina dostupnih algoritama je veliki potrošač vremena zbog toga što je generacija kontinuiranih kartograma uz simultanu optimizaciju ovih ciljeva dosta komplicirana.
Krajnji cilj je da se kartogramom ostvare veličine područja proporcionalne s brojem podatkovnih točaka u njima. Razlog tome je da se područja s gustom raspodjelom podatkovnih točaka prošire kako bi svaka pojedinačna podatkovna točka bila vidljiva bez promjene mjerila mape. SCADA sustavi zahtijevaju mogućnost da u svakom trenutku bude prikazana mapa u cijelosti kako bi promjene bile vidljive na ekranu bez obzira na kojem području se dogodile.