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:

• Piazza Chiara Gambacorti
• Piazza dei Cavalieri
• Piazza dell'Arcivescovado
• Piazza Domenico Guerrazzi
• Piazza Francesco Carrara
• Piazza San Francesco
• Piazza San Martino
• Piazza San Paolo a Ripa d'Arno
• Piazza San Silvestro
• Piazza Vittorio Emanuele II

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

• nodi: sono punti nel globo terrestre di cui si conoscono longitudine e latidudine. Inoltre, le caratteristiche del nodo sono memorizzate in un array di tag (vedi anche http://wiki.openstreetmap.org/wiki/Node)
• way: da non confondere con le strade, descrivono una qualsiasi linea spezzata in più punti: strada, muro, contorno di un parco, ecc. Si conosce la sequenza di nodi in essa contenuti e un array di tag (vedi anche http://wiki.openstreetmap.org/wiki/Way).
• relazioni: rappresentano delle restrizioni su strade, ecc., ma le ignoriamo in questo progetto.

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).