Differenze

Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.

--- matematica:asd:asd_16:progetto_16 [22/02/2017 alle 11:09 (8 anni fa)] – creata Roberto Grossi
+++ matematica:asd:asd_16:progetto_16 [03/07/2017 alle 14:11 (8 anni fa)] (versione attuale) – Roberto Grossi
@@ Linea 1: / Linea 1: @@
-TBA
+====== 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).