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

Contents of /navit/navit/maptool/coastline.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 8 - (show annotations) (download)
Fri Oct 28 21:39:42 2011 UTC (9 years ago) by zoff99
File MIME type: text/plain
File size: 17336 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 #include "maptool.h"
20 #include "debug.h"
21
22 static int distance_from_ll(struct coord *c, struct rect *bbox)
23 {
24 int dist=0;
25 if (c->x == bbox->l.x)
26 return dist+c->y-bbox->l.y;
27 dist+=bbox->h.y-bbox->l.y;
28 if (c->y == bbox->h.y)
29 return dist+c->x-bbox->l.x;
30 dist+=bbox->h.x-bbox->l.x;
31 if (c->x == bbox->h.x)
32 return dist+bbox->h.y-c->y;
33 dist+=bbox->h.y-bbox->l.y;
34 if (c->y == bbox->l.y)
35 return dist+bbox->h.x-c->x;
36 return -1;
37 }
38
39 static struct geom_poly_segment *
40 find_next(struct rect *bbox, GList *segments, struct coord *c, int exclude, struct coord *ci)
41 {
42 int min=INT_MAX,search=distance_from_ll(c, bbox)+(exclude?1:0);
43 GList *curr;
44 int i;
45 struct geom_poly_segment *ret=NULL;
46 int dbgl=1;
47
48 for (i = 0 ; i < 2 ; i++) {
49 curr=segments;
50 dbg(dbgl,"search distance %d\n",search);
51 while (curr) {
52 struct geom_poly_segment *seg=curr->data;
53 int dist=distance_from_ll(seg->first, bbox);
54 dbg(dbgl,"0x%x 0x%x dist %d\n",seg->first->x,seg->first->y,dist);
55 if (dist != -1 && seg->first != seg->last && dist < min && (dist >= search)) {
56 min=dist;
57 ci[0]=*seg->first;
58 ci[1]=*seg->last;
59 ret=seg;
60 }
61 curr=g_list_next(curr);
62 }
63 if (ret || !search)
64 break;
65 search=0;
66 }
67 return ret;
68 }
69
70 static void
71 close_polygon(struct item_bin *ib, struct coord *from, struct coord *to, int dir, struct rect *bbox, int *edges)
72 {
73 int i,e,dist,fromdist,todist;
74 int full=(bbox->h.x-bbox->l.x+bbox->h.y-bbox->l.y)*2;
75 int corners=0,first_corner=0;
76 struct coord c;
77 if (dir > 0) {
78 fromdist=distance_from_ll(from, bbox);
79 todist=distance_from_ll(to, bbox);
80 } else {
81 fromdist=distance_from_ll(to, bbox);
82 todist=distance_from_ll(from, bbox);
83 }
84 #if 0
85 fprintf(stderr,"close_polygon fromdist %d todist %d full %d dir %d\n", fromdist, todist, full, dir);
86 #endif
87 if (fromdist > todist)
88 todist+=full;
89 #if 0
90 fprintf(stderr,"close_polygon corrected fromdist %d todist %d full %d dir %d\n", fromdist, todist, full, dir);
91 #endif
92 for (i = 0 ; i < 8 ; i++) {
93 if (dir > 0)
94 e=i;
95 else
96 e=7-i;
97 switch (e%4) {
98 case 0:
99 c=bbox->l;
100 break;
101 case 1:
102 c.x=bbox->l.x;
103 c.y=bbox->h.y;
104 break;
105 case 2:
106 c=bbox->h;
107 break;
108 case 3:
109 c.x=bbox->h.x;
110 c.y=bbox->l.y;
111 break;
112 }
113 dist=distance_from_ll(&c, bbox);
114 if (e & 4)
115 dist+=full;
116 #if 0
117 fprintf(stderr,"dist %d %d\n",e,dist);
118 #endif
119 if (dist > fromdist && dist < todist) {
120 item_bin_add_coord(ib, &c, 1);
121 #if 0
122 fprintf(stderr,"add\n");
123 #endif
124 }
125 if (dist >= fromdist && dist <= todist) {
126 if (!corners)
127 first_corner=e;
128 corners++;
129 }
130 }
131 while (corners >= 2) {
132 *edges |= 1<<(first_corner%4);
133 first_corner++;
134 corners--;
135 }
136 }
137
138 struct coastline_tile_data {
139 struct item_bin_sink_func *sink;
140 GHashTable *tile_edges;
141 int level;
142 };
143
144 static GList *
145 tile_data_to_segments(int *tile_data)
146 {
147 int *end=tile_data+tile_data[0];
148 int *curr=tile_data+1;
149 GList *segments=NULL;
150 int count=0;
151
152 while (curr < end) {
153 struct item_bin *ib=(struct item_bin *)curr;
154 segments=g_list_prepend(segments,item_bin_to_poly_segment(ib, geom_poly_segment_type_way_right_side));
155 curr+=ib->len+1;
156 count++;
157 }
158 #if 0
159 fprintf(stderr,"%d segments\n",count);
160 #endif
161 return segments;
162 }
163
164 static void
165 tile_collector_process_tile(char *tile, int *tile_data, struct coastline_tile_data *data)
166 {
167 int poly_start_valid,tile_start_valid,exclude,search=0;
168 struct rect bbox;
169 struct coord cn[2],end,poly_start,tile_start;
170 struct geom_poly_segment *first;
171 struct item_bin *ib=NULL;
172 struct item_bin_sink *out=data->sink->priv_data[1];
173 int dbgl=1;
174 int edges=0,flags;
175 GList *sorted_segments,*curr;
176 #if 0
177 if (strncmp(tile,"bcdbdcabddddba",7))
178 return;
179 #endif
180 #if 0
181 if (strncmp(tile,"bcdbdcaaaaddba",14))
182 return;
183 #endif
184 #if 0
185 fprintf(stderr,"tile %s of size %d\n", tile, *tile_data);
186 #endif
187 tile_bbox(tile, &bbox, 0);
188 sorted_segments=geom_poly_segments_sort(tile_data_to_segments(tile_data), geom_poly_segment_type_way_right_side);
189 #if 0
190 {
191 GList *sort_segments=sorted_segments;
192 int count=0;
193 while (sort_segments) {
194 struct geom_poly_segment *seg=sort_segments->data;
195 struct item_bin *ib=(struct item_bin *)buffer;
196 char *text=g_strdup_printf("segment %d type %d %p %s area "LONGLONG_FMT,count++,seg->type,sort_segments,coord_is_equal(*seg->first, *seg->last) ? "closed":"open",geom_poly_area(seg->first,seg->last-seg->first+1));
197 item_bin_init(ib, type_rg_segment);
198 item_bin_add_coord(ib, seg->first, seg->last-seg->first+1);
199 item_bin_add_attr_string(ib, attr_debug, text);
200 // fprintf(stderr,"%s\n",text);
201 g_free(text);
202 // item_bin_dump(ib, stderr);
203 item_bin_write_to_sink(ib, out, NULL);
204 sort_segments=g_list_next(sort_segments);
205 }
206 }
207 #endif
208 flags=0;
209 curr=sorted_segments;
210 while (curr) {
211 struct geom_poly_segment *seg=curr->data;
212 switch (seg->type) {
213 case geom_poly_segment_type_way_inner:
214 flags|=1;
215 break;
216 case geom_poly_segment_type_way_outer:
217 flags|=2;
218 break;
219 default:
220 flags|=4;
221 break;
222 }
223 curr=g_list_next(curr);
224 }
225 if (flags == 1) {
226 ib=init_item(type_poly_water_tiled);
227 item_bin_bbox(ib, &bbox);
228 item_bin_write_to_sink(ib, out, NULL);
229 g_hash_table_insert(data->tile_edges, g_strdup(tile), (void *)15);
230 return;
231 }
232 #if 1
233 end=bbox.l;
234 tile_start_valid=0;
235 poly_start_valid=0;
236 exclude=0;
237 poly_start.x=0;
238 poly_start.y=0;
239 tile_start.x=0;
240 tile_start.y=0;
241 for (;;) {
242 search++;
243 // item_bin_write_debug_point_to_sink(out, &end, "Search %d",search);
244 dbg(dbgl,"searching next polygon from 0x%x 0x%x\n",end.x,end.y);
245 first=find_next(&bbox, sorted_segments, &end, exclude, cn);
246 exclude=1;
247 if (!first)
248 break;
249 if (!tile_start_valid) {
250 tile_start=cn[0];
251 tile_start_valid=1;
252 } else {
253 if (cn[0].x == tile_start.x && cn[0].y == tile_start.y) {
254 dbg(dbgl,"end of tile reached\n");
255 break;
256 }
257 }
258 if (first->type == geom_poly_segment_type_none) {
259 end=cn[0];
260 continue;
261 }
262 poly_start_valid=0;
263 dbg(dbgl,"start of polygon 0x%x 0x%x\n",cn[0].x,cn[0].y);
264 for (;;) {
265 if (!poly_start_valid) {
266 poly_start=cn[0];
267 poly_start_valid=1;
268 ib=init_item(type_poly_water_tiled);
269 } else {
270 close_polygon(ib, &end, &cn[0], 1, &bbox, &edges);
271 if (cn[0].x == poly_start.x && cn[0].y == poly_start.y) {
272 dbg(dbgl,"poly end reached\n");
273 item_bin_write_to_sink(ib, out, NULL);
274 end=cn[0];
275 break;
276 }
277 }
278 if (first->type == geom_poly_segment_type_none)
279 break;
280 item_bin_add_coord(ib, first->first, first->last-first->first+1);
281 first->type=geom_poly_segment_type_none;
282 end=cn[1];
283 if (distance_from_ll(&end, &bbox) == -1) {
284 dbg(dbgl,"incomplete\n");
285 break;
286 }
287 first=find_next(&bbox, sorted_segments, &end, 1, cn);
288 dbg(dbgl,"next segment of polygon 0x%x 0x%x\n",cn[0].x,cn[0].y);
289 }
290 if (search > 55)
291 break;
292 }
293 #endif
294
295 #if 0
296 {
297 int *end=tile_data+tile_data[0];
298 int *curr=tile_data+1;
299 while (curr < end) {
300 struct item_bin *ib=(struct item_bin *)curr;
301 // item_bin_dump(ib);
302 ib->type=type_rg_segment;
303 item_bin_write_to_sink(ib, out, NULL);
304 curr+=ib->len+1;
305 #if 0
306 {
307 struct coord *c[2];
308 int i;
309 char *s;
310 c[0]=(struct coord *)(ib+1);
311 c[1]=c[0]+ib->clen/2-1;
312 for (i = 0 ; i < 2 ; i++) {
313 s=coord_to_str(c[i]);
314 item_bin_write_debug_point_to_sink(out, c[i], "%s",s);
315 g_free(s);
316 }
317
318 }
319 #endif
320 }
321 }
322 #endif
323 g_hash_table_insert(data->tile_edges, g_strdup(tile), (void *)edges);
324 #if 0
325 item_bin_init(ib, type_border_country);
326 item_bin_bbox(ib, &bbox);
327 item_bin_add_attr_string(ib, attr_debug, tile);
328 item_bin_write_to_sink(ib, out, NULL);
329 #endif
330 #if 0
331 c.x=(bbox.l.x+bbox.h.x)/2;
332 c.y=(bbox.l.y+bbox.h.y)/2;
333 item_bin_write_debug_point_to_sink(out, &c, "%s %d",tile,edges);
334 #endif
335 }
336
337 static void
338 ocean_tile(GHashTable *hash, char *tile, char c, struct item_bin_sink *out)
339 {
340 int len=strlen(tile);
341 char *tile2=g_alloca(sizeof(char)*(len+1));
342 struct rect bbox;
343 struct item_bin *ib;
344 struct coord co;
345
346 strcpy(tile2, tile);
347 tile2[len-1]=c;
348 //fprintf(stderr,"Testing %s\n",tile2);
349 if (g_hash_table_lookup_extended(hash, tile2, NULL, NULL))
350 return;
351 //fprintf(stderr,"%s ok\n",tile2);
352 tile_bbox(tile2, &bbox, 0);
353 ib=init_item(type_poly_water_tiled);
354 item_bin_bbox(ib, &bbox);
355 item_bin_write_to_sink(ib, out, NULL);
356 g_hash_table_insert(hash, g_strdup(tile2), (void *)15);
357 #if 0
358 item_bin_init(ib, type_border_country);
359 item_bin_bbox(ib, &bbox);
360 item_bin_add_attr_string(ib, attr_debug, tile2);
361 item_bin_write_to_sink(ib, out, NULL);
362 #endif
363 co.x=(bbox.l.x+bbox.h.x)/2;
364 co.y=(bbox.l.y+bbox.h.y)/2;
365 //item_bin_write_debug_point_to_sink(out, &co, "%s 15",tile2);
366
367 }
368
369 /* ba */
370 /* dc */
371
372 static void
373 tile_collector_add_siblings(char *tile, void *edgesp, struct coastline_tile_data *data)
374 {
375 int len=strlen(tile);
376 char t=tile[len-1];
377 struct item_bin_sink *out=data->sink->priv_data[1];
378 int edges=(int)edgesp;
379 int debug=0;
380
381 if (len != data->level)
382 return;
383 #if 0
384 if (!strncmp(tile,"bcacccaadbdcd",10))
385 debug=1;
386 #endif
387 if (debug)
388 fprintf(stderr,"%s (%c) has %d edges active\n",tile,t,edges);
389 if (t == 'a' && (edges & 1))
390 ocean_tile(data->tile_edges, tile, 'b', out);
391 if (t == 'a' && (edges & 8))
392 ocean_tile(data->tile_edges, tile, 'c', out);
393 if (t == 'b' && (edges & 4))
394 ocean_tile(data->tile_edges, tile, 'a', out);
395 if (t == 'b' && (edges & 8))
396 ocean_tile(data->tile_edges, tile, 'd', out);
397 if (t == 'c' && (edges & 1))
398 ocean_tile(data->tile_edges, tile, 'd', out);
399 if (t == 'c' && (edges & 2))
400 ocean_tile(data->tile_edges, tile, 'a', out);
401 if (t == 'd' && (edges & 4))
402 ocean_tile(data->tile_edges, tile, 'c', out);
403 if (t == 'd' && (edges & 2))
404 ocean_tile(data->tile_edges, tile, 'b', out);
405 }
406
407 static int
408 tile_sibling_edges(GHashTable *hash, char *tile, char c)
409 {
410 int len=strlen(tile);
411 int ret;
412 char *tile2=g_alloca(sizeof(char)*(len+1));
413 void *data;
414 strcpy(tile2, tile);
415 tile2[len-1]=c;
416 if (!g_hash_table_lookup_extended(hash, tile2, NULL, &data))
417 ret=15;
418 else
419 ret=(int)data;
420 //fprintf(stderr,"checking '%s' with %d edges active\n",tile2,ret);
421
422 return ret;
423 }
424
425 static void
426 ocean_tile2(struct rect *r, int dx, int dy, int wf, int hf, struct item_bin_sink *out)
427 {
428 struct item_bin *ib;
429 int w=r->h.x-r->l.x;
430 int h=r->h.y-r->l.y;
431 char tile2[32];
432 struct rect bbox;
433 struct coord co;
434 bbox.l.x=r->l.x+dx*w;
435 bbox.l.y=r->l.y+dy*h;
436 bbox.h.x=bbox.l.x+w*wf;
437 bbox.h.y=bbox.l.y+h*hf;
438 //fprintf(stderr,"0x%x,0x%x-0x%x,0x%x -> 0x%x,0x%x-0x%x,0x%x\n",r->l.x,r->l.y,r->h.x,r->h.y,bbox.l.x,bbox.l.y,bbox.h.x,bbox.h.y);
439 ib=init_item(type_poly_water_tiled);
440 item_bin_bbox(ib, &bbox);
441 item_bin_write_to_sink(ib, out, NULL);
442 #if 0
443 item_bin_init(ib, type_border_country);
444 item_bin_bbox(ib, &bbox);
445 item_bin_add_attr_string(ib, attr_debug, tile2);
446 item_bin_write_to_sink(ib, out, NULL);
447 #endif
448 tile(&bbox, NULL, tile2, 32, 0, NULL);
449 co.x=(bbox.l.x+bbox.h.x)/2;
450 co.y=(bbox.l.y+bbox.h.y)/2;
451 //item_bin_write_debug_point_to_sink(out, &co, "%s 15",tile2);
452 }
453
454 static void
455 tile_collector_add_siblings2(char *tile, void *edgesp, struct coastline_tile_data *data)
456 {
457 int edges=(int)edgesp;
458 int pedges=0;
459 int debug=0;
460 int len=strlen(tile);
461 char *tile2=g_alloca(sizeof(char)*(len+1));
462 char t=tile[len-1];
463 strcpy(tile2, tile);
464 tile2[len-1]='\0';
465 #if 0
466 if (!strncmp(tile,"bcacccaadbdcd",10))
467 debug=1;
468 #endif
469 if (debug)
470 fprintf(stderr,"len of %s %d vs %d\n",tile,len,data->level);
471 if (len != data->level)
472 return;
473
474
475 if (debug)
476 fprintf(stderr,"checking siblings of '%s' with %d edges active\n",tile,edges);
477 if (t == 'b' && (edges & 1) && (tile_sibling_edges(data->tile_edges, tile, 'd') & 1))
478 pedges|=1;
479 if (t == 'd' && (edges & 2) && (tile_sibling_edges(data->tile_edges, tile, 'b') & 1))
480 pedges|=1;
481 if (t == 'a' && (edges & 2) && (tile_sibling_edges(data->tile_edges, tile, 'b') & 2))
482 pedges|=2;
483 if (t == 'b' && (edges & 2) && (tile_sibling_edges(data->tile_edges, tile, 'a') & 2))
484 pedges|=2;
485 if (t == 'a' && (edges & 4) && (tile_sibling_edges(data->tile_edges, tile, 'c') & 4))
486 pedges|=4;
487 if (t == 'c' && (edges & 4) && (tile_sibling_edges(data->tile_edges, tile, 'a') & 4))
488 pedges|=4;
489 if (t == 'd' && (edges & 8) && (tile_sibling_edges(data->tile_edges, tile, 'c') & 8))
490 pedges|=8;
491 if (t == 'c' && (edges & 8) && (tile_sibling_edges(data->tile_edges, tile, 'd') & 8))
492 pedges|=8;
493 if (debug)
494 fprintf(stderr,"result '%s' %d old %d\n",tile2,pedges,(int)g_hash_table_lookup(data->tile_edges, tile2));
495 g_hash_table_insert(data->tile_edges, g_strdup(tile2), (void *)((int)g_hash_table_lookup(data->tile_edges, tile2)|pedges));
496 }
497
498 static int
499 tile_collector_finish(struct item_bin_sink_func *tile_collector)
500 {
501 struct coastline_tile_data data;
502 int i;
503 GHashTable *hash;
504 data.sink=tile_collector;
505 data.tile_edges=g_hash_table_new_full(g_str_hash, g_str_equal, g_free, NULL);
506 hash=tile_collector->priv_data[0];
507 fprintf(stderr,"tile_collector_finish\n");
508 g_hash_table_foreach(hash, (GHFunc) tile_collector_process_tile, &data);
509 fprintf(stderr,"tile_collector_finish foreach done\n");
510 g_hash_table_destroy(hash);
511 fprintf(stderr,"tile_collector_finish destroy done\n");
512 for (i = 14 ; i > 0 ; i--) {
513 fprintf(stderr,"Level=%d\n",i);
514 data.level=i;
515 g_hash_table_foreach(data.tile_edges, (GHFunc) tile_collector_add_siblings, &data);
516 fprintf(stderr,"*");
517 g_hash_table_foreach(data.tile_edges, (GHFunc) tile_collector_add_siblings, &data);
518 fprintf(stderr,"*");
519 g_hash_table_foreach(data.tile_edges, (GHFunc) tile_collector_add_siblings, &data);
520 fprintf(stderr,"*");
521 g_hash_table_foreach(data.tile_edges, (GHFunc) tile_collector_add_siblings, &data);
522 fprintf(stderr,"*");
523 g_hash_table_foreach(data.tile_edges, (GHFunc) tile_collector_add_siblings2, &data);
524 fprintf(stderr,"*\n");
525 g_hash_table_foreach(data.tile_edges, (GHFunc) tile_collector_add_siblings2, &data);
526 fprintf(stderr,"*\n");
527 g_hash_table_foreach(data.tile_edges, (GHFunc) tile_collector_add_siblings2, &data);
528 fprintf(stderr,"*\n");
529 g_hash_table_foreach(data.tile_edges, (GHFunc) tile_collector_add_siblings2, &data);
530 fprintf(stderr,"*\n");
531 }
532 #if 0
533 data.level=13;
534 g_hash_table_foreach(data.tile_edges, tile_collector_add_siblings, &data);
535 g_hash_table_foreach(data.tile_edges, tile_collector_add_siblings, &data);
536 g_hash_table_foreach(data.tile_edges, tile_collector_add_siblings2, &data);
537 data.level=12;
538 g_hash_table_foreach(data.tile_edges, tile_collector_add_siblings, &data);
539 g_hash_table_foreach(data.tile_edges, tile_collector_add_siblings, &data);
540 #endif
541 item_bin_sink_func_destroy(tile_collector);
542 fprintf(stderr,"tile_collector_finish done\n");
543 return 0;
544 }
545
546
547 static int
548 coastline_processor_process(struct item_bin_sink_func *func, struct item_bin *ib, struct tile_data *tile_data)
549 {
550 #if 0
551 int i;
552 struct coord *c=(struct coord *)(ib+1);
553 for (i = 0 ; i < 19 ; i++) {
554 c[i]=c[i+420];
555 }
556 ib->clen=(i-1)*2;
557 #endif
558 item_bin_write_clipped(ib, func->priv_data[0], func->priv_data[1]);
559 return 0;
560 }
561
562 static struct item_bin_sink_func *
563 coastline_processor_new(struct item_bin_sink *out)
564 {
565 struct item_bin_sink_func *coastline_processor=item_bin_sink_func_new(coastline_processor_process);
566 struct item_bin_sink *tiles=item_bin_sink_new();
567 struct item_bin_sink_func *tile_collector=tile_collector_new(out);
568 struct tile_parameter *param=g_new0(struct tile_parameter, 1);
569
570 fprintf(stderr,"new:out=%p\n",out);
571 param->min=14;
572 param->max=14;
573 param->overlap=0;
574
575 item_bin_sink_add_func(tiles, tile_collector);
576 coastline_processor->priv_data[0]=param;
577 coastline_processor->priv_data[1]=tiles;
578 coastline_processor->priv_data[2]=tile_collector;
579 return coastline_processor;
580 }
581
582 static void
583 coastline_processor_finish(struct item_bin_sink_func *coastline_processor)
584 {
585 struct tile_parameter *param=coastline_processor->priv_data[0];
586 struct item_bin_sink *tiles=coastline_processor->priv_data[1];
587 struct item_bin_sink_func *tile_collector=coastline_processor->priv_data[2];
588 g_free(param);
589 tile_collector_finish(tile_collector);
590 item_bin_sink_destroy(tiles);
591 item_bin_sink_func_destroy(coastline_processor);
592 }
593
594 void
595 process_coastlines(FILE *in, FILE *out)
596 {
597 struct item_bin_sink *reader=file_reader_new(in,1000000,0);
598 struct item_bin_sink_func *file_writer=file_writer_new(out);
599 struct item_bin_sink *result=item_bin_sink_new();
600 struct item_bin_sink_func *coastline_processor=coastline_processor_new(result);
601 item_bin_sink_add_func(reader, coastline_processor);
602 item_bin_sink_add_func(result, file_writer);
603 file_reader_finish(reader);
604 coastline_processor_finish(coastline_processor);
605 file_writer_finish(file_writer);
606 item_bin_sink_destroy(result);
607 }

   
Visit the ZANavi Wiki