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

Diff of /navit/navit/maptool/geom.c

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

Revision 56 Revision 57
… …
210int 210int
211geom_poly_closest_point(struct coord *pl, int count, struct coord *p, struct coord *c) 211geom_poly_closest_point(struct coord *pl, int count, struct coord *p, struct coord *c)
212{ 212{
213 int i,vertex=0; 213 int i,vertex=0;
214 long long x, y, xi, xj, yi, yj, u, d, dmin=0; 214 long long x, y, xi, xj, yi, yj, u, d, dmin=0;
215
215 if(count<2) { 216 if (count<2)
217 {
216 c->x=pl->x; 218 c->x=pl->x;
217 c->y=pl->y; 219 c->y=pl->y;
218 return 0; 220 return 0;
219 } 221 }
222
220 for(i=0;i<count-1;i++) { 223 for (i=0;i<count-1;i++)
224 {
221 xi=pl[i].x; 225 xi=pl[i].x;
222 yi=pl[i].y; 226 yi=pl[i].y;
223 xj=pl[i+1].x; 227 xj=pl[i+1].x;
224 yj=pl[i+1].y; 228 yj=pl[i+1].y;
225 u=(xj-xi)*(xj-xi)+(yj-yi)*(yj-yi); 229 u=(xj-xi)*(xj-xi)+(yj-yi)*(yj-yi);
230
226 if(u!=0) { 231 if(u!=0)
232 {
227 u=((p->x-xi)*(xj-xi)+(p->y-yi)*(yj-yi))*1000/u; 233 u=((p->x-xi)*(xj-xi)+(p->y-yi)*(yj-yi))*1000/u;
228 } 234 }
235
229 if(u<0) 236 if(u<0)
237 {
230 u=0; 238 u=0;
239 }
231 else if (u>1000) 240 else if (u>1000)
241 {
232 u=1000; 242 u=1000;
243 }
244
233 x=xi+u*(xj-xi)/1000; 245 x=xi+u*(xj-xi)/1000;
234 y=yi+u*(yj-yi)/1000; 246 y=yi+u*(yj-yi)/1000;
235 d=(p->x-x)*(p->x-x)+(p->y-y)*(p->y-y); 247 d=(p->x-x)*(p->x-x)+(p->y-y)*(p->y-y);
248
236 if(i==0 || d<dmin) { 249 if (i==0 || d<dmin)
250 {
237 dmin=d; 251 dmin=d;
238 c->x=x; 252 c->x=x;
239 c->y=y; 253 c->y=y;
240 vertex=i; 254 vertex=i;
241 } 255 }
242 } 256 }
257
243 return vertex; 258 return vertex;
244} 259}
245 260
246/** 261/**
247 * Check if point is inside polygon 262 * Check if point is inside polygon
… …
281 struct geom_poly_segment *ret; 296 struct geom_poly_segment *ret;
282 struct coord *pos; 297 struct coord *pos;
283 298
284 if (!second) 299 if (!second)
285 return NULL; ret=g_new(struct geom_poly_segment, 1); 300 return NULL; ret=g_new(struct geom_poly_segment, 1);
301
286 ret->type = second->type; 302 ret->type = second->type;
287 count = (second->last - second->first) + 1; 303 count = (second->last - second->first) + 1;
288 if (first) 304 if (first)
289 count += (first->last - first->first); 305 count += (first->last - first->first);
306
290 if (third) 307 if (third)
291 count += (third->last - third->first); 308 count += (third->last - third->first);
309
292#if 0 310#if 0
293 fprintf(stderr,"count=%d first=%p second=%p third=%p\n",count,first,second,third); 311 fprintf(stderr,"count=%d first=%p second=%p third=%p\n",count,first,second,third);
294 if (first) 312 if (first)
295 fprintf(stderr,"first:0x%x,0x%x-0x%x,0x%x (%d)\n",first->first->x,first->first->y,first->last->x,first->last->y, first->last-first->first+1); 313 fprintf(stderr,"first:0x%x,0x%x-0x%x,0x%x (%d)\n",first->first->x,first->first->y,first->last->x,first->last->y, first->last-first->first+1);
296 if (second) 314 if (second)
… …
298 if (third) 316 if (third)
299 fprintf(stderr,"third:0x%x,0x%x-0x%x,0x%x (%d)\n",third->first->x,third->first->y,third->last->x,third->last->y, third->last-third->first+1); 317 fprintf(stderr,"third:0x%x,0x%x-0x%x,0x%x (%d)\n",third->first->x,third->first->y,third->last->x,third->last->y, third->last-third->first+1);
300#endif 318#endif
301 ret->first=g_new(struct coord, count); 319 ret->first=g_new(struct coord, count);
302 pos = ret->first; 320 pos = ret->first;
321
303 if (first) 322 if (first)
304 { 323 {
305 count = (first->last - first->first) + 1; 324 count = (first->last - first->first) + 1;
306 geom_coord_copy(first->first, pos, count, coord_is_equal(*first->first, *second->first)); 325 geom_coord_copy(first->first, pos, count, coord_is_equal(*first->first, *second->first));
307 pos += count - 1; 326 pos += count - 1;
308 } 327 }
328
309 count = (second->last - second->first) + 1; 329 count = (second->last - second->first) + 1;
310 geom_coord_copy(second->first, pos, count, 0); 330 geom_coord_copy(second->first, pos, count, 0);
311 pos += count; 331 pos += count;
332
312 if (third) 333 if (third)
313 { 334 {
314 pos--; 335 pos--;
315 count = (third->last - third->first) + 1; 336 count = (third->last - third->first) + 1;
316 geom_coord_copy(third->first, pos, count, coord_is_equal(*third->last, *second->last)); 337 geom_coord_copy(third->first, pos, count, coord_is_equal(*third->last, *second->last));
317 pos += count; 338 pos += count;
318 } 339 }
340
319 ret->last = pos - 1; 341 ret->last = pos - 1;
320#if 0 342#if 0
321 fprintf(stderr,"result:0x%x,0x%x-0x%x,0x%x (%d)\n",ret->first->x,ret->first->y,ret->last->x,ret->last->y, ret->last-ret->first+1); 343 fprintf(stderr,"result:0x%x,0x%x-0x%x,0x%x (%d)\n",ret->first->x,ret->first->y,ret->last->x,ret->last->y, ret->last-ret->first+1);
322#endif 344#endif
323 list = g_list_prepend(list, ret); 345 list = g_list_prepend(list, ret);
324#if 0 346#if 0
325 fprintf(stderr,"List=%p\n",list); 347 fprintf(stderr,"List=%p\n",list);
326#endif 348#endif
349
327 return list; 350 return list;
328} 351}
329 352
330void geom_poly_segment_destroy(struct geom_poly_segment *seg) 353void geom_poly_segment_destroy(struct geom_poly_segment *seg)
331{ 354{
… …
347int geom_poly_segment_compatible(struct geom_poly_segment *s1, struct geom_poly_segment *s2, int dir) 370int geom_poly_segment_compatible(struct geom_poly_segment *s1, struct geom_poly_segment *s2, int dir)
348{ 371{
349 int same = 0, opposite = 0; 372 int same = 0, opposite = 0;
350 if (s1->type == geom_poly_segment_type_none || s2->type == geom_poly_segment_type_none) 373 if (s1->type == geom_poly_segment_type_none || s2->type == geom_poly_segment_type_none)
351 return 0; 374 return 0;
375
352 if (s1->type == s2->type) 376 if (s1->type == s2->type)
353 { 377 {
354 same = 1; 378 same = 1;
355 if (s1->type == geom_poly_segment_type_way_inner || s1->type == geom_poly_segment_type_way_outer) 379 if (s1->type == geom_poly_segment_type_way_inner || s1->type == geom_poly_segment_type_way_outer)
356 { 380 {
357 opposite = 1; 381 opposite = 1;
358 } 382 }
359 } 383 }
384
360 if (s1->type == geom_poly_segment_type_way_left_side && s2->type == geom_poly_segment_type_way_right_side) 385 if (s1->type == geom_poly_segment_type_way_left_side && s2->type == geom_poly_segment_type_way_right_side)
361 opposite = 1; 386 opposite = 1;
387
362 if (s1->type == geom_poly_segment_type_way_right_side && s2->type == geom_poly_segment_type_way_left_side) 388 if (s1->type == geom_poly_segment_type_way_right_side && s2->type == geom_poly_segment_type_way_left_side)
363 opposite = 1; 389 opposite = 1;
390
364 if (s1->type == geom_poly_segment_type_way_unknown || s2->type == geom_poly_segment_type_way_unknown) 391 if (s1->type == geom_poly_segment_type_way_unknown || s2->type == geom_poly_segment_type_way_unknown)
365 { 392 {
366 same = 1; 393 same = 1;
367 opposite = 1; 394 opposite = 1;
368 } 395 }
396
369 if (dir < 0) 397 if (dir < 0)
370 { 398 {
371 if ((opposite && coord_is_equal(*s1->first, *s2->first)) || (same && coord_is_equal(*s1->first, *s2->last))) 399 if ((opposite && coord_is_equal(*s1->first, *s2->first)) || (same && coord_is_equal(*s1->first, *s2->last)))
372 return 1; 400 return 1;
401
373 } 402 }
374 else 403 else
375 { 404 {
376 if ((opposite && coord_is_equal(*s1->last, *s2->last)) || (same && coord_is_equal(*s1->last, *s2->first))) 405 if ((opposite && coord_is_equal(*s1->last, *s2->last)) || (same && coord_is_equal(*s1->last, *s2->first)))
377 return 1; 406 return 1;
407
378 } 408 }
409
379 return 0; 410 return 0;
380} 411}
381 412
382GList * 413GList *
383geom_poly_segments_sort(GList *in, enum geom_poly_segment_type type) 414geom_poly_segments_sort(GList *in, enum geom_poly_segment_type type)
… …
386 while (in) 417 while (in)
387 { 418 {
388 struct geom_poly_segment *seg = in->data; 419 struct geom_poly_segment *seg = in->data;
389 GList *tmp = ret; 420 GList *tmp = ret;
390 struct geom_poly_segment *merge_first = NULL, *merge_last = NULL; 421 struct geom_poly_segment *merge_first = NULL, *merge_last = NULL;
422
391 while (tmp) 423 while (tmp)
392 { 424 {
393 struct geom_poly_segment *cseg = tmp->data; 425 struct geom_poly_segment *cseg = tmp->data;
426
394 if (geom_poly_segment_compatible(seg, cseg, -1)) 427 if (geom_poly_segment_compatible(seg, cseg, -1))
395 merge_first = cseg; 428 merge_first = cseg;
429
396 if (geom_poly_segment_compatible(seg, cseg, 1)) 430 if (geom_poly_segment_compatible(seg, cseg, 1))
397 merge_last = cseg; 431 merge_last = cseg;
432
398 tmp = g_list_next(tmp); 433 tmp = g_list_next(tmp);
399 } 434 }
435
400 if (merge_first == merge_last) 436 if (merge_first == merge_last)
401 { 437 {
402 merge_last = NULL; 438 merge_last = NULL;
403 } 439 }
404 ret = geom_poly_segments_insert(ret, merge_first, seg, merge_last); 440 ret = geom_poly_segments_insert(ret, merge_first, seg, merge_last);
… …
469 if (closed_matches & 1) 505 if (closed_matches & 1)
470 return 1; 506 return 1;
471 else 507 else
472 return 0; 508 return 0;
473 } 509 }
510
474 if (open_matches) 511 if (open_matches)
475 { 512 {
476 if (open_matches & 1) 513 if (open_matches & 1)
477 return -1; 514 return -1;
478 else 515 else
… …
486{ 523{
487 // int is_closed_poly = 0; 524 // int is_closed_poly = 0;
488 525
489 int i; 526 int i;
490 int count = ib->clen / 2; 527 int count = ib->clen / 2;
528
491 if (count <= 1) 529 if (count <= 1)
492 { 530 {
493 return 0; 531 return 0;
494 } 532 }
495 533
496 struct coord *c = (struct coord *) (ib + 1); 534 struct coord *c = (struct coord *) (ib + 1);
… …
543} 581}
544 582
545static int clipcode(struct coord *p, struct rect *r) 583static int clipcode(struct coord *p, struct rect *r)
546{ 584{
547 int code = 0; 585 int code = 0;
586
548 if (p->x < r->l.x) 587 if (p->x < r->l.x)
549 code = 1; 588 code = 1;
550 if (p->x > r->h.x) 589 if (p->x > r->h.x)
551 code = 2; 590 code = 2;
552 if (p->y < r->l.y) 591 if (p->y < r->l.y)
553 code |= 4; 592 code |= 4;
554 if (p->y > r->h.y) 593 if (p->y > r->h.y)
555 code |= 8; 594 code |= 8;
595
556 return code; 596 return code;
557} 597}
558 598
559static int clip_line_code(struct coord *p1, struct coord *p2, struct rect *r) 599static int clip_line_code(struct coord *p1, struct coord *p2, struct rect *r)
560{ 600{
561 int code1, code2, ret = 1; 601 int code1, code2, ret = 1;
562 long long dx, dy; 602 long long dx, dy;
563 code1 = clipcode(p1, r); 603 code1 = clipcode(p1, r);
604
564 if (code1) 605 if (code1)
565 ret |= 2; 606 ret |= 2;
607
566 code2 = clipcode(p2, r); 608 code2 = clipcode(p2, r);
609
567 if (code2) 610 if (code2)
568 ret |= 4; 611 ret |= 4;
612
569 dx = p2->x - p1->x; 613 dx = p2->x - p1->x;
570 dy = p2->y - p1->y; 614 dy = p2->y - p1->y;
615
571 while (code1 || code2) 616 while (code1 || code2)
572 { 617 {
573 if (code1 & code2) 618 if (code1 & code2)
574 return 0; 619 return 0;
620
575 if (code1 & 1) 621 if (code1 & 1)
576 { 622 {
577 p1->y += (r->l.x - p1->x) * dy / dx; 623 p1->y += (r->l.x - p1->x) * dy / dx;
578 p1->x = r->l.x; 624 p1->x = r->l.x;
579 } 625 }
… …
590 else if (code1 & 8) 636 else if (code1 & 8)
591 { 637 {
592 p1->x += (r->h.y - p1->y) * dx / dy; 638 p1->x += (r->h.y - p1->y) * dx / dy;
593 p1->y = r->h.y; 639 p1->y = r->h.y;
594 } 640 }
641
595 code1 = clipcode(p1, r); 642 code1 = clipcode(p1, r);
643
596 if (code1 & code2) 644 if (code1 & code2)
597 return 0; 645 return 0;
646
598 if (code2 & 1) 647 if (code2 & 1)
599 { 648 {
600 p2->y += (r->l.x - p2->x) * dy / dx; 649 p2->y += (r->l.x - p2->x) * dy / dx;
601 p2->x = r->l.x; 650 p2->x = r->l.x;
602 } 651 }
… …
613 else if (code2 & 8) 662 else if (code2 & 8)
614 { 663 {
615 p2->x += (r->h.y - p2->y) * dx / dy; 664 p2->x += (r->h.y - p2->y) * dx / dy;
616 p2->y = r->h.y; 665 p2->y = r->h.y;
617 } 666 }
667
618 code2 = clipcode(p2, r); 668 code2 = clipcode(p2, r);
669
619 } 670 }
671
620 if (p1->x == p2->x && p1->y == p2->y) 672 if (p1->x == p2->x && p1->y == p2->y)
621 ret = 0; 673 ret = 0;
674
622 return ret; 675 return ret;
623} 676}
624 677
625void clip_line(struct item_bin *ib, struct rect *r, struct tile_parameter *param, struct item_bin_sink *out) 678void clip_line(struct item_bin *ib, struct rect *r, struct tile_parameter *param, struct item_bin_sink *out)
626{ 679{
… …
629 struct coord *pa = (struct coord *) (ib + 1); 682 struct coord *pa = (struct coord *) (ib + 1);
630 int count = ib->clen / 2; 683 int count = ib->clen / 2;
631 struct coord p1, p2; 684 struct coord p1, p2;
632 int i, code; 685 int i, code;
633 item_bin_init(ib_new, ib->type); 686 item_bin_init(ib_new, ib->type);
687
634 for (i = 0; i < count; i++) 688 for (i = 0; i < count; i++)
635 { 689 {
636 if (i) 690 if (i)
637 { 691 {
638 p1.x = pa[i - 1].x; 692 p1.x = pa[i - 1].x;
… …
644#if 1 698#if 1
645 if (((code == 1 || code == 5) && ib_new->clen == 0) || (code & 2)) 699 if (((code == 1 || code == 5) && ib_new->clen == 0) || (code & 2))
646 { 700 {
647 item_bin_add_coord(ib_new, &p1, 1); 701 item_bin_add_coord(ib_new, &p1, 1);
648 } 702 }
703
649 if (code) 704 if (code)
650 { 705 {
651 item_bin_add_coord(ib_new, &p2, 1); 706 item_bin_add_coord(ib_new, &p2, 1);
652 } 707 }
708
653 if (i == count - 1 || (code & 4)) 709 if (i == count - 1 || (code & 4))
654 { 710 {
655 if (ib_new->clen) 711 if (ib_new->clen)
656 item_bin_write_clipped(ib_new, param, out); 712 item_bin_write_clipped(ib_new, param, out);
713
657 item_bin_init(ib_new, ib->type); 714 item_bin_init(ib_new, ib->type);
658 } 715 }
659#else 716#else
660 if (code) 717 if (code)
661 { 718 {
… …
765 } 822 }
766 if (ib_in->clen) 823 if (ib_in->clen)
767 item_bin_write_clipped(ib_in, param, out); 824 item_bin_write_clipped(ib_in, param, out);
768} 825}
769 826
827
Legend:
Removed from v.56  
changed lines
  Added in v.57
   
Visit the ZANavi Wiki