DidaWiki

Questa pagina è in sola lettura. Puoi visualizzare il sorgente, ma non puoi modificarlo. Contatta l'amministratore se pensi che ci sia un errore.
====== 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 un ordine di visita delle piazze in modo che la distanza totale **percorsa a piedi** sia breve, rispettando i sensi unici delle strade percorse: la distanza tra due piazze deve essere calcolata utilizzando la mappa di Pisa indicata sopra. Il programma prende in ingresso tale mappa e fornisce in uscita, oltre alla distanza totale percorsa, la sequenza dei nomi delle corrispondenti vie (chiaramente in ordine di percorrenza). 

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