/[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 - (show annotations) (download)
Mon Feb 4 17:41:59 2013 UTC (11 years, 1 month ago) by zoff99
File MIME type: text/plain
File size: 13860 byte(s)
new map version, lots of fixes and experimental new features
1 /**
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 struct ch_edge
36 {
37 int flags;
38 int weight;
39 struct item_id target, middle;
40 };
41
42 struct node
43 {
44 int first_edge;
45 int dummy;
46 }*nodes;
47 int node_count;
48
49 struct edge
50 {
51 unsigned target :26;
52 unsigned scedge1 :6;
53 unsigned weight :28;
54 unsigned type :2;
55 unsigned flags :2;
56 unsigned int edge_count;
57 unsigned scedge2 :6;
58 unsigned scmiddle :26;
59 }*edges;
60
61 int edge_count;
62
63 struct newnode
64 {
65 int newnode;
66 }*newnodes;
67
68 int newnode_count;
69
70 GHashTable *newnode_hash;
71
72 struct edge_hash_item
73 {
74 int first, last;
75 };
76
77 GHashTable *edge_hash;
78
79 struct file *sgr, *ddsg_node_index;
80
81 struct coord *node_index;
82
83 GHashTable *sgr_nodes_hash;
84
85 static int ch_levels = 14;
86
87 static int road_speed(enum item_type type)
88 {
89 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 }
128 }
129
130 static void coord_slice_free(void *data)
131 {
132 g_slice_free(struct coord, data);
133 }
134
135 static GHashTable *
136 coord_hash_new(void)
137 {
138 return g_hash_table_new_full(coord_hash, coord_equal, coord_slice_free, NULL);
139 }
140
141 static void item_id_slice_free(void *data)
142 {
143 g_slice_free(struct item_id, data);
144 }
145
146 #define sq(x) ((double)(x)*(x))
147
148 static void add_node_to_hash(FILE *idx, GHashTable *hash, struct coord *c, int *nodes)
149 {
150 if (!g_hash_table_lookup(hash, c))
151 {
152 struct coord *ct=g_slice_new(struct coord);
153 *ct = *c;
154 fwrite(c, sizeof(*c), 1, idx);
155 (*nodes)++;
156 g_hash_table_insert(hash, ct, (void *) (*nodes));
157 }
158
159 }
160
161 static void edge_hash_slice_free(void *data)
162 {
163 g_slice_free(struct edge_hash_item, data);
164 }
165
166 static guint edge_hash_hash(gconstpointer key)
167 {
168 const struct edge_hash_item *itm = key;
169 return itm->first * 2654435761UL + itm->last;
170 }
171
172 static gboolean edge_hash_equal(gconstpointer a, gconstpointer b)
173 {
174 const struct edge_hash_item *itm_a = a;
175 const struct edge_hash_item *itm_b = b;
176 return (itm_a->first == itm_b->first && itm_a->last == itm_b->last);
177 }
178
179 static void ch_generate_ddsg(FILE *in, FILE *ref, FILE *idx, FILE *ddsg)
180 {
181 GHashTable *hash = coord_hash_new();
182 struct item_bin *ib;
183 int nodes = 0, edges = 0;
184
185 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 add_node_to_hash(idx, hash, &c[0], &nodes);
192 add_node_to_hash(idx, hash, &c[ccount - 1], &nodes);
193 edges++;
194 }
195 }
196 edge_hash = g_hash_table_new_full(edge_hash_hash, edge_hash_equal, edge_hash_slice_free, item_id_slice_free);
197 fseek(in, 0, SEEK_SET);
198 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 struct item_id road_id;
206 double l;
207 fread(&road_id, sizeof(road_id), 1, ref);
208 if (speed)
209 {
210 struct edge_hash_item *hi=g_slice_new(struct edge_hash_item);
211 struct item_id *id=g_slice_new(struct item_id);
212 *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 }
220 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 g_hash_table_insert(edge_hash, hi, id);
224 }
225 }
226 g_hash_table_destroy(hash);
227 }
228
229 static void ch_generate_sgr(char *suffix)
230 {
231 #ifndef HAVE_API_WIN32_CE
232 char command[1024];
233 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 system(command);
236 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 system(command);
239 #endif
240 }
241
242 static void ch_process_node(FILE *out, int node, int resolve)
243 {
244 int first_edge_id = nodes[node].first_edge;
245 int last_edge_id = nodes[node + 1].first_edge;
246 int edge_id;
247 struct ch_edge ch_edge;
248 struct item_bin *item_bin;
249 struct edge_hash_item fwd, rev;
250 int oldnode;
251 memset(&ch_edge, 0, sizeof(ch_edge));
252 item_bin = init_item(type_ch_node, 0);
253 oldnode = GPOINTER_TO_INT(g_hash_table_lookup(newnode_hash, GINT_TO_POINTER(node)));
254 #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 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 struct item_id *id;
267 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 }
279 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 exit(1);
284 }
285 else
286 {
287 ch_edge.middle = *id;
288 #if 0
289 dbg(0,"middle street id for is "ITEM_ID_FMT"\n",ITEM_ID_ARGS(*id));
290 #endif
291 }
292 }
293 else
294 {
295 ch_edge.flags |= 4;
296 id = g_hash_table_lookup(sgr_nodes_hash, GINT_TO_POINTER((int) edge->scmiddle));
297 dbg_assert(id != NULL);
298 ch_edge.middle = *id;
299 #if 0
300 dbg(0,"middle node id for is "ITEM_ID_FMT"\n",ITEM_ID_ARGS(*id));
301 #endif
302 }
303 id = g_hash_table_lookup(sgr_nodes_hash, GINT_TO_POINTER((int) edge->target));
304 #if 0
305 dbg(0,"id for %d is "ITEM_ID_FMT"\n",edge->target,ITEM_ID_ARGS(*id));
306 #endif
307 if (id == NULL)
308 {
309 fprintf(stderr, "Failed to look up target %d\n", edge->target);
310 }
311 else
312 {
313 ch_edge.target = *id;
314 }
315 }
316 item_bin_add_attr_data(item_bin, attr_ch_edge, &ch_edge, sizeof(ch_edge));
317 }
318 item_bin_write(item_bin, out);
319 }
320
321 static void ch_process_nodes(FILE *out, int pos, int count, int resolve)
322 {
323 int i;
324 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 }
328
329 static void ch_process(FILE **files, int depth, int resolve)
330 {
331 int count = newnode_count;
332 int pos = 0;
333
334 while (depth > 0 && pos < newnode_count)
335 {
336 count = (count + 1) / 2;
337 ch_process_nodes(files[depth], pos, count, resolve);
338 pos += count;
339 depth--;
340 }
341 ch_process_nodes(files[depth], pos, newnode_count - pos, resolve);
342 }
343
344 static void ch_setup(char *suffix)
345 {
346 int i;
347 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 g_free(filename);
354 dbg_assert(sgr != NULL);
355 file_mmap(sgr);
356
357 size = sizeof(int);
358 data = (int *) file_data_read(sgr, offset, size);
359 node_count = *data;
360 offset += size;
361
362 size = node_count * sizeof(struct node);
363 nodes = (struct node *) file_data_read(sgr, offset, size);
364 offset += size;
365
366 size = sizeof(int);
367 data = (int *) file_data_read(sgr, offset, size);
368 edge_count = *data;
369 offset += size;
370
371 size = edge_count * sizeof(struct edge);
372 edges = (struct edge *) file_data_read(sgr, offset, size);
373 offset += size;
374
375 size = sizeof(int);
376 data = (int *) file_data_read(sgr, offset, size);
377 newnode_count = *data;
378 offset += size;
379
380 size = edge_count * sizeof(struct newnode);
381 newnodes = (struct newnode *) file_data_read(sgr, offset, size);
382 offset += size;
383
384 newnode_hash = g_hash_table_new(NULL, NULL);
385
386 for (i = 0; i < newnode_count; i++)
387 {
388 g_hash_table_insert(newnode_hash, GINT_TO_POINTER(newnodes[i].newnode), GINT_TO_POINTER(i));
389 }
390 }
391 if (!ddsg_node_index)
392 {
393 char *filename = tempfile_name(suffix, "ddsg_coords");
394 ddsg_node_index = file_create(filename, 0);
395 g_free(filename);
396 dbg_assert(ddsg_node_index != NULL);
397 file_mmap(ddsg_node_index);
398 node_index = (struct coord *) file_data_read(ddsg_node_index, 0, file_size(ddsg_node_index));
399 }
400 }
401
402 static void ch_create_tempfiles(char *suffix, FILE **files, int count, int mode)
403 {
404 char name[256];
405 int i;
406
407 for (i = 0; i <= count; i++)
408 {
409 sprintf(name, "graph_%d", i);
410 files[i] = tempfile(suffix, name, mode);
411 }
412 }
413
414 static void ch_close_tempfiles(FILE **files, int count)
415 {
416 int i;
417
418 for (i = 0; i <= count; i++)
419 {
420 fclose(files[i]);
421 }
422 }
423
424 static void ch_remove_tempfiles(char *suffix, int count)
425 {
426 char name[256];
427 int i;
428
429 for (i = 0; i <= count; i++)
430 {
431 sprintf(name, "graph_%d", i);
432 tempfile_unlink(suffix, name);
433 }
434 }
435
436 static void ch_copy_to_tiles(char *suffix, int count, struct tile_info *info, FILE *ref)
437 {
438 char name[256];
439 int i;
440 FILE *f;
441 struct item_bin *item_bin;
442
443 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 tile_write_item_minmax(info, item_bin, ref, i, i);
450 }
451 fclose(f);
452 }
453 }
454
455 void ch_generate_tiles(char *map_suffix, char *suffix, FILE *tilesdir_out, struct zip_info *zip_info)
456 {
457 struct tile_info info;
458 FILE *in, *ref, *ddsg_coords, *ddsg;
459 FILE **graphfiles;
460 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
467 ch_create_tempfiles(suffix, graphfiles, ch_levels, 1);
468 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 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 tile_hash = g_hash_table_new(g_str_hash, g_str_equal);
483 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 void ch_assemble_map(char *map_suffix, char *suffix, struct zip_info *zip_info)
490 {
491 struct tile_info info;
492 struct tile_head *th;
493 FILE **graphfiles = g_alloca(sizeof(FILE*) * (ch_levels + 1));
494 FILE *ref;
495 struct item_id id;
496 int nodeid = 0;
497
498 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
505 create_tile_hash();
506
507 th = tile_head_root;
508 while (th)
509 {
510 th->zip_data = NULL;
511 th->process = 1;
512 th = th->next;
513 }
514
515 ch_setup(suffix);
516 ch_copy_to_tiles(suffix, ch_levels, &info, ref);
517 fclose(ref);
518 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 struct item_id *id2=g_slice_new(struct item_id);
523 *id2 = id;
524 #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 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 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 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 exit(1);
557 }
558 write_zipmember(zip_info, th->name, zip_get_maxnamelen(zip_info), th->zip_data, th->total_size);
559 }
560 else
561 {
562 fwrite(th->zip_data, th->total_size, 1, zip_get_index(zip_info));
563 }
564 g_free(th->zip_data);
565 th = th->next;
566 }
567 }

   
Visit the ZANavi Wiki