DidaWiki

Questa pagina è in sola lettura. Puoi visualizzare il sorgente, ma non puoi modificarlo. Contatta l'amministratore se pensi che ci sia un errore.
====== Mini-progetto di ASD 2016/2017 ======

Il progetto utilizza le mappe stradali disponibili sul sito [[http://www.openstreetmap.org|Open Street Map]] (OMS) e richiede di rappresentare una mappa come un grafo orientato. In particolare vengono fornite una {{ :matematica:asd:asd_16:pisa.osm.zip | 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 {{ :matematica:asd:asd_16:asd1617-project.zip |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 {{ :matematica:asd:asd_16:map_tags.zip |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.

<code>
#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;
}
</code>

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