Il progetto utilizza le mappe stradali disponibili sul sito Open Street Map (OMS) e richiede di rappresentare una mappa come un grafo orientato. In particolare vengono fornite una mappa stradale di Pisa e le seguenti dieci piazze in ordine alfabetico:
Il progetto richiede di scrivere un programma per trovare la distanza in linea d'aria tra tutte le coppie delle suddette piazze: la distanza tra due piazze deve essere calcolata utilizzando la mappa di Pisa indicata sopra e può essere approssimata (entro limiti ragionevoli) perché presa in linea d'aria.
Per facilitare l’accesso ai dati codificati nella mappa, sono disponibili delle API (application program interface) scritte in linguaggio C da Luca Versari. In particolare, il file parse_osm.h
contiene la descrizione di una mappa. Una mappa è costituita da
I tag usati per i nodi e le way nella mappa sono piuttosto numerosi, e sono raccolti qui. Il loro significato è descritto in http://wiki.openstreetmap.org/wiki/Tags.
Il programma test.c
mostra un esempio d’uso. Per creare una rappresentazione interna della mappa con le API, a partire dal file pisa.osm
fornito sopra, il programma utilizza la funzione osm_parse
che restituisce una mappa struct
come quella definita in parse_osm.h
. Quindi il programma itera su tutti i nodi presenti nella mappa e, per ogni nodo, ne stampa l’ID, le coordinate e i tag.
#include "parse_osm.h" int main() { FILE *fd = fopen("pisa.osm", "r"); osm_map_t* map = osm_parse(fd); unsigned i; for (i=0; i<dyn_size(map->nodes); i++) { osm_node_t* node = dyn_get(map->nodes, i); printf("%lu (%lf, %lf)", node->id, node->lat, node->lon); unsigned j=0; for (j=0; j<dyn_size(node->tags); j++) { osm_tag_t* tag = dyn_get(node->tags, j); printf(" %s='%s'", tag->key, tag->value); } printf("\n"); } osm_free_map(map); return 0; }
Occorre compilare con gcc dynarray.c dynstring.c parse_osm.c xml.c test.c -o test -O2 -Wall
e lanciare ./test | more
oppure test.exe | more
da terminale (a seconda del sistema operativo).