git.maemo.org Git - navit-package/blob - navit/maptool/geom.c

   1 #include <string.h>
   2 #include "maptool.h"
   3
   4 void
   5 geom_coord_copy(struct coord *from, struct coord *to, int count, int reverse)
   6 {
   7         int i;
   8         if (!reverse) {
   9                 memcpy(to, from, count*sizeof(struct coord));
  10                 return;
  11         }
  12         from+=count;
  13         for (i = 0 ; i < count ; i++)
  14                 *to++=*--from;
  15 }
  16
  17 void
  18 geom_coord_revert(struct coord *c, int count)
  19 {
  20         struct coord tmp;
  21         int i;
  22
  23         for (i = 0 ; i < count/2 ; i++) {
  24                 tmp=c[i];
  25                 c[i]=c[count-1-i];
  26                 c[count-1-i]=tmp;
  27         }
  28 }
  29
  30
  31 long long
  32 geom_poly_area(struct coord *c, int count)
  33 {
  34         long long area=0;
  35         int i,j=0;
  36 #if 0
  37         fprintf(stderr,"count=%d\n",count);
  38 #endif
  39         for (i=0; i<count; i++) {
  40                 if (++j == count)
  41                         j=0;
  42 #if 0
  43                 fprintf(stderr,"(%d+%d)*(%d-%d)=%d*%d=%Ld\n",c[i].x,c[j].x,c[i].y,c[j].y,c[i].x+c[j].x,c[i].y-c[j].y,(long long)(c[i].x+c[j].x)*(c[i].y-c[j].y));
  44 #endif
  45                 area+=(long long)(c[i].x+c[j].x)*(c[i].y-c[j].y);
  46 #if 0
  47                 fprintf(stderr,"area=%Ld\n",area);
  48 #endif
  49         }
  50         return area/2;
  51 }
  52
  53 GList *
  54 geom_poly_segments_insert(GList *list, struct geom_poly_segment *first, struct geom_poly_segment *second, struct geom_poly_segment *third)
  55 {
  56         int count;
  57         struct geom_poly_segment *ret;
  58         struct coord *pos;
  59
  60         if (!second)
  61                 return NULL;
  62         ret=g_new(struct geom_poly_segment, 1);
  63         ret->type=second->type;
  64         count=(second->last-second->first)+1;
  65         if (first)
  66                 count+=(first->last-first->first);
  67         if (third)
  68                 count+=(third->last-third->first);
  69 #if 0
  70         fprintf(stderr,"count=%d first=%p second=%p third=%p\n",count,first,second,third);
  71         if (first)
  72                 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);
  73         if (second)
  74                 fprintf(stderr,"second:0x%x,0x%x-0x%x,0x%x (%d)\n",second->first->x,second->first->y,second->last->x,second->last->y, second->last-second->first+1);
  75         if (third)
  76                 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);
  77 #endif
  78         ret->first=g_new(struct coord, count);
  79         pos=ret->first;
  80         if (first) {
  81                 count=(first->last-first->first)+1;
  82                 geom_coord_copy(first->first, pos, count, coord_is_equal(*first->first, *second->first));
  83                 pos+=count-1;
  84         }
  85         count=(second->last-second->first)+1;
  86         geom_coord_copy(second->first, pos, count, 0);
  87         pos+=count;
  88         if (third) {
  89                 pos--;
  90                 count=(third->last-third->first)+1;
  91                 geom_coord_copy(third->first, pos, count, coord_is_equal(*third->last, *second->last));
  92                 pos+=count;
  93         }
  94         ret->last=pos-1;
  95 #if 0
  96         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);
  97 #endif
  98         list=g_list_prepend(list, ret);
  99 #if 0
 100         fprintf(stderr,"List=%p\n",list);
 101 #endif
 102         return list;
 103 }
 104
 105 void
 106 geom_poly_segment_destroy(struct geom_poly_segment *seg)
 107 {
 108         g_free(seg->first);
 109         g_free(seg);
 110 }
 111
 112 GList *
 113 geom_poly_segments_remove(GList *list, struct geom_poly_segment *seg)
 114 {
 115         if (seg) {
 116                 list=g_list_remove(list, seg);
 117                 geom_poly_segment_destroy(seg);
 118         }
 119         return list;
 120 }
 121
 122 int
 123 geom_poly_segment_compatible(struct geom_poly_segment *s1, struct geom_poly_segment *s2, int dir)
 124 {
 125         int same=0,opposite=0;
 126         if (s1->type == geom_poly_segment_type_none || s2->type == geom_poly_segment_type_none)
 127                 return 0;
 128         if (s1->type == s2->type)
 129                 same=1;
 130         if (s1->type == geom_poly_segment_type_way_inner && s2->type == geom_poly_segment_type_way_outer)
 131                 opposite=1;
 132         if (s1->type == geom_poly_segment_type_way_outer && s2->type == geom_poly_segment_type_way_inner)
 133                 opposite=1;
 134         if (s1->type == geom_poly_segment_type_way_left_side && s2->type == geom_poly_segment_type_way_right_side)
 135                 opposite=1;
 136         if (s1->type == geom_poly_segment_type_way_right_side && s2->type == geom_poly_segment_type_way_left_side)
 137                 opposite=1;
 138         if (s1->type == geom_poly_segment_type_way_unknown || s2->type == geom_poly_segment_type_way_unknown) {
 139                 same=1;
 140                 opposite=1;
 141         }
 142         if (dir < 0) {
 143                 if ((opposite && coord_is_equal(*s1->first, *s2->first)) || (same && coord_is_equal(*s1->first, *s2->last)))
 144                         return 1;
 145         } else {
 146                 if ((opposite && coord_is_equal(*s1->last, *s2->last)) || (same && coord_is_equal(*s1->last, *s2->first)))
 147                         return 1;
 148         }
 149         return 0;
 150 }
 151
 152
 153 GList *
 154 geom_poly_segments_sort(GList *in, enum geom_poly_segment_type type)
 155 {
 156         GList *ret=NULL;
 157         while (in) {
 158                 struct geom_poly_segment *seg=in->data;
 159                 GList *tmp=ret;
 160                 struct geom_poly_segment *merge_first=NULL,*merge_last=NULL;
 161                 while (tmp) {
 162                         struct geom_poly_segment *cseg=tmp->data;
 163                         if (geom_poly_segment_compatible(seg, cseg, -1))
 164                                 merge_first=cseg;
 165                         if (geom_poly_segment_compatible(seg, cseg, 1))
 166                                 merge_last=cseg;
 167                         tmp=g_list_next(tmp);
 168                 }
 169                 if (merge_first == merge_last)
 170                         merge_last=NULL;
 171                 ret=geom_poly_segments_insert(ret, merge_first, seg, merge_last);
 172                 ret=geom_poly_segments_remove(ret, merge_first);
 173                 ret=geom_poly_segments_remove(ret, merge_last);
 174                 in=g_list_next(in);
 175         }
 176         in=ret;
 177         while (in) {
 178                 struct geom_poly_segment *seg=in->data;
 179                 if (coord_is_equal(*seg->first, *seg->last)) {
 180                         long long area=geom_poly_area(seg->first,seg->last-seg->first+1);
 181                         if (type == geom_poly_segment_type_way_right_side && seg->type == geom_poly_segment_type_way_right_side) {
 182                                 seg->type=area > 0 ? geom_poly_segment_type_way_outer : geom_poly_segment_type_way_inner;
 183                         }
 184                 }
 185                 in=g_list_next(in);
 186         }
 187         return ret;
 188 }
 189
 190 struct geom_poly_segment *
 191 item_bin_to_poly_segment(struct item_bin *ib, int type)
 192 {
 193         struct geom_poly_segment *ret=g_new(struct geom_poly_segment, 1);
 194         int count=ib->clen*sizeof(int)/sizeof(struct coord);
 195         ret->type=type;
 196         ret->first=g_new(struct coord, count);
 197         ret->last=ret->first+count-1;
 198         geom_coord_copy((struct coord *)(ib+1), ret->first, count, 0);
 199         return ret;
 200 }
 201
 202
 203 static int
 204 clipcode(struct coord *p, struct rect *r)
 205 {
 206         int code=0;
 207         if (p->x < r->l.x)
 208                 code=1;
 209         if (p->x > r->h.x)
 210                 code=2;
 211         if (p->y < r->l.y)
 212                 code |=4;
 213         if (p->y > r->h.y)
 214                 code |=8;
 215         return code;
 216 }
 217
 218
 219 static int
 220 clip_line_code(struct coord *p1, struct coord *p2, struct rect *r)
 221 {
 222         int code1,code2,ret=1;
 223         long long dx,dy;
 224         code1=clipcode(p1, r);
 225         if (code1)
 226                 ret |= 2;
 227         code2=clipcode(p2, r);
 228         if (code2)
 229                 ret |= 4;
 230         dx=p2->x-p1->x;
 231         dy=p2->y-p1->y;
 232         while (code1 || code2) {
 233                 if (code1 & code2)
 234                         return 0;
 235                 if (code1 & 1) {
 236                         p1->y+=(r->l.x-p1->x)*dy/dx;
 237                         p1->x=r->l.x;
 238                 } else if (code1 & 2) {
 239                         p1->y+=(r->h.x-p1->x)*dy/dx;
 240                         p1->x=r->h.x;
 241                 } else if (code1 & 4) {
 242                         p1->x+=(r->l.y-p1->y)*dx/dy;
 243                         p1->y=r->l.y;
 244                 } else if (code1 & 8) {
 245                         p1->x+=(r->h.y-p1->y)*dx/dy;
 246                         p1->y=r->h.y;
 247                 }
 248                 code1=clipcode(p1, r);
 249                 if (code1 & code2)
 250                         return 0;
 251                 if (code2 & 1) {
 252                         p2->y+=(r->l.x-p2->x)*dy/dx;
 253                         p2->x=r->l.x;
 254                 } else if (code2 & 2) {
 255                         p2->y+=(r->h.x-p2->x)*dy/dx;
 256                         p2->x=r->h.x;
 257                 } else if (code2 & 4) {
 258                         p2->x+=(r->l.y-p2->y)*dx/dy;
 259                         p2->y=r->l.y;
 260                 } else if (code2 & 8) {
 261                         p2->x+=(r->h.y-p2->y)*dx/dy;
 262                         p2->y=r->h.y;
 263                 }
 264                 code2=clipcode(p2, r);
 265         }
 266         if (p1->x == p2->x && p1->y == p2->y)
 267                 ret=0;
 268         return ret;
 269 }
 270
 271 void
 272 clip_line(struct item_bin *ib, struct rect *r, struct tile_parameter *param, struct item_bin_sink *out)
 273 {
 274         char buffer[ib->len*4+32];
 275         struct item_bin *ib_new=(struct item_bin *)buffer;
 276         struct coord *pa=(struct coord *)(ib+1);
 277         int count=ib->clen/2;
 278         struct coord p1,p2;
 279         int i,code;
 280         item_bin_init(ib_new, ib->type);
 281         for (i = 0 ; i < count ; i++) {
 282                 if (i) {
 283                         p1.x=pa[i-1].x;
 284                         p1.y=pa[i-1].y;
 285                         p2.x=pa[i].x;
 286                         p2.y=pa[i].y;
 287                         /* 0 = invisible, 1 = completely visible, 3 = start point clipped, 5 = end point clipped, 7 both points clipped */
 288                         code=clip_line_code(&p1, &p2, r);
 289 #if 1
 290                         if (((code == 1 || code == 5) && ib_new->clen == 0) || (code & 2)) {
 291                                 item_bin_add_coord(ib_new, &p1, 1);
 292                         }
 293                         if (code) {
 294                                 item_bin_add_coord(ib_new, &p2, 1);
 295                         }
 296                         if (i == count-1 || (code & 4)) {
 297                                 if (ib_new->clen)
 298                                         item_bin_write_clipped(ib_new, param, out);
 299                                 item_bin_init(ib_new, ib->type);
 300                         }
 301 #else
 302                         if (code) {
 303                                 item_bin_init(ib_new, ib->type);
 304                                 item_bin_add_coord(ib_new, &p1, 1);
 305                                 item_bin_add_coord(ib_new, &p2, 1);
 306                                 item_bin_write_clipped(ib_new, param, out);
 307                         }
 308 #endif
 309                 }
 310         }
 311 }
 312
 313 static int
 314 is_inside(struct coord *p, struct rect *r, int edge)
 315 {
 316         switch(edge) {
 317         case 0:
 318                 return p->x >= r->l.x;
 319         case 1:
 320                 return p->x <= r->h.x;
 321         case 2:
 322                 return p->y >= r->l.y;
 323         case 3:
 324                 return p->y <= r->h.y;
 325         default:
 326                 return 0;
 327         }
 328 }
 329
 330 static void
 331 poly_intersection(struct coord *p1, struct coord *p2, struct rect *r, int edge, struct coord *ret)
 332 {
 333         int dx=p2->x-p1->x;
 334         int dy=p2->y-p1->y;
 335         switch(edge) {
 336         case 0:
 337                 ret->y=p1->y+(r->l.x-p1->x)*dy/dx;
 338                 ret->x=r->l.x;
 339                 break;
 340         case 1:
 341                 ret->y=p1->y+(r->h.x-p1->x)*dy/dx;
 342                 ret->x=r->h.x;
 343                 break;
 344         case 2:
 345                 ret->x=p1->x+(r->l.y-p1->y)*dx/dy;
 346                 ret->y=r->l.y;
 347                 break;
 348         case 3:
 349                 ret->x=p1->x+(r->h.y-p1->y)*dx/dy;
 350                 ret->y=r->h.y;
 351                 break;
 352         }
 353 }
 354
 355 void
 356 clip_polygon(struct item_bin *ib, struct rect *r, struct tile_parameter *param, struct item_bin_sink *out)
 357 {
 358         int count_in=ib->clen/2;
 359         struct coord *pin,*p,*s,pi;
 360         char buffer1[ib->len*4+ib->clen*7+32];
 361         struct item_bin *ib1=(struct item_bin *)buffer1;
 362         char buffer2[ib->len*4+ib->clen*7+32];
 363         struct item_bin *ib2=(struct item_bin *)buffer2;
 364         struct item_bin *ib_in,*ib_out;
 365         int edge,i;
 366         ib_out=ib1;
 367         ib_in=ib;
 368         for (edge = 0 ; edge < 4 ; edge++) {
 369                 count_in=ib_in->clen/2;
 370                 pin=(struct coord *)(ib_in+1);
 371                 p=pin;
 372                 s=pin+count_in-1;
 373                 item_bin_init(ib_out, ib_in->type);
 374                 for (i = 0 ; i < count_in ; i++) {
 375                         if (is_inside(p, r, edge)) {
 376                                 if (! is_inside(s, r, edge)) {
 377                                         poly_intersection(s,p,r,edge,&pi);
 378                                         item_bin_add_coord(ib_out, &pi, 1);
 379                                 }
 380                                 item_bin_add_coord(ib_out, p, 1);
 381                         } else {
 382                                 if (is_inside(s, r, edge)) {
 383                                         poly_intersection(p,s,r,edge,&pi);
 384                                         item_bin_add_coord(ib_out, &pi, 1);
 385                                 }
 386                         }
 387                         s=p;
 388                         p++;
 389                 }
 390                 if (ib_in == ib1) {
 391                         ib_in=ib2;
 392                         ib_out=ib1;
 393                 } else {
 394                        ib_in=ib1;
 395                         ib_out=ib2;
 396                 }
 397         }
 398         if (ib_in->clen)
 399                 item_bin_write_clipped(ib_in, param, out);
 400 }