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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 8 - (show annotations) (download)
Fri Oct 28 21:39:42 2011 UTC (12 years, 5 months ago) by zoff99
File MIME type: text/plain
File size: 13631 byte(s)
import
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 int flags;
37 int weight;
38 struct item_id target,middle;
39 };
40
41 struct node {
42 int first_edge;
43 int dummy;
44 } *nodes;
45 int node_count;
46
47 struct edge {
48 unsigned target:26;
49 unsigned scedge1:6;
50 unsigned weight:28;
51 unsigned type:2;
52 unsigned flags:2;
53 unsigned int edge_count;
54 unsigned scedge2:6;
55 unsigned scmiddle:26;
56 } *edges;
57
58 int edge_count;
59
60 struct newnode {
61 int newnode;
62 } *newnodes;
63
64 int newnode_count;
65
66 GHashTable *newnode_hash;
67
68 struct edge_hash_item {
69 int first,last;
70 };
71
72
73 GHashTable *edge_hash;
74
75 struct file *sgr,*ddsg_node_index;
76
77 struct coord *node_index;
78
79 GHashTable *sgr_nodes_hash;
80
81 static int ch_levels=14;
82
83 static int
84 road_speed(enum item_type type)
85 {
86 switch (type) {
87 case type_street_0:
88 case type_street_1_city:
89 case type_living_street:
90 case type_street_service:
91 case type_track_gravelled:
92 case type_track_unpaved:
93 return 10;
94 case type_street_2_city:
95 case type_track_paved:
96 return 30;
97 case type_street_3_city:
98 return 40;
99 case type_street_4_city:
100 return 50;
101 case type_highway_city:
102 return 80;
103 case type_street_1_land:
104 return 60;
105 case type_street_2_land:
106 return 65;
107 case type_street_3_land:
108 return 70;
109 case type_street_4_land:
110 return 80;
111 case type_street_n_lanes:
112 return 120;
113 case type_highway_land:
114 return 120;
115 case type_ramp:
116 return 40;
117 case type_roundabout:
118 return 10;
119 case type_ferry:
120 return 40;
121 default:
122 return 0;
123 }
124 }
125
126 static void
127 coord_slice_free(void *data)
128 {
129 g_slice_free(struct coord, data);
130 }
131
132
133 static GHashTable *
134 coord_hash_new(void)
135 {
136 return g_hash_table_new_full(coord_hash, coord_equal, coord_slice_free, NULL);
137 }
138
139 static void
140 item_id_slice_free(void *data)
141 {
142 g_slice_free(struct item_id, data);
143 }
144
145 #define sq(x) ((double)(x)*(x))
146
147 static void
148 add_node_to_hash(FILE *idx, GHashTable *hash, struct coord *c, int *nodes)
149 {
150 if (! g_hash_table_lookup(hash, c)) {
151 struct coord *ct=g_slice_new(struct coord);
152 *ct=*c;
153 fwrite(c, sizeof(*c), 1, idx);
154 (*nodes)++;
155 g_hash_table_insert(hash, ct, (void *)(*nodes));
156 }
157
158 }
159
160 static void
161 edge_hash_slice_free(void *data)
162 {
163 g_slice_free(struct edge_hash_item, data);
164 }
165
166 static guint
167 edge_hash_hash(gconstpointer key)
168 {
169 const struct edge_hash_item *itm=key;
170 return itm->first*2654435761UL+itm->last;
171 }
172
173 static gboolean
174 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
182
183 static void
184 ch_generate_ddsg(FILE *in, FILE *ref, FILE *idx, FILE *ddsg)
185 {
186 GHashTable *hash=coord_hash_new();
187 struct item_bin *ib;
188 int nodes=0,edges=0;
189
190 while ((ib=read_item(in))) {
191 int ccount=ib->clen/2;
192 struct coord *c=(struct coord *)(ib+1);
193 if (road_speed(ib->type)) {
194 add_node_to_hash(idx, hash, &c[0], &nodes);
195 add_node_to_hash(idx, hash, &c[ccount-1], &nodes);
196 edges++;
197 }
198 }
199 edge_hash=g_hash_table_new_full(edge_hash_hash, edge_hash_equal, edge_hash_slice_free, item_id_slice_free);
200 fseek(in, 0, SEEK_SET);
201 fprintf(ddsg,"d\n");
202 fprintf(ddsg,"%d %d\n", nodes, edges);
203 while ((ib=read_item(in))) {
204 int i,ccount=ib->clen/2;
205 struct coord *c=(struct coord *)(ib+1);
206 int n1,n2,speed=road_speed(ib->type);
207 struct item_id road_id;
208 double l;
209 fread(&road_id, sizeof(road_id), 1, ref);
210 if (speed) {
211 struct edge_hash_item *hi=g_slice_new(struct edge_hash_item);
212 struct item_id *id=g_slice_new(struct item_id);
213 *id=road_id;
214 dbg_assert((n1=GPOINTER_TO_INT(g_hash_table_lookup(hash, &c[0]))) != 0);
215 dbg_assert((n2=GPOINTER_TO_INT(g_hash_table_lookup(hash, &c[ccount-1]))) != 0);
216 l=0;
217 for (i = 0 ; i < ccount-1 ; i++) {
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
230 ch_generate_sgr(char *suffix)
231 {
232 #ifndef HAVE_API_WIN32_CE
233 char command[1024];
234 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);
235 printf("%s\n",command);
236 system(command);
237 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);
238 printf("%s\n",command);
239 system(command);
240 #endif
241 }
242
243 static void
244 ch_process_node(FILE *out, int node, int resolve)
245 {
246 int first_edge_id=nodes[node].first_edge;
247 int last_edge_id=nodes[node+1].first_edge;
248 int edge_id;
249 struct ch_edge ch_edge;
250 struct item_bin *item_bin;
251 struct edge_hash_item fwd,rev;
252 int oldnode;
253 memset(&ch_edge, 0, sizeof(ch_edge));
254 item_bin=init_item(type_ch_node);
255 oldnode=GPOINTER_TO_INT(g_hash_table_lookup(newnode_hash, GINT_TO_POINTER(node)));
256 #if 0
257 dbg(0,"0x%x,0x%x\n",node_index[oldnode].x,node_index[oldnode].y);
258 #endif
259 item_bin_add_coord(item_bin, &node_index[oldnode], 1);
260 fwd.first=oldnode;
261 rev.last=oldnode;
262 for (edge_id = first_edge_id ; edge_id < last_edge_id ; edge_id++) {
263 if (resolve) {
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 id=g_hash_table_lookup(edge_hash, &fwd);
273 if (!id) {
274 ch_edge.flags|=8;
275 id=g_hash_table_lookup(edge_hash, &rev);
276 }
277 if (id == NULL) {
278 fprintf(stderr,"Shortcut %d Weight %d\n",edge->scmiddle,edge->weight);
279 fprintf(stderr,"Neither %d-%d nor %d-%d exists\n",fwd.first,fwd.last,rev.first,rev.last);
280 exit(1);
281 } else {
282 ch_edge.middle=*id;
283 #if 0
284 dbg(0,"middle street id for is "ITEM_ID_FMT"\n",ITEM_ID_ARGS(*id));
285 #endif
286 }
287 } else {
288 ch_edge.flags|=4;
289 id=g_hash_table_lookup(sgr_nodes_hash, GINT_TO_POINTER((int)edge->scmiddle));
290 dbg_assert(id != NULL);
291 ch_edge.middle=*id;
292 #if 0
293 dbg(0,"middle node id for is "ITEM_ID_FMT"\n",ITEM_ID_ARGS(*id));
294 #endif
295 }
296 id=g_hash_table_lookup(sgr_nodes_hash, GINT_TO_POINTER((int)edge->target));
297 #if 0
298 dbg(0,"id for %d is "ITEM_ID_FMT"\n",edge->target,ITEM_ID_ARGS(*id));
299 #endif
300 if (id == NULL) {
301 fprintf(stderr,"Failed to look up target %d\n",edge->target);
302 } else {
303 ch_edge.target=*id;
304 }
305 }
306 item_bin_add_attr_data(item_bin,attr_ch_edge,&ch_edge,sizeof(ch_edge));
307 }
308 item_bin_write(item_bin, out);
309 }
310
311 static void
312 ch_process_nodes(FILE *out, int pos, int count, int resolve)
313 {
314 int i;
315 printf("count %d sum=%d newnode_count=%d\n",count,pos,newnode_count);
316 for (i = 0 ; i < count ; i++)
317 ch_process_node(out, pos+i, resolve);
318 }
319
320
321 static void
322 ch_process(FILE **files, int depth, int resolve)
323 {
324 int count=newnode_count;
325 int pos=0;
326
327 while (depth > 0 && pos < newnode_count) {
328 count=(count+1)/2;
329 ch_process_nodes(files[depth], pos, count, resolve);
330 pos+=count;
331 depth--;
332 }
333 ch_process_nodes(files[depth], pos, newnode_count-pos, resolve);
334 }
335
336 static void
337 ch_setup(char *suffix)
338 {
339 int i;
340 if (!sgr) {
341 int *data,size,offset=0;
342 char *filename=tempfile_name(suffix,"sgr");
343 printf("filename=%s\n",filename);
344 sgr=file_create(filename,0);
345 g_free(filename);
346 dbg_assert(sgr != NULL);
347 file_mmap(sgr);
348
349 size=sizeof(int);
350 data=(int *)file_data_read(sgr, offset, size);
351 node_count=*data;
352 offset+=size;
353
354 size=node_count*sizeof(struct node);
355 nodes=(struct node *)file_data_read(sgr, offset, size);
356 offset+=size;
357
358 size=sizeof(int);
359 data=(int *)file_data_read(sgr, offset, size);
360 edge_count=*data;
361 offset+=size;
362
363 size=edge_count*sizeof(struct edge);
364 edges=(struct edge *)file_data_read(sgr, offset, size);
365 offset+=size;
366
367 size=sizeof(int);
368 data=(int *)file_data_read(sgr, offset, size);
369 newnode_count=*data;
370 offset+=size;
371
372 size=edge_count*sizeof(struct newnode);
373 newnodes=(struct newnode *)file_data_read(sgr, offset, size);
374 offset+=size;
375
376 newnode_hash=g_hash_table_new(NULL, NULL);
377
378 for (i = 0 ; i < newnode_count ; i++) {
379 g_hash_table_insert(newnode_hash, GINT_TO_POINTER(newnodes[i].newnode), GINT_TO_POINTER(i));
380 }
381 }
382 if (!ddsg_node_index) {
383 char *filename=tempfile_name(suffix,"ddsg_coords");
384 ddsg_node_index=file_create(filename,0);
385 g_free(filename);
386 dbg_assert(ddsg_node_index != NULL);
387 file_mmap(ddsg_node_index);
388 node_index=(struct coord *)file_data_read(ddsg_node_index, 0, file_size(ddsg_node_index));
389 }
390 }
391
392 static void
393 ch_create_tempfiles(char *suffix, FILE **files, int count, int mode)
394 {
395 char name[256];
396 int i;
397
398 for (i = 0 ; i <= count ; i++) {
399 sprintf(name,"graph_%d",i);
400 files[i]=tempfile(suffix, name, mode);
401 }
402 }
403
404 static void
405 ch_close_tempfiles(FILE **files, int count)
406 {
407 int i;
408
409 for (i = 0 ; i <= count ; i++) {
410 fclose(files[i]);
411 }
412 }
413
414 static void
415 ch_remove_tempfiles(char *suffix, int count)
416 {
417 char name[256];
418 int i;
419
420 for (i = 0 ; i <= count ; i++) {
421 sprintf(name,"graph_%d",i);
422 tempfile_unlink(suffix, name);
423 }
424 }
425
426 static void
427 ch_copy_to_tiles(char *suffix, int count, struct tile_info *info, FILE *ref)
428 {
429 char name[256];
430 int i;
431 FILE *f;
432 struct item_bin *item_bin;
433
434 for (i = count ; i >= 0 ; i--) {
435 sprintf(name,"graph_%d",i);
436 f=tempfile(suffix, name, 0);
437 while ((item_bin = read_item(f))) {
438 tile_write_item_minmax(info, item_bin, ref, i, i);
439 }
440 fclose(f);
441 }
442 }
443
444 void
445 ch_generate_tiles(char *map_suffix, char *suffix, FILE *tilesdir_out, struct zip_info *zip_info)
446 {
447 struct tile_info info;
448 FILE *in,*ref,*ddsg_coords,*ddsg;
449 FILE **graphfiles;
450 info.write=0;
451 info.maxlen=0;
452 info.suffix=suffix;
453 info.tiles_list=NULL;
454 info.tilesdir_out=tilesdir_out;
455 graphfiles=g_alloca(sizeof(FILE*)*(ch_levels+1));
456
457 ch_create_tempfiles(suffix, graphfiles, ch_levels, 1);
458 in=tempfile(map_suffix,"ways_split",0);
459 ref=tempfile(map_suffix,"ways_split_ref",0);
460 ddsg_coords=tempfile(suffix,"ddsg_coords",1);
461 ddsg=tempfile(suffix,"ddsg",1);
462 ch_generate_ddsg(in, ref, ddsg_coords, ddsg);
463 fclose(in);
464 fclose(ref);
465 fclose(ddsg_coords);
466 fclose(ddsg);
467 ch_generate_sgr(suffix);
468 ch_setup(suffix);
469 ch_process(graphfiles, ch_levels, 0);
470 ch_close_tempfiles(graphfiles, ch_levels);
471
472 tile_hash=g_hash_table_new(g_str_hash, g_str_equal);
473 ch_copy_to_tiles(suffix, ch_levels, &info, NULL);
474 merge_tiles(&info);
475
476 write_tilesdir(&info, zip_info, tilesdir_out);
477 }
478
479 void
480 ch_assemble_map(char *map_suffix, char *suffix, struct zip_info *zip_info)
481 {
482 struct tile_info info;
483 struct tile_head *th;
484 FILE **graphfiles=g_alloca(sizeof(FILE*)*(ch_levels+1));
485 FILE *ref;
486 struct item_id id;
487 int nodeid=0;
488
489 info.write=1;
490 info.maxlen=zip_get_maxnamelen(zip_info);
491 info.suffix=suffix;
492 info.tiles_list=NULL;
493 info.tilesdir_out=NULL;
494 ref=tempfile(suffix,"sgr_ref",1);
495
496 create_tile_hash();
497
498 th=tile_head_root;
499 while (th) {
500 th->zip_data=NULL;
501 th->process=1;
502 th=th->next;
503 }
504
505 ch_setup(suffix);
506 ch_copy_to_tiles(suffix, ch_levels, &info, ref);
507 fclose(ref);
508 ref=tempfile(suffix,"sgr_ref",0);
509 sgr_nodes_hash=g_hash_table_new_full(NULL, NULL, NULL, item_id_slice_free);
510 while (fread(&id, sizeof(id), 1, ref)) {
511 struct item_id *id2=g_slice_new(struct item_id);
512 *id2=id;
513 #if 0
514 dbg(0,"%d is "ITEM_ID_FMT"\n",nodeid,ITEM_ID_ARGS(*id2));
515 #endif
516 g_hash_table_insert(sgr_nodes_hash, GINT_TO_POINTER(nodeid), id2);
517 nodeid++;
518 }
519 th=tile_head_root;
520 while (th) {
521 th->zip_data=malloc(th->total_size);
522 th->total_size_used=0;
523 th=th->next;
524 }
525 ch_create_tempfiles(suffix, graphfiles, ch_levels, 1);
526 ch_process(graphfiles, ch_levels, 1);
527 ch_close_tempfiles(graphfiles, ch_levels);
528
529 g_hash_table_destroy(newnode_hash);
530 g_hash_table_destroy(edge_hash);
531 g_hash_table_destroy(sgr_nodes_hash);
532
533 ch_copy_to_tiles(suffix, ch_levels, &info, NULL);
534 write_tilesdir(&info, zip_info, NULL);
535
536 th=tile_head_root;
537 while (th) {
538 if (th->name[0]) {
539 if (th->total_size != th->total_size_used) {
540 fprintf(stderr,"Size error '%s': %d vs %d\n", th->name, th->total_size, th->total_size_used);
541 exit(1);
542 }
543 write_zipmember(zip_info, th->name, zip_get_maxnamelen(zip_info), th->zip_data, th->total_size);
544 } else {
545 fwrite(th->zip_data, th->total_size, 1, zip_get_index(zip_info));
546 }
547 g_free(th->zip_data);
548 th=th->next;
549 }
550 }

   
Visit the ZANavi Wiki