/[zanavi_public1]/navit/navit/maptool/ch.c
ZANavi

Contents of /navit/navit/maptool/ch.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 31 - (hide annotations) (download)
Mon Feb 4 17:41:59 2013 UTC (7 years, 2 months ago) by zoff99
File MIME type: text/plain
File size: 13860 byte(s)
new map version, lots of fixes and experimental new features
1 zoff99 8 /**
2     * Navit, a modular navigation system.
3     * Copyright (C) 2005-2011 Navit Team
4     *
5     * This program is free software; you can redistribute it and/or
6     * modify it under the terms of the GNU General Public License
7     * version 2 as published by the Free Software Foundation.
8     *
9     * This program is distributed in the hope that it will be useful,
10     * but WITHOUT ANY WARRANTY; without even the implied warranty of
11     * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12     * GNU General Public License for more details.
13     *
14     * You should have received a copy of the GNU General Public License
15     * along with this program; if not, write to the
16     * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17     * Boston, MA 02110-1301, USA.
18     */
19    
20     #include <math.h>
21     #include <stdlib.h>
22     #include "maptool.h"
23     #include "coord.h"
24     #include "file.h"
25     #include "debug.h"
26    
27     #if GLIB_MAJOR_VERSION == 2 && GLIB_MINOR_VERSION < 10
28     #define g_slice_alloc0 g_malloc0
29     #define g_slice_new(x) g_new(x,1)
30     #define g_slice_new0(x) g_new0(x,1)
31     #define g_slice_free(x,y) g_free(y)
32     #define g_slice_free1(x,y) g_free(y)
33     #endif
34    
35 zoff99 31 struct ch_edge
36     {
37 zoff99 8 int flags;
38     int weight;
39 zoff99 31 struct item_id target, middle;
40 zoff99 8 };
41    
42 zoff99 31 struct node
43     {
44 zoff99 8 int first_edge;
45     int dummy;
46 zoff99 31 }*nodes;
47 zoff99 8 int node_count;
48    
49 zoff99 31 struct edge
50     {
51     unsigned target :26;
52     unsigned scedge1 :6;
53     unsigned weight :28;
54     unsigned type :2;
55     unsigned flags :2;
56 zoff99 8 unsigned int edge_count;
57 zoff99 31 unsigned scedge2 :6;
58     unsigned scmiddle :26;
59     }*edges;
60 zoff99 8
61     int edge_count;
62    
63 zoff99 31 struct newnode
64     {
65 zoff99 8 int newnode;
66 zoff99 31 }*newnodes;
67 zoff99 8
68     int newnode_count;
69    
70     GHashTable *newnode_hash;
71    
72 zoff99 31 struct edge_hash_item
73     {
74     int first, last;
75 zoff99 8 };
76    
77     GHashTable *edge_hash;
78    
79 zoff99 31 struct file *sgr, *ddsg_node_index;
80 zoff99 8
81     struct coord *node_index;
82    
83     GHashTable *sgr_nodes_hash;
84    
85 zoff99 31 static int ch_levels = 14;
86 zoff99 8
87 zoff99 31 static int road_speed(enum item_type type)
88 zoff99 8 {
89 zoff99 31 switch (type)
90     {
91     case type_street_0:
92     case type_street_1_city:
93     case type_living_street:
94     case type_street_service:
95     case type_track_gravelled:
96     case type_track_unpaved:
97     return 10;
98     case type_street_2_city:
99     case type_track_paved:
100     return 30;
101     case type_street_3_city:
102     return 40;
103     case type_street_4_city:
104     return 50;
105     case type_highway_city:
106     return 80;
107     case type_street_1_land:
108     return 60;
109     case type_street_2_land:
110     return 65;
111     case type_street_3_land:
112     return 70;
113     case type_street_4_land:
114     return 80;
115     case type_street_n_lanes:
116     return 120;
117     case type_highway_land:
118     return 120;
119     case type_ramp:
120     return 40;
121     case type_roundabout:
122     return 10;
123     case type_ferry:
124     return 40;
125     default:
126     return 0;
127 zoff99 8 }
128     }
129    
130 zoff99 31 static void coord_slice_free(void *data)
131 zoff99 8 {
132 zoff99 31 g_slice_free(struct coord, data);
133 zoff99 8 }
134    
135     static GHashTable *
136     coord_hash_new(void)
137     {
138 zoff99 31 return g_hash_table_new_full(coord_hash, coord_equal, coord_slice_free, NULL);
139 zoff99 8 }
140    
141 zoff99 31 static void item_id_slice_free(void *data)
142 zoff99 8 {
143 zoff99 31 g_slice_free(struct item_id, data);
144 zoff99 8 }
145    
146     #define sq(x) ((double)(x)*(x))
147    
148 zoff99 31 static void add_node_to_hash(FILE *idx, GHashTable *hash, struct coord *c, int *nodes)
149 zoff99 8 {
150 zoff99 31 if (!g_hash_table_lookup(hash, c))
151     {
152 zoff99 8 struct coord *ct=g_slice_new(struct coord);
153 zoff99 31 *ct = *c;
154 zoff99 8 fwrite(c, sizeof(*c), 1, idx);
155     (*nodes)++;
156 zoff99 31 g_hash_table_insert(hash, ct, (void *) (*nodes));
157 zoff99 8 }
158    
159     }
160    
161 zoff99 31 static void edge_hash_slice_free(void *data)
162 zoff99 8 {
163 zoff99 31 g_slice_free(struct edge_hash_item, data);
164 zoff99 8 }
165    
166 zoff99 31 static guint edge_hash_hash(gconstpointer key)
167 zoff99 8 {
168 zoff99 31 const struct edge_hash_item *itm = key;
169     return itm->first * 2654435761UL + itm->last;
170 zoff99 8 }
171    
172 zoff99 31 static gboolean edge_hash_equal(gconstpointer a, gconstpointer b)
173 zoff99 8 {
174 zoff99 31 const struct edge_hash_item *itm_a = a;
175     const struct edge_hash_item *itm_b = b;
176 zoff99 8 return (itm_a->first == itm_b->first && itm_a->last == itm_b->last);
177     }
178    
179 zoff99 31 static void ch_generate_ddsg(FILE *in, FILE *ref, FILE *idx, FILE *ddsg)
180 zoff99 8 {
181 zoff99 31 GHashTable *hash = coord_hash_new();
182 zoff99 8 struct item_bin *ib;
183 zoff99 31 int nodes = 0, edges = 0;
184 zoff99 8
185 zoff99 31 while ((ib = read_item(in, 0)))
186     {
187     int ccount = ib->clen / 2;
188     struct coord *c = (struct coord *) (ib + 1);
189     if (road_speed(ib->type))
190     {
191 zoff99 8 add_node_to_hash(idx, hash, &c[0], &nodes);
192 zoff99 31 add_node_to_hash(idx, hash, &c[ccount - 1], &nodes);
193 zoff99 8 edges++;
194     }
195     }
196 zoff99 31 edge_hash = g_hash_table_new_full(edge_hash_hash, edge_hash_equal, edge_hash_slice_free, item_id_slice_free);
197 zoff99 8 fseek(in, 0, SEEK_SET);
198 zoff99 31 fprintf(ddsg, "d\n");
199     fprintf(ddsg, "%d %d\n", nodes, edges);
200     while ((ib = read_item(in, 0)))
201     {
202     int i, ccount = ib->clen / 2;
203     struct coord *c = (struct coord *) (ib + 1);
204     int n1, n2, speed = road_speed(ib->type);
205 zoff99 8 struct item_id road_id;
206     double l;
207     fread(&road_id, sizeof(road_id), 1, ref);
208 zoff99 31 if (speed)
209     {
210 zoff99 8 struct edge_hash_item *hi=g_slice_new(struct edge_hash_item);
211     struct item_id *id=g_slice_new(struct item_id);
212 zoff99 31 *id = road_id;
213     dbg_assert((n1 = GPOINTER_TO_INT(g_hash_table_lookup(hash, &c[0]))) != 0);
214     dbg_assert((n2 = GPOINTER_TO_INT(g_hash_table_lookup(hash, &c[ccount - 1]))) != 0);
215     l = 0;
216     for (i = 0; i < ccount - 1; i++)
217     {
218     l += sqrt(sq(c[i+1].x-c[i].x) + sq(c[i+1].y-c[i].y));
219 zoff99 8 }
220 zoff99 31 fprintf(ddsg, "%d %d %d 0\n", n1 - 1, n2 - 1, (int) (l * 36 / speed));
221     hi->first = n1 - 1;
222     hi->last = n2 - 1;
223 zoff99 8 g_hash_table_insert(edge_hash, hi, id);
224     }
225     }
226     g_hash_table_destroy(hash);
227     }
228    
229 zoff99 31 static void ch_generate_sgr(char *suffix)
230 zoff99 8 {
231     #ifndef HAVE_API_WIN32_CE
232     char command[1024];
233 zoff99 31 sprintf(command, "./contraction-hierarchies-20080621/main -s -p -f ddsg_%s.tmp -o hcn_%s.tmp -l hcn_log_%s.tmp -x 190 -y 1 -e 600 -p 1000 -k 1,3.3,2,10,3,10,5", suffix, suffix, suffix);
234     printf("%s\n", command);
235 zoff99 8 system(command);
236 zoff99 31 sprintf(command, "./contraction-hierarchies-20080621/main -c -f ddsg_%s.tmp -h hcn_%s.tmp -k 1,3.3,2,10,3,10,5 -C ch_%s.tmp -O 1 -z sgr_%s.tmp", suffix, suffix, suffix, suffix);
237     printf("%s\n", command);
238 zoff99 8 system(command);
239     #endif
240     }
241    
242 zoff99 31 static void ch_process_node(FILE *out, int node, int resolve)
243 zoff99 8 {
244 zoff99 31 int first_edge_id = nodes[node].first_edge;
245     int last_edge_id = nodes[node + 1].first_edge;
246 zoff99 8 int edge_id;
247     struct ch_edge ch_edge;
248     struct item_bin *item_bin;
249 zoff99 31 struct edge_hash_item fwd, rev;
250 zoff99 8 int oldnode;
251     memset(&ch_edge, 0, sizeof(ch_edge));
252 zoff99 31 item_bin = init_item(type_ch_node, 0);
253     oldnode = GPOINTER_TO_INT(g_hash_table_lookup(newnode_hash, GINT_TO_POINTER(node)));
254 zoff99 8 #if 0
255     dbg(0,"0x%x,0x%x\n",node_index[oldnode].x,node_index[oldnode].y);
256     #endif
257     item_bin_add_coord(item_bin, &node_index[oldnode], 1);
258 zoff99 31 fwd.first = oldnode;
259     rev.last = oldnode;
260     for (edge_id = first_edge_id; edge_id < last_edge_id; edge_id++)
261     {
262     if (resolve)
263     {
264     struct edge *edge = &edges[edge_id];
265     int oldnode = GPOINTER_TO_INT(g_hash_table_lookup(newnode_hash, GINT_TO_POINTER((int) edge->target)));
266 zoff99 8 struct item_id *id;
267 zoff99 31 ch_edge.weight = edge->weight;
268     fwd.last = oldnode;
269     rev.first = oldnode;
270     ch_edge.flags = edge->flags & 3;
271     if (edge->scmiddle == 67108863)
272     {
273     id = g_hash_table_lookup(edge_hash, &fwd);
274     if (!id)
275     {
276     ch_edge.flags |= 8;
277     id = g_hash_table_lookup(edge_hash, &rev);
278 zoff99 8 }
279 zoff99 31 if (id == NULL)
280     {
281     fprintf(stderr, "Shortcut %d Weight %d\n", edge->scmiddle, edge->weight);
282     fprintf(stderr, "Neither %d-%d nor %d-%d exists\n", fwd.first, fwd.last, rev.first, rev.last);
283 zoff99 8 exit(1);
284 zoff99 31 }
285     else
286     {
287     ch_edge.middle = *id;
288 zoff99 8 #if 0
289     dbg(0,"middle street id for is "ITEM_ID_FMT"\n",ITEM_ID_ARGS(*id));
290     #endif
291     }
292 zoff99 31 }
293     else
294     {
295     ch_edge.flags |= 4;
296     id = g_hash_table_lookup(sgr_nodes_hash, GINT_TO_POINTER((int) edge->scmiddle));
297 zoff99 8 dbg_assert(id != NULL);
298 zoff99 31 ch_edge.middle = *id;
299 zoff99 8 #if 0
300     dbg(0,"middle node id for is "ITEM_ID_FMT"\n",ITEM_ID_ARGS(*id));
301     #endif
302     }
303 zoff99 31 id = g_hash_table_lookup(sgr_nodes_hash, GINT_TO_POINTER((int) edge->target));
304 zoff99 8 #if 0
305     dbg(0,"id for %d is "ITEM_ID_FMT"\n",edge->target,ITEM_ID_ARGS(*id));
306     #endif
307 zoff99 31 if (id == NULL)
308     {
309     fprintf(stderr, "Failed to look up target %d\n", edge->target);
310 zoff99 8 }
311 zoff99 31 else
312     {
313     ch_edge.target = *id;
314     }
315 zoff99 8 }
316 zoff99 31 item_bin_add_attr_data(item_bin, attr_ch_edge, &ch_edge, sizeof(ch_edge));
317 zoff99 8 }
318     item_bin_write(item_bin, out);
319     }
320    
321 zoff99 31 static void ch_process_nodes(FILE *out, int pos, int count, int resolve)
322 zoff99 8 {
323     int i;
324 zoff99 31 printf("count %d sum=%d newnode_count=%d\n", count, pos, newnode_count);
325     for (i = 0; i < count; i++)
326     ch_process_node(out, pos + i, resolve);
327 zoff99 8 }
328    
329 zoff99 31 static void ch_process(FILE **files, int depth, int resolve)
330 zoff99 8 {
331 zoff99 31 int count = newnode_count;
332     int pos = 0;
333 zoff99 8
334 zoff99 31 while (depth > 0 && pos < newnode_count)
335     {
336     count = (count + 1) / 2;
337 zoff99 8 ch_process_nodes(files[depth], pos, count, resolve);
338 zoff99 31 pos += count;
339 zoff99 8 depth--;
340     }
341 zoff99 31 ch_process_nodes(files[depth], pos, newnode_count - pos, resolve);
342 zoff99 8 }
343    
344 zoff99 31 static void ch_setup(char *suffix)
345 zoff99 8 {
346     int i;
347 zoff99 31 if (!sgr)
348     {
349     int *data, size, offset = 0;
350     char *filename = tempfile_name(suffix, "sgr");
351     printf("filename=%s\n", filename);
352     sgr = file_create(filename, 0);
353 zoff99 8 g_free(filename);
354     dbg_assert(sgr != NULL);
355     file_mmap(sgr);
356    
357 zoff99 31 size = sizeof(int);
358     data = (int *) file_data_read(sgr, offset, size);
359     node_count = *data;
360     offset += size;
361 zoff99 8
362 zoff99 31 size = node_count * sizeof(struct node);
363     nodes = (struct node *) file_data_read(sgr, offset, size);
364     offset += size;
365 zoff99 8
366 zoff99 31 size = sizeof(int);
367     data = (int *) file_data_read(sgr, offset, size);
368     edge_count = *data;
369     offset += size;
370 zoff99 8
371 zoff99 31 size = edge_count * sizeof(struct edge);
372     edges = (struct edge *) file_data_read(sgr, offset, size);
373     offset += size;
374 zoff99 8
375 zoff99 31 size = sizeof(int);
376     data = (int *) file_data_read(sgr, offset, size);
377     newnode_count = *data;
378     offset += size;
379 zoff99 8
380 zoff99 31 size = edge_count * sizeof(struct newnode);
381     newnodes = (struct newnode *) file_data_read(sgr, offset, size);
382     offset += size;
383 zoff99 8
384 zoff99 31 newnode_hash = g_hash_table_new(NULL, NULL);
385 zoff99 8
386 zoff99 31 for (i = 0; i < newnode_count; i++)
387     {
388 zoff99 8 g_hash_table_insert(newnode_hash, GINT_TO_POINTER(newnodes[i].newnode), GINT_TO_POINTER(i));
389 zoff99 31 }
390 zoff99 8 }
391 zoff99 31 if (!ddsg_node_index)
392     {
393     char *filename = tempfile_name(suffix, "ddsg_coords");
394     ddsg_node_index = file_create(filename, 0);
395 zoff99 8 g_free(filename);
396     dbg_assert(ddsg_node_index != NULL);
397     file_mmap(ddsg_node_index);
398 zoff99 31 node_index = (struct coord *) file_data_read(ddsg_node_index, 0, file_size(ddsg_node_index));
399 zoff99 8 }
400     }
401    
402 zoff99 31 static void ch_create_tempfiles(char *suffix, FILE **files, int count, int mode)
403     {
404 zoff99 8 char name[256];
405     int i;
406    
407 zoff99 31 for (i = 0; i <= count; i++)
408     {
409     sprintf(name, "graph_%d", i);
410     files[i] = tempfile(suffix, name, mode);
411 zoff99 8 }
412     }
413    
414 zoff99 31 static void ch_close_tempfiles(FILE **files, int count)
415 zoff99 8 {
416     int i;
417    
418 zoff99 31 for (i = 0; i <= count; i++)
419     {
420 zoff99 8 fclose(files[i]);
421     }
422     }
423    
424 zoff99 31 static void ch_remove_tempfiles(char *suffix, int count)
425 zoff99 8 {
426     char name[256];
427     int i;
428    
429 zoff99 31 for (i = 0; i <= count; i++)
430     {
431     sprintf(name, "graph_%d", i);
432 zoff99 8 tempfile_unlink(suffix, name);
433     }
434     }
435    
436 zoff99 31 static void ch_copy_to_tiles(char *suffix, int count, struct tile_info *info, FILE *ref)
437 zoff99 8 {
438     char name[256];
439     int i;
440     FILE *f;
441     struct item_bin *item_bin;
442    
443 zoff99 31 for (i = count; i >= 0; i--)
444     {
445     sprintf(name, "graph_%d", i);
446     f = tempfile(suffix, name, 0);
447     while ((item_bin = read_item(f, 0)))
448     {
449 zoff99 8 tile_write_item_minmax(info, item_bin, ref, i, i);
450     }
451     fclose(f);
452     }
453     }
454    
455 zoff99 31 void ch_generate_tiles(char *map_suffix, char *suffix, FILE *tilesdir_out, struct zip_info *zip_info)
456 zoff99 8 {
457     struct tile_info info;
458 zoff99 31 FILE *in, *ref, *ddsg_coords, *ddsg;
459 zoff99 8 FILE **graphfiles;
460 zoff99 31 info.write = 0;
461     info.maxlen = 0;
462     info.suffix = suffix;
463     info.tiles_list = NULL;
464     info.tilesdir_out = tilesdir_out;
465     graphfiles = g_alloca(sizeof(FILE*) * (ch_levels + 1));
466 zoff99 8
467     ch_create_tempfiles(suffix, graphfiles, ch_levels, 1);
468 zoff99 31 in = tempfile(map_suffix, "ways_split", 0);
469     ref = tempfile(map_suffix, "ways_split_ref", 0);
470     ddsg_coords = tempfile(suffix, "ddsg_coords", 1);
471     ddsg = tempfile(suffix, "ddsg", 1);
472 zoff99 8 ch_generate_ddsg(in, ref, ddsg_coords, ddsg);
473     fclose(in);
474     fclose(ref);
475     fclose(ddsg_coords);
476     fclose(ddsg);
477     ch_generate_sgr(suffix);
478     ch_setup(suffix);
479     ch_process(graphfiles, ch_levels, 0);
480     ch_close_tempfiles(graphfiles, ch_levels);
481    
482 zoff99 31 tile_hash = g_hash_table_new(g_str_hash, g_str_equal);
483 zoff99 8 ch_copy_to_tiles(suffix, ch_levels, &info, NULL);
484     merge_tiles(&info);
485    
486     write_tilesdir(&info, zip_info, tilesdir_out);
487     }
488    
489 zoff99 31 void ch_assemble_map(char *map_suffix, char *suffix, struct zip_info *zip_info)
490 zoff99 8 {
491     struct tile_info info;
492     struct tile_head *th;
493 zoff99 31 FILE **graphfiles = g_alloca(sizeof(FILE*) * (ch_levels + 1));
494 zoff99 8 FILE *ref;
495     struct item_id id;
496 zoff99 31 int nodeid = 0;
497 zoff99 8
498 zoff99 31 info.write = 1;
499     info.maxlen = zip_get_maxnamelen(zip_info);
500     info.suffix = suffix;
501     info.tiles_list = NULL;
502     info.tilesdir_out = NULL;
503     ref = tempfile(suffix, "sgr_ref", 1);
504 zoff99 8
505     create_tile_hash();
506    
507 zoff99 31 th = tile_head_root;
508     while (th)
509     {
510     th->zip_data = NULL;
511     th->process = 1;
512     th = th->next;
513     }
514 zoff99 8
515     ch_setup(suffix);
516     ch_copy_to_tiles(suffix, ch_levels, &info, ref);
517     fclose(ref);
518 zoff99 31 ref = tempfile(suffix, "sgr_ref", 0);
519     sgr_nodes_hash = g_hash_table_new_full(NULL, NULL, NULL, item_id_slice_free);
520     while (fread(&id, sizeof(id), 1, ref))
521     {
522 zoff99 8 struct item_id *id2=g_slice_new(struct item_id);
523 zoff99 31 *id2 = id;
524 zoff99 8 #if 0
525     dbg(0,"%d is "ITEM_ID_FMT"\n",nodeid,ITEM_ID_ARGS(*id2));
526     #endif
527     g_hash_table_insert(sgr_nodes_hash, GINT_TO_POINTER(nodeid), id2);
528     nodeid++;
529     }
530 zoff99 31 th = tile_head_root;
531     while (th)
532     {
533     th->zip_data = malloc(th->total_size);
534     th->total_size_used = 0;
535     th = th->next;
536     }
537 zoff99 8 ch_create_tempfiles(suffix, graphfiles, ch_levels, 1);
538     ch_process(graphfiles, ch_levels, 1);
539     ch_close_tempfiles(graphfiles, ch_levels);
540    
541     g_hash_table_destroy(newnode_hash);
542     g_hash_table_destroy(edge_hash);
543     g_hash_table_destroy(sgr_nodes_hash);
544    
545     ch_copy_to_tiles(suffix, ch_levels, &info, NULL);
546     write_tilesdir(&info, zip_info, NULL);
547    
548 zoff99 31 th = tile_head_root;
549     while (th)
550     {
551     if (th->name[0])
552     {
553     if (th->total_size != th->total_size_used)
554     {
555     fprintf(stderr, "Size error '%s': %d vs %d\n", th->name, th->total_size, th->total_size_used);
556 zoff99 8 exit(1);
557     }
558     write_zipmember(zip_info, th->name, zip_get_maxnamelen(zip_info), th->zip_data, th->total_size);
559 zoff99 31 }
560     else
561     {
562 zoff99 8 fwrite(th->zip_data, th->total_size, 1, zip_get_index(zip_info));
563     }
564     g_free(th->zip_data);
565 zoff99 31 th = th->next;
566     }
567 zoff99 8 }

   
Visit the ZANavi Wiki