/[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 - (hide 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 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     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