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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 57 - (show annotations) (download)
Sun Mar 19 16:46:08 2017 UTC (7 years ago) by zoff99
File MIME type: text/plain
File size: 14006 byte(s)
updates
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 #if 0
120 case type_ramp:
121 return 40;
122 #endif
123 case type_roundabout:
124 return 10;
125 case type_ferry:
126 return 40;
127 default:
128 return 0;
129 }
130 }
131
132 static void coord_slice_free(void *data)
133 {
134 g_slice_free(struct coord, data);
135 }
136
137 static GHashTable *
138 coord_hash_new(void)
139 {
140 return g_hash_table_new_full(coord_hash, coord_equal, coord_slice_free, NULL);
141 }
142
143 static void item_id_slice_free(void *data)
144 {
145 g_slice_free(struct item_id, data);
146 }
147
148 #define sq(x) ((double)(x)*(x))
149
150 static void add_node_to_hash(FILE *idx, GHashTable *hash, struct coord *c, int *nodes)
151 {
152 if (!g_hash_table_lookup(hash, c))
153 {
154 struct coord *ct=g_slice_new(struct coord);
155 *ct = *c;
156 fwrite(c, sizeof(*c), 1, idx);
157 (*nodes)++;
158 g_hash_table_insert(hash, ct, (void *) (*nodes));
159 }
160
161 }
162
163 static void edge_hash_slice_free(void *data)
164 {
165 g_slice_free(struct edge_hash_item, data);
166 }
167
168 static guint edge_hash_hash(gconstpointer key)
169 {
170 const struct edge_hash_item *itm = key;
171 return itm->first * 2654435761UL + itm->last;
172 }
173
174 static gboolean edge_hash_equal(gconstpointer a, gconstpointer b)
175 {
176 const struct edge_hash_item *itm_a = a;
177 const struct edge_hash_item *itm_b = b;
178 return (itm_a->first == itm_b->first && itm_a->last == itm_b->last);
179 }
180
181 static void ch_generate_ddsg(FILE *in, FILE *ref, FILE *idx, FILE *ddsg)
182 {
183 }
184
185 static void ch_generate_ddsg_XX(FILE *in, FILE *ref, FILE *idx, FILE *ddsg)
186 {
187 GHashTable *hash = coord_hash_new();
188 struct item_bin *ib;
189 int nodes = 0, edges = 0;
190
191 while ((ib = read_item(in, 0)))
192 {
193 int ccount = ib->clen / 2;
194 struct coord *c = (struct coord *) (ib + 1);
195 if (road_speed(ib->type))
196 {
197 add_node_to_hash(idx, hash, &c[0], &nodes);
198 add_node_to_hash(idx, hash, &c[ccount - 1], &nodes);
199 edges++;
200 }
201 }
202 edge_hash = g_hash_table_new_full(edge_hash_hash, edge_hash_equal, edge_hash_slice_free, item_id_slice_free);
203 fseek(in, 0, SEEK_SET);
204 fprintf(ddsg, "d\n");
205 fprintf(ddsg, "%d %d\n", nodes, edges);
206 while ((ib = read_item(in, 0)))
207 {
208 int i, ccount = ib->clen / 2;
209 struct coord *c = (struct coord *) (ib + 1);
210 int n1, n2, speed = road_speed(ib->type);
211 struct item_id road_id;
212 double l;
213 fread(&road_id, sizeof(road_id), 1, ref);
214 if (speed)
215 {
216 struct edge_hash_item *hi=g_slice_new(struct edge_hash_item);
217 struct item_id *id=g_slice_new(struct item_id);
218 *id = road_id;
219 dbg_assert((n1 = GPOINTER_TO_INT(g_hash_table_lookup(hash, &c[0]))) != 0);
220 dbg_assert((n2 = GPOINTER_TO_INT(g_hash_table_lookup(hash, &c[ccount - 1]))) != 0);
221 l = 0;
222 for (i = 0; i < ccount - 1; i++)
223 {
224 l += sqrt(sq(c[i+1].x-c[i].x) + sq(c[i+1].y-c[i].y));
225 }
226 fprintf(ddsg, "%d %d %d 0\n", n1 - 1, n2 - 1, (int) (l * 36 / speed));
227 hi->first = n1 - 1;
228 hi->last = n2 - 1;
229 g_hash_table_insert(edge_hash, hi, id);
230 }
231 }
232 g_hash_table_destroy(hash);
233 }
234
235 static void ch_generate_sgr(char *suffix)
236 {
237 #ifndef HAVE_API_WIN32_CE
238 char command[1024];
239 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);
240 printf("%s\n", command);
241 system(command);
242 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);
243 printf("%s\n", command);
244 system(command);
245 #endif
246 }
247
248 static void ch_process_node(FILE *out, int node, int resolve)
249 {
250 int first_edge_id = nodes[node].first_edge;
251 int last_edge_id = nodes[node + 1].first_edge;
252 int edge_id;
253 struct ch_edge ch_edge;
254 struct item_bin *item_bin;
255 struct edge_hash_item fwd, rev;
256 int oldnode;
257 memset(&ch_edge, 0, sizeof(ch_edge));
258 item_bin = init_item(type_ch_node, 0);
259 oldnode = GPOINTER_TO_INT(g_hash_table_lookup(newnode_hash, GINT_TO_POINTER(node)));
260 #if 0
261 dbg(0,"0x%x,0x%x\n",node_index[oldnode].x,node_index[oldnode].y);
262 #endif
263 item_bin_add_coord(item_bin, &node_index[oldnode], 1);
264 fwd.first = oldnode;
265 rev.last = oldnode;
266 for (edge_id = first_edge_id; edge_id < last_edge_id; edge_id++)
267 {
268 if (resolve)
269 {
270 struct edge *edge = &edges[edge_id];
271 int oldnode = GPOINTER_TO_INT(g_hash_table_lookup(newnode_hash, GINT_TO_POINTER((int) edge->target)));
272 struct item_id *id;
273 ch_edge.weight = edge->weight;
274 fwd.last = oldnode;
275 rev.first = oldnode;
276 ch_edge.flags = edge->flags & 3;
277 if (edge->scmiddle == 67108863)
278 {
279 id = g_hash_table_lookup(edge_hash, &fwd);
280 if (!id)
281 {
282 ch_edge.flags |= 8;
283 id = g_hash_table_lookup(edge_hash, &rev);
284 }
285 if (id == NULL)
286 {
287 fprintf(stderr, "Shortcut %d Weight %d\n", edge->scmiddle, edge->weight);
288 fprintf(stderr, "Neither %d-%d nor %d-%d exists\n", fwd.first, fwd.last, rev.first, rev.last);
289 exit(1);
290 }
291 else
292 {
293 ch_edge.middle = *id;
294 #if 0
295 dbg(0,"middle street id for is "ITEM_ID_FMT"\n",ITEM_ID_ARGS(*id));
296 #endif
297 }
298 }
299 else
300 {
301 ch_edge.flags |= 4;
302 id = g_hash_table_lookup(sgr_nodes_hash, GINT_TO_POINTER((int) edge->scmiddle));
303 dbg_assert(id != NULL);
304 ch_edge.middle = *id;
305 #if 0
306 dbg(0,"middle node id for is "ITEM_ID_FMT"\n",ITEM_ID_ARGS(*id));
307 #endif
308 }
309 id = g_hash_table_lookup(sgr_nodes_hash, GINT_TO_POINTER((int) edge->target));
310 #if 0
311 dbg(0,"id for %d is "ITEM_ID_FMT"\n",edge->target,ITEM_ID_ARGS(*id));
312 #endif
313 if (id == NULL)
314 {
315 fprintf(stderr, "Failed to look up target %d\n", edge->target);
316 }
317 else
318 {
319 ch_edge.target = *id;
320 }
321 }
322 item_bin_add_attr_data(item_bin, attr_ch_edge, &ch_edge, sizeof(ch_edge));
323 }
324 item_bin_write(item_bin, out);
325 }
326
327 static void ch_process_nodes(FILE *out, int pos, int count, int resolve)
328 {
329 int i;
330 printf("count %d sum=%d newnode_count=%d\n", count, pos, newnode_count);
331 for (i = 0; i < count; i++)
332 ch_process_node(out, pos + i, resolve);
333 }
334
335 static void ch_process(FILE **files, int depth, int resolve)
336 {
337 int count = newnode_count;
338 int pos = 0;
339
340 while (depth > 0 && pos < newnode_count)
341 {
342 count = (count + 1) / 2;
343 ch_process_nodes(files[depth], pos, count, resolve);
344 pos += count;
345 depth--;
346 }
347 ch_process_nodes(files[depth], pos, newnode_count - pos, resolve);
348 }
349
350 static void ch_setup(char *suffix)
351 {
352 int i;
353 if (!sgr)
354 {
355 int *data, size, offset = 0;
356 char *filename = tempfile_name(suffix, "sgr");
357 printf("filename=%s\n", filename);
358 sgr = file_create(filename, 0);
359 g_free(filename);
360 dbg_assert(sgr != NULL);
361 file_mmap(sgr);
362
363 size = sizeof(int);
364 data = (int *) file_data_read(sgr, offset, size);
365 node_count = *data;
366 offset += size;
367
368 size = node_count * sizeof(struct node);
369 nodes = (struct node *) file_data_read(sgr, offset, size);
370 offset += size;
371
372 size = sizeof(int);
373 data = (int *) file_data_read(sgr, offset, size);
374 edge_count = *data;
375 offset += size;
376
377 size = edge_count * sizeof(struct edge);
378 edges = (struct edge *) file_data_read(sgr, offset, size);
379 offset += size;
380
381 size = sizeof(int);
382 data = (int *) file_data_read(sgr, offset, size);
383 newnode_count = *data;
384 offset += size;
385
386 size = edge_count * sizeof(struct newnode);
387 newnodes = (struct newnode *) file_data_read(sgr, offset, size);
388 offset += size;
389
390 newnode_hash = g_hash_table_new(NULL, NULL);
391
392 for (i = 0; i < newnode_count; i++)
393 {
394 g_hash_table_insert(newnode_hash, GINT_TO_POINTER(newnodes[i].newnode), GINT_TO_POINTER(i));
395 }
396 }
397 if (!ddsg_node_index)
398 {
399 char *filename = tempfile_name(suffix, "ddsg_coords");
400 ddsg_node_index = file_create(filename, 0);
401 g_free(filename);
402 dbg_assert(ddsg_node_index != NULL);
403 file_mmap(ddsg_node_index);
404 node_index = (struct coord *) file_data_read(ddsg_node_index, 0, file_size(ddsg_node_index));
405 }
406 }
407
408 static void ch_create_tempfiles(char *suffix, FILE **files, int count, int mode)
409 {
410 char name[256];
411 int i;
412
413 for (i = 0; i <= count; i++)
414 {
415 sprintf(name, "graph_%d", i);
416 files[i] = tempfile(suffix, name, mode);
417 }
418 }
419
420 static void ch_close_tempfiles(FILE **files, int count)
421 {
422 int i;
423
424 for (i = 0; i <= count; i++)
425 {
426 fclose(files[i]);
427 }
428 }
429
430 static void ch_remove_tempfiles(char *suffix, int count)
431 {
432 char name[256];
433 int i;
434
435 for (i = 0; i <= count; i++)
436 {
437 sprintf(name, "graph_%d", i);
438 tempfile_unlink(suffix, name);
439 }
440 }
441
442 static void ch_copy_to_tiles(char *suffix, int count, struct tile_info *info, FILE *ref)
443 {
444 char name[256];
445 int i;
446 FILE *f;
447 struct item_bin *item_bin;
448
449 for (i = count; i >= 0; i--)
450 {
451 sprintf(name, "graph_%d", i);
452 f = tempfile(suffix, name, 0);
453 while ((item_bin = read_item(f, 0)))
454 {
455 tile_write_item_minmax(info, item_bin, ref, i, i);
456 }
457 fclose(f);
458 }
459 }
460
461 void ch_generate_tiles(char *map_suffix, char *suffix, FILE *tilesdir_out, struct zip_info *zip_info)
462 {
463 struct tile_info info;
464 FILE *in, *ref, *ddsg_coords, *ddsg;
465 FILE **graphfiles;
466 info.write = 0;
467 info.maxlen = 0;
468 info.suffix = suffix;
469 info.tiles_list = NULL;
470 info.tilesdir_out = tilesdir_out;
471 graphfiles = g_alloca(sizeof(FILE*) * (ch_levels + 1));
472
473 ch_create_tempfiles(suffix, graphfiles, ch_levels, 1);
474 in = tempfile(map_suffix, "ways_split", 0);
475 ref = tempfile(map_suffix, "ways_split_ref", 0);
476 ddsg_coords = tempfile(suffix, "ddsg_coords", 1);
477 ddsg = tempfile(suffix, "ddsg", 1);
478 ch_generate_ddsg(in, ref, ddsg_coords, ddsg);
479 fclose(in);
480 fclose(ref);
481 fclose(ddsg_coords);
482 fclose(ddsg);
483 ch_generate_sgr(suffix);
484 ch_setup(suffix);
485 ch_process(graphfiles, ch_levels, 0);
486 ch_close_tempfiles(graphfiles, ch_levels);
487
488 tile_hash = g_hash_table_new(g_str_hash, g_str_equal);
489 ch_copy_to_tiles(suffix, ch_levels, &info, NULL);
490 merge_tiles(&info);
491
492 write_tilesdir(&info, zip_info, tilesdir_out);
493 }
494
495 void ch_assemble_map(char *map_suffix, char *suffix, struct zip_info *zip_info)
496 {
497 struct tile_info info;
498 struct tile_head *th;
499 FILE **graphfiles = g_alloca(sizeof(FILE*) * (ch_levels + 1));
500 FILE *ref;
501 struct item_id id;
502 int nodeid = 0;
503
504 fprintf(stderr, "-----:ch_assemble_map:-----\n");
505
506 info.write = 1;
507 info.maxlen = zip_get_maxnamelen(zip_info);
508 info.suffix = suffix;
509 info.tiles_list = NULL;
510 info.tilesdir_out = NULL;
511 ref = tempfile(suffix, "sgr_ref", 1);
512
513 create_tile_hash();
514
515 th = tile_head_root;
516 while (th)
517 {
518 th->zip_data = NULL;
519 th->process = 1;
520 th = th->next;
521 }
522
523 ch_setup(suffix);
524 ch_copy_to_tiles(suffix, ch_levels, &info, ref);
525 fclose(ref);
526 ref = tempfile(suffix, "sgr_ref", 0);
527 sgr_nodes_hash = g_hash_table_new_full(NULL, NULL, NULL, item_id_slice_free);
528 while (fread(&id, sizeof(id), 1, ref))
529 {
530 struct item_id *id2=g_slice_new(struct item_id);
531 *id2 = id;
532 #if 0
533 dbg(0,"%d is "ITEM_ID_FMT"\n",nodeid,ITEM_ID_ARGS(*id2));
534 #endif
535 g_hash_table_insert(sgr_nodes_hash, GINT_TO_POINTER(nodeid), id2);
536 nodeid++;
537 }
538 th = tile_head_root;
539 while (th)
540 {
541 th->zip_data = malloc(th->total_size);
542 th->total_size_used = 0;
543 th = th->next;
544 }
545 ch_create_tempfiles(suffix, graphfiles, ch_levels, 1);
546 ch_process(graphfiles, ch_levels, 1);
547 ch_close_tempfiles(graphfiles, ch_levels);
548
549 g_hash_table_destroy(newnode_hash);
550 g_hash_table_destroy(edge_hash);
551 g_hash_table_destroy(sgr_nodes_hash);
552
553 ch_copy_to_tiles(suffix, ch_levels, &info, NULL);
554 write_tilesdir(&info, zip_info, NULL);
555
556 th = tile_head_root;
557 while (th)
558 {
559 if (th->name[0])
560 {
561 if (th->total_size != th->total_size_used)
562 {
563 fprintf(stderr, "Size error '%s': %d vs %d\n", th->name, th->total_size, th->total_size_used);
564 exit(1);
565 }
566 write_zipmember(zip_info, th->name, zip_get_maxnamelen(zip_info), th->zip_data, th->total_size);
567 }
568 else
569 {
570 fwrite(th->zip_data, th->total_size, 1, zip_get_index(zip_info));
571 }
572 g_free(th->zip_data);
573 th = th->next;
574 }
575 }

   
Visit the ZANavi Wiki