/[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 8 Revision 31
1/**
2 * ZANavi, Zoff Android Navigation system.
3 * Copyright (C) 2011-2012 Zoff <zoff@zoff.cc>
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
1/** 20/**
2 * Navit, a modular navigation system. 21 * Navit, a modular navigation system.
3 * Copyright (C) 2005-2011 Navit Team 22 * Copyright (C) 2005-2011 Navit Team
4 * 23 *
5 * This program is free software; you can redistribute it and/or 24 * This program is free software; you can redistribute it and/or
15 * along with this program; if not, write to the 34 * along with this program; if not, write to the
16 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 35 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17 * Boston, MA 02110-1301, USA. 36 * Boston, MA 02110-1301, USA.
18 */ 37 */
19#include <string.h> 38#include <string.h>
39#include <math.h>
20#include "maptool.h" 40#include "maptool.h"
21 41
22void
23geom_coord_copy(struct coord *from, struct coord *to, int count, int reverse) 42void geom_coord_copy(struct coord *from, struct coord *to, int count, int reverse)
24{ 43{
25 int i; 44 int i;
26 if (!reverse) { 45 if (!reverse)
46 {
27 memcpy(to, from, count*sizeof(struct coord)); 47 memcpy(to, from, count * sizeof(struct coord));
28 return; 48 return;
29 } 49 }
30 from+=count; 50 from += count;
31 for (i = 0 ; i < count ; i++) 51 for (i = 0; i < count; i++)
52 {
32 *to++=*--from; 53 *to++ = *--from;
54 }
33} 55}
34 56
35void 57
58/**
59 * Get coordinates of polyline middle point.
60 * @param in *p array of poly vertex coordinates
61 * @param in count count of poly vertexes
62 * @param out *c coordinates of middle point
63 * @returns number of first vertex of segment containing middle point
64 */
65int geom_line_middle(struct coord *p, int count, struct coord *c)
66{
67 double length = 0, half = 0, len = 0;
68 int i;
69
70 if (count == 1)
71 {
72 *c=*p;
73 return 0;
74 }
75
76 for (i=0; i<count-1; i++)
77 {
78 length+=sqrt(sq(p[i].x-p[i+1].x)+sq(p[i].y-p[i+1].y));
79 }
80
81 length /= 2;
82 for (i=0; (i<count-1) && (half<length); i++)
83 {
84 len=sqrt(sq(p[i].x-p[i+1].x)+sq(p[i].y-p[i+1].y));
85 half += len;
86 }
87
88 if (i > 0)
89 {
90 i--;
91 half -= length;
92 if (len)
93 {
94 c->x=(p[i].x*half+p[i+1].x*(len-half))/len;
95 c->y=(p[i].y*half+p[i+1].y*(len-half))/len;
96 }
97 else
98 {
99 *c = p[i];
100 }
101 }
102 else
103 {
104 *c = p[0];
105 }
106
107 return i;
108}
109
36geom_coord_revert(struct coord *c, int count) 110void geom_coord_revert(struct coord *c, int count)
37{ 111{
38 struct coord tmp; 112 struct coord tmp;
39 int i; 113 int i;
40 114
41 for (i = 0 ; i < count/2 ; i++) { 115 for (i = 0; i < count / 2; i++)
116 {
42 tmp=c[i]; 117 tmp = c[i];
43 c[i]=c[count-1-i]; 118 c[i] = c[count - 1 - i];
44 c[count-1-i]=tmp; 119 c[count - 1 - i] = tmp;
45 } 120 }
46} 121}
47 122
48
49long long
50geom_poly_area(struct coord *c, int count) 123long long geom_poly_area(struct coord *c, int count)
51{ 124{
52 long long area=0; 125 long long area = 0;
53 int i,j=0; 126 int i, j = 0;
54#if 0 127#if 0
55 fprintf(stderr,"count=%d\n",count); 128 fprintf(stderr,"count=%d\n",count);
56#endif 129#endif
57 for (i=0; i<count; i++) { 130 for (i = 0; i < count; i++)
131 {
58 if (++j == count) 132 if (++j == count)
59 j=0; 133 j = 0;
60#if 0 134#if 0
61 fprintf(stderr,"(%d+%d)*(%d-%d)=%d*%d="LONGLONG_FMT"\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)); 135 fprintf(stderr,"(%d+%d)*(%d-%d)=%d*%d="LONGLONG_FMT"\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));
62#endif 136#endif
63 area+=(long long)(c[i].x+c[j].x)*(c[i].y-c[j].y); 137 area += (long long) (c[i].x + c[j].x) * (c[i].y - c[j].y);
64#if 0 138#if 0
65 fprintf(stderr,"area="LONGLONG_FMT"\n",area); 139 fprintf(stderr,"area="LONGLONG_FMT"\n",area);
66#endif 140#endif
67 } 141 }
68 return area/2; 142 return area / 2;
69} 143}
144
145/**
146 * Get poly centroid coordinates.
147 * @param in *p array of poly vertex coordinates
148 * @param in count count of poly vertexes
149 * @param out *c coordinates of poly centroid
150 * @returns 1 on success, 0 if poly area is 0
151
152new version taken from mapnik source:
153https://github.com/mapnik/mapnik/blob/master/include/mapnik/geometry.hpp
154function:
155label_position
156
157 */
158int
159geom_poly_centroid(struct coord *p, int count, struct coord *c)
160{
161 int i;
162 long long ox, oy, x0, y0, x1, y1;
163
164 double ai;
165 double atmp = 0;
166 double xtmp = 0;
167 double ytmp = 0;
168
169 // Use first point as origin to improve numerical accuracy
170 ox=p[0].x;
171 oy=p[0].y;
172
173 for (i = 0; i < count-1; i++)
174 {
175 x0=p[i].x;
176 y0=p[i].y;
177 x1=p[i+1].x;
178 y1=p[i+1].y;
179
180 x0 -= ox; y0 -= oy;
181 x1 -= ox; y1 -= oy;
182
183 ai = x0 * y1 - x1 * y0;
184 atmp += ai;
185 xtmp += (x1 + x0) * ai;
186 ytmp += (y1 + y0) * ai;
187 }
188
189 if (atmp != 0)
190 {
191 c->x = (xtmp/(3*atmp)) + ox;
192 c->y = (ytmp/(3*atmp)) + oy;
193 return 1;
194 }
195 c->x = x0;
196 c->y = y0;
197
198 return 0;
199}
200
201
202/**
203 * Get coordinates of polyline point c most close to given point p.
204 * @param in *pl array of polyline vertex coordinates
205 * @param in count count of polyline vertexes
206 * @param in *p point coordinates
207 * @param out *c coordinates of polyline point most close to given point.
208 * @returns first vertex number of polyline segment to which c belongs
209 */
210int
211geom_poly_closest_point(struct coord *pl, int count, struct coord *p, struct coord *c)
212{
213 int i,vertex=0;
214 long long x, y, xi, xj, yi, yj, u, d, dmin=0;
215 if(count<2) {
216 c->x=pl->x;
217 c->y=pl->y;
218 return 0;
219 }
220 for(i=0;i<count-1;i++) {
221 xi=pl[i].x;
222 yi=pl[i].y;
223 xj=pl[i+1].x;
224 yj=pl[i+1].y;
225 u=(xj-xi)*(xj-xi)+(yj-yi)*(yj-yi);
226 if(u!=0) {
227 u=((p->x-xi)*(xj-xi)+(p->y-yi)*(yj-yi))*1000/u;
228 }
229 if(u<0)
230 u=0;
231 else if (u>1000)
232 u=1000;
233 x=xi+u*(xj-xi)/1000;
234 y=yi+u*(yj-yi)/1000;
235 d=(p->x-x)*(p->x-x)+(p->y-y)*(p->y-y);
236 if(i==0 || d<dmin) {
237 dmin=d;
238 c->x=x;
239 c->y=y;
240 vertex=i;
241 }
242 }
243 return vertex;
244}
245
246/**
247 * Check if point is inside polygon
248 * @param in *cp array of polygon vertex coordinates
249 * @param in count count of polygon vertexes
250 * @param in *c point coordinates
251 * @returns 1 - inside, 0 - outside
252 */
253int
254geom_poly_point_inside(struct coord *cp, int count, struct coord *c)
255{
256 int ret=0;
257 struct coord *last=cp+count-1;
258 while (cp < last)
259 {
260 if ((cp[0].y > c->y) != (cp[1].y > c->y) &&
261 c->x < ((long long)cp[1].x-cp[0].x)*(c->y-cp[0].y)/(cp[1].y-cp[0].y)+cp[0].x)
262 {
263#if 0
264 fprintf(stderr," cross 0x%x,0x%x-0x%x,0x%x %dx%d",cp,cp[0].x,cp[0].y,cp[1].x,cp[1].y,cp[1].x-cp[0].x,c->y-cp[0].y);
265 printf("type=selected_line\n");
266 coord_print(projection_mg, &cp[0], stdout);
267 coord_print(projection_mg, &cp[1], stdout);
268#endif
269 ret=!ret;
270 }
271 cp++;
272 }
273 return ret;
274}
275
70 276
71GList * 277GList *
72geom_poly_segments_insert(GList *list, struct geom_poly_segment *first, struct geom_poly_segment *second, struct geom_poly_segment *third) 278geom_poly_segments_insert(GList *list, struct geom_poly_segment *first, struct geom_poly_segment *second, struct geom_poly_segment *third)
73{ 279{
74 int count; 280 int count;
75 struct geom_poly_segment *ret; 281 struct geom_poly_segment *ret;
76 struct coord *pos; 282 struct coord *pos;
77 283
78 if (!second) 284 if (!second)
79 return NULL;
80 ret=g_new(struct geom_poly_segment, 1); 285 return NULL; ret=g_new(struct geom_poly_segment, 1);
81 ret->type=second->type; 286 ret->type = second->type;
82 count=(second->last-second->first)+1; 287 count = (second->last - second->first) + 1;
83 if (first) 288 if (first)
84 count+=(first->last-first->first); 289 count += (first->last - first->first);
85 if (third) 290 if (third)
86 count+=(third->last-third->first); 291 count += (third->last - third->first);
87#if 0 292#if 0
88 fprintf(stderr,"count=%d first=%p second=%p third=%p\n",count,first,second,third); 293 fprintf(stderr,"count=%d first=%p second=%p third=%p\n",count,first,second,third);
89 if (first) 294 if (first)
90 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); 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);
91 if (second) 296 if (second)
92 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); 297 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);
93 if (third) 298 if (third)
94 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); 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);
95#endif 300#endif
96 ret->first=g_new(struct coord, count); 301 ret->first=g_new(struct coord, count);
97 pos=ret->first; 302 pos = ret->first;
98 if (first) { 303 if (first)
304 {
99 count=(first->last-first->first)+1; 305 count = (first->last - first->first) + 1;
100 geom_coord_copy(first->first, pos, count, coord_is_equal(*first->first, *second->first)); 306 geom_coord_copy(first->first, pos, count, coord_is_equal(*first->first, *second->first));
101 pos+=count-1; 307 pos += count - 1;
102 } 308 }
103 count=(second->last-second->first)+1; 309 count = (second->last - second->first) + 1;
104 geom_coord_copy(second->first, pos, count, 0); 310 geom_coord_copy(second->first, pos, count, 0);
105 pos+=count; 311 pos += count;
106 if (third) { 312 if (third)
313 {
107 pos--; 314 pos--;
108 count=(third->last-third->first)+1; 315 count = (third->last - third->first) + 1;
109 geom_coord_copy(third->first, pos, count, coord_is_equal(*third->last, *second->last)); 316 geom_coord_copy(third->first, pos, count, coord_is_equal(*third->last, *second->last));
110 pos+=count; 317 pos += count;
111 } 318 }
112 ret->last=pos-1; 319 ret->last = pos - 1;
113#if 0 320#if 0
114 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); 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);
115#endif 322#endif
116 list=g_list_prepend(list, ret); 323 list = g_list_prepend(list, ret);
117#if 0 324#if 0
118 fprintf(stderr,"List=%p\n",list); 325 fprintf(stderr,"List=%p\n",list);
119#endif 326#endif
120 return list; 327 return list;
121} 328}
122 329
123void
124geom_poly_segment_destroy(struct geom_poly_segment *seg) 330void geom_poly_segment_destroy(struct geom_poly_segment *seg)
125{ 331{
126 g_free(seg->first); 332 g_free(seg->first);
127 g_free(seg); 333 g_free(seg);
128} 334}
129 335
130GList * 336GList *
131geom_poly_segments_remove(GList *list, struct geom_poly_segment *seg) 337geom_poly_segments_remove(GList *list, struct geom_poly_segment *seg)
132{ 338{
133 if (seg) { 339 if (seg)
340 {
134 list=g_list_remove(list, seg); 341 list = g_list_remove(list, seg);
135 geom_poly_segment_destroy(seg); 342 geom_poly_segment_destroy(seg);
136 } 343 }
137 return list; 344 return list;
138} 345}
139 346
140int
141geom_poly_segment_compatible(struct geom_poly_segment *s1, struct geom_poly_segment *s2, int dir) 347int geom_poly_segment_compatible(struct geom_poly_segment *s1, struct geom_poly_segment *s2, int dir)
142{ 348{
143 int same=0,opposite=0; 349 int same = 0, opposite = 0;
144 if (s1->type == geom_poly_segment_type_none || s2->type == geom_poly_segment_type_none) 350 if (s1->type == geom_poly_segment_type_none || s2->type == geom_poly_segment_type_none)
145 return 0; 351 return 0;
146 if (s1->type == s2->type) 352 if (s1->type == s2->type)
353 {
147 same=1; 354 same = 1;
148 if (s1->type == geom_poly_segment_type_way_inner && s2->type == geom_poly_segment_type_way_outer) 355 if (s1->type == geom_poly_segment_type_way_inner || s1->type == geom_poly_segment_type_way_outer)
356 {
149 opposite=1; 357 opposite = 1;
150 if (s1->type == geom_poly_segment_type_way_outer && s2->type == geom_poly_segment_type_way_inner) 358 }
151 opposite=1; 359 }
152 if (s1->type == geom_poly_segment_type_way_left_side && s2->type == geom_poly_segment_type_way_right_side) 360 if (s1->type == geom_poly_segment_type_way_left_side && s2->type == geom_poly_segment_type_way_right_side)
153 opposite=1; 361 opposite = 1;
154 if (s1->type == geom_poly_segment_type_way_right_side && s2->type == geom_poly_segment_type_way_left_side) 362 if (s1->type == geom_poly_segment_type_way_right_side && s2->type == geom_poly_segment_type_way_left_side)
155 opposite=1; 363 opposite = 1;
156 if (s1->type == geom_poly_segment_type_way_unknown || s2->type == geom_poly_segment_type_way_unknown) { 364 if (s1->type == geom_poly_segment_type_way_unknown || s2->type == geom_poly_segment_type_way_unknown)
365 {
157 same=1; 366 same = 1;
158 opposite=1; 367 opposite = 1;
159 } 368 }
160 if (dir < 0) { 369 if (dir < 0)
370 {
161 if ((opposite && coord_is_equal(*s1->first, *s2->first)) || (same && coord_is_equal(*s1->first, *s2->last))) 371 if ((opposite && coord_is_equal(*s1->first, *s2->first)) || (same && coord_is_equal(*s1->first, *s2->last)))
162 return 1; 372 return 1;
163 } else { 373 }
374 else
375 {
164 if ((opposite && coord_is_equal(*s1->last, *s2->last)) || (same && coord_is_equal(*s1->last, *s2->first))) 376 if ((opposite && coord_is_equal(*s1->last, *s2->last)) || (same && coord_is_equal(*s1->last, *s2->first)))
165 return 1; 377 return 1;
166 } 378 }
167 return 0; 379 return 0;
168} 380}
169
170 381
171GList * 382GList *
172geom_poly_segments_sort(GList *in, enum geom_poly_segment_type type) 383geom_poly_segments_sort(GList *in, enum geom_poly_segment_type type)
173{ 384{
174 GList *ret=NULL; 385 GList *ret = NULL;
175 while (in) { 386 while (in)
387 {
176 struct geom_poly_segment *seg=in->data; 388 struct geom_poly_segment *seg = in->data;
177 GList *tmp=ret; 389 GList *tmp = ret;
178 struct geom_poly_segment *merge_first=NULL,*merge_last=NULL; 390 struct geom_poly_segment *merge_first = NULL, *merge_last = NULL;
179 while (tmp) { 391 while (tmp)
392 {
180 struct geom_poly_segment *cseg=tmp->data; 393 struct geom_poly_segment *cseg = tmp->data;
181 if (geom_poly_segment_compatible(seg, cseg, -1)) 394 if (geom_poly_segment_compatible(seg, cseg, -1))
182 merge_first=cseg; 395 merge_first = cseg;
183 if (geom_poly_segment_compatible(seg, cseg, 1)) 396 if (geom_poly_segment_compatible(seg, cseg, 1))
184 merge_last=cseg; 397 merge_last = cseg;
185 tmp=g_list_next(tmp); 398 tmp = g_list_next(tmp);
186 } 399 }
187 if (merge_first == merge_last) 400 if (merge_first == merge_last)
401 {
188 merge_last=NULL; 402 merge_last = NULL;
403 }
189 ret=geom_poly_segments_insert(ret, merge_first, seg, merge_last); 404 ret = geom_poly_segments_insert(ret, merge_first, seg, merge_last);
190 ret=geom_poly_segments_remove(ret, merge_first); 405 ret = geom_poly_segments_remove(ret, merge_first);
191 ret=geom_poly_segments_remove(ret, merge_last); 406 ret = geom_poly_segments_remove(ret, merge_last);
192 in=g_list_next(in); 407 in = g_list_next(in);
193 } 408 }
409
194 in=ret; 410 in = ret;
195 while (in) { 411 while (in)
412 {
196 struct geom_poly_segment *seg=in->data; 413 struct geom_poly_segment *seg = in->data;
197 if (coord_is_equal(*seg->first, *seg->last)) { 414 if (coord_is_equal(*seg->first, *seg->last))
415 {
198 long long area=geom_poly_area(seg->first,seg->last-seg->first+1); 416 long long area = geom_poly_area(seg->first, seg->last - seg->first + 1);
199 if (type == geom_poly_segment_type_way_right_side && seg->type == geom_poly_segment_type_way_right_side) { 417 if (type == geom_poly_segment_type_way_right_side && seg->type == geom_poly_segment_type_way_right_side)
418 {
200 seg->type=area > 0 ? geom_poly_segment_type_way_outer : geom_poly_segment_type_way_inner; 419 seg->type = area > 0 ? geom_poly_segment_type_way_outer : geom_poly_segment_type_way_inner;
201 }
202 } 420 }
421 }
203 in=g_list_next(in); 422 in = g_list_next(in);
204 } 423 }
205 return ret; 424 return ret;
206} 425}
207 426
427int geom_poly_segments_point_inside(GList *in, struct coord *c)
428{
429 int open_matches = 0, closed_matches = 0;
430 struct coord *cp;
431
432 //fprintf(stderr,"point: x=%d, y=%d\n",c->x,c->y);
433
434 while (in)
435 {
436 struct geom_poly_segment *seg = in->data;
437 cp = seg->first;
438
439 //fprintf(stderr, " seg x=%d, y=%d\n", seg->first[0].x, seg->first[0].y);
440
441 if (geom_poly_point_inside(seg->first, seg->last - seg->first + 1, c))
442 {
443#if 0
444 fprintf(stderr," inside");
445#endif
446 if (coord_is_equal(*seg->first, *seg->last))
447 {
448 closed_matches++;
449 }
450 else
451 {
452 open_matches++;
453 }
454 }
455 else
456 {
457#if 0
458 fprintf(stderr," outside");
459#endif
460 }
461 in = g_list_next(in);
462 }
463#if 0
464 fprintf(stderr,"\n");
465 fprintf(stderr,"open_matches %d closed_matches %d\n",open_matches,closed_matches);
466#endif
467 if (closed_matches)
468 {
469 if (closed_matches & 1)
470 return 1;
471 else
472 return 0;
473 }
474 if (open_matches)
475 {
476 if (open_matches & 1)
477 return -1;
478 else
479 return 0;
480 }
481 return 0;
482}
483
208int 484int
209geom_poly_segments_point_inside(GList *in, struct coord *c) 485item_bin_is_closed_poly(struct item_bin *ib)
210{ 486{
211 int ret=0; 487 // int is_closed_poly = 0;
212 struct coord *cp; 488
213 while (in) { 489 int i;
214 struct geom_poly_segment *seg=in->data; 490 int count = ib->clen / 2;
215 cp=seg->first; 491 if (count <= 1)
216 while (cp < seg->last) { 492 {
217 if ((cp[0].y > c->y) != (cp[1].y > c->y) && 493 return 0;
218 c->x < (cp[1].x-cp[0].x)*(c->y-cp[0].y)/(cp[1].y-cp[0].y)+cp[0].x)
219 ret=!ret;
220 cp++;
221 } 494 }
222 in=g_list_next(in); 495
496 struct coord *c = (struct coord *) (ib + 1);
497 //for (i = 0; i < count; i++) // loop thru all the coordinates (nodes) of this way
498 //{
499 //}
500
501 if ((c[0].x == c[count-1].x) && (c[0].y == c[count-1].y))
502 {
503 //fprintf(stderr,"%d,%d %d,%d\n", c[0].x,c[0].y,c[count-1].x,c[count-1].y);
504 // is_closed_poly = 1;
505 return 1;
223 } 506 }
507 //else
508 //{
509 // //fprintf(stderr,"%d .. %d,%d %d,%d\n", count, c[0].x,c[0].y,c[count-1].x,c[count-1].y);
510 //}
511
512 // return is_closed_poly;
224 return ret; 513 return 0;
225} 514}
226 515
227struct geom_poly_segment * 516struct geom_poly_segment *
228item_bin_to_poly_segment(struct item_bin *ib, int type) 517item_bin_to_poly_segment(struct item_bin *ib, int type)
229{ 518{
519 //fprintf(stderr,"item_bin_to_poly_segment:001\n");
520
230 struct geom_poly_segment *ret=g_new(struct geom_poly_segment, 1); 521 struct geom_poly_segment *ret=g_new(struct geom_poly_segment, 1);
231 int count=ib->clen*sizeof(int)/sizeof(struct coord); 522 int count = ib->clen * sizeof(int) / sizeof(struct coord);
523
524 //fprintf(stderr, "item id:%lld\n", item_bin_get_attr(ib, attr_osm_wayid, NULL));
525 //fprintf(stderr,"item_bin_to_poly_segment:count=%d\n", ib->clen);
526
232 ret->type=type; 527 ret->type = type;
233 ret->first=g_new(struct coord, count); 528 ret->first=g_new(struct coord, count);
234 ret->last=ret->first+count-1; 529 ret->last = ret->first + count - 1;
530
531 //fprintf(stderr,"item_bin_to_poly_segment:002.f %d %d\n", ret->first->x, ret->first->y);
532 //fprintf(stderr,"item_bin_to_poly_segment:002.l %d %d\n", ret->last->x, ret->last->y);
533
534 //fprintf(stderr,"********DUMP***********\n");
535 //dump_itembin(ib);
536 //fprintf(stderr,"********DUMP***********\n");
537
235 geom_coord_copy((struct coord *)(ib+1), ret->first, count, 0); 538 geom_coord_copy((struct coord *) (ib + 1), ret->first, count, 0);
539
540 //fprintf(stderr,"item_bin_to_poly_segment:099\n");
541
236 return ret; 542 return ret;
237} 543}
238 544
239
240static int
241clipcode(struct coord *p, struct rect *r) 545static int clipcode(struct coord *p, struct rect *r)
242{ 546{
243 int code=0; 547 int code = 0;
244 if (p->x < r->l.x) 548 if (p->x < r->l.x)
245 code=1; 549 code = 1;
246 if (p->x > r->h.x) 550 if (p->x > r->h.x)
247 code=2; 551 code = 2;
248 if (p->y < r->l.y) 552 if (p->y < r->l.y)
249 code |=4; 553 code |= 4;
250 if (p->y > r->h.y) 554 if (p->y > r->h.y)
251 code |=8; 555 code |= 8;
252 return code; 556 return code;
253} 557}
254 558
255
256static int
257clip_line_code(struct coord *p1, struct coord *p2, struct rect *r) 559static int clip_line_code(struct coord *p1, struct coord *p2, struct rect *r)
258{ 560{
259 int code1,code2,ret=1; 561 int code1, code2, ret = 1;
260 long long dx,dy; 562 long long dx, dy;
261 code1=clipcode(p1, r); 563 code1 = clipcode(p1, r);
262 if (code1) 564 if (code1)
263 ret |= 2; 565 ret |= 2;
264 code2=clipcode(p2, r); 566 code2 = clipcode(p2, r);
265 if (code2) 567 if (code2)
266 ret |= 4; 568 ret |= 4;
267 dx=p2->x-p1->x; 569 dx = p2->x - p1->x;
268 dy=p2->y-p1->y; 570 dy = p2->y - p1->y;
269 while (code1 || code2) { 571 while (code1 || code2)
572 {
270 if (code1 & code2) 573 if (code1 & code2)
271 return 0; 574 return 0;
272 if (code1 & 1) { 575 if (code1 & 1)
576 {
273 p1->y+=(r->l.x-p1->x)*dy/dx; 577 p1->y += (r->l.x - p1->x) * dy / dx;
274 p1->x=r->l.x; 578 p1->x = r->l.x;
579 }
275 } else if (code1 & 2) { 580 else if (code1 & 2)
581 {
276 p1->y+=(r->h.x-p1->x)*dy/dx; 582 p1->y += (r->h.x - p1->x) * dy / dx;
277 p1->x=r->h.x; 583 p1->x = r->h.x;
584 }
278 } else if (code1 & 4) { 585 else if (code1 & 4)
586 {
279 p1->x+=(r->l.y-p1->y)*dx/dy; 587 p1->x += (r->l.y - p1->y) * dx / dy;
280 p1->y=r->l.y; 588 p1->y = r->l.y;
589 }
281 } else if (code1 & 8) { 590 else if (code1 & 8)
591 {
282 p1->x+=(r->h.y-p1->y)*dx/dy; 592 p1->x += (r->h.y - p1->y) * dx / dy;
283 p1->y=r->h.y; 593 p1->y = r->h.y;
284 } 594 }
285 code1=clipcode(p1, r); 595 code1 = clipcode(p1, r);
286 if (code1 & code2) 596 if (code1 & code2)
287 return 0; 597 return 0;
288 if (code2 & 1) { 598 if (code2 & 1)
599 {
289 p2->y+=(r->l.x-p2->x)*dy/dx; 600 p2->y += (r->l.x - p2->x) * dy / dx;
290 p2->x=r->l.x; 601 p2->x = r->l.x;
602 }
291 } else if (code2 & 2) { 603 else if (code2 & 2)
604 {
292 p2->y+=(r->h.x-p2->x)*dy/dx; 605 p2->y += (r->h.x - p2->x) * dy / dx;
293 p2->x=r->h.x; 606 p2->x = r->h.x;
607 }
294 } else if (code2 & 4) { 608 else if (code2 & 4)
609 {
295 p2->x+=(r->l.y-p2->y)*dx/dy; 610 p2->x += (r->l.y - p2->y) * dx / dy;
296 p2->y=r->l.y; 611 p2->y = r->l.y;
612 }
297 } else if (code2 & 8) { 613 else if (code2 & 8)
614 {
298 p2->x+=(r->h.y-p2->y)*dx/dy; 615 p2->x += (r->h.y - p2->y) * dx / dy;
299 p2->y=r->h.y; 616 p2->y = r->h.y;
300 } 617 }
301 code2=clipcode(p2, r); 618 code2 = clipcode(p2, r);
302 } 619 }
303 if (p1->x == p2->x && p1->y == p2->y) 620 if (p1->x == p2->x && p1->y == p2->y)
304 ret=0; 621 ret = 0;
305 return ret; 622 return ret;
306} 623}
307 624
308void
309clip_line(struct item_bin *ib, struct rect *r, struct tile_parameter *param, struct item_bin_sink *out) 625void clip_line(struct item_bin *ib, struct rect *r, struct tile_parameter *param, struct item_bin_sink *out)
310{ 626{
311 char *buffer=g_alloca(sizeof(char)*(ib->len*4+32)); 627 char *buffer = g_alloca(sizeof(char) * (ib->len * 4 + 32));
312 struct item_bin *ib_new=(struct item_bin *)buffer; 628 struct item_bin *ib_new = (struct item_bin *) buffer;
313 struct coord *pa=(struct coord *)(ib+1); 629 struct coord *pa = (struct coord *) (ib + 1);
314 int count=ib->clen/2; 630 int count = ib->clen / 2;
315 struct coord p1,p2; 631 struct coord p1, p2;
316 int i,code; 632 int i, code;
317 item_bin_init(ib_new, ib->type); 633 item_bin_init(ib_new, ib->type);
318 for (i = 0 ; i < count ; i++) { 634 for (i = 0; i < count; i++)
635 {
319 if (i) { 636 if (i)
637 {
320 p1.x=pa[i-1].x; 638 p1.x = pa[i - 1].x;
321 p1.y=pa[i-1].y; 639 p1.y = pa[i - 1].y;
322 p2.x=pa[i].x; 640 p2.x = pa[i].x;
323 p2.y=pa[i].y; 641 p2.y = pa[i].y;
324 /* 0 = invisible, 1 = completely visible, 3 = start point clipped, 5 = end point clipped, 7 both points clipped */ 642 /* 0 = invisible, 1 = completely visible, 3 = start point clipped, 5 = end point clipped, 7 both points clipped */
325 code=clip_line_code(&p1, &p2, r); 643 code = clip_line_code(&p1, &p2, r);
326#if 1 644#if 1
327 if (((code == 1 || code == 5) && ib_new->clen == 0) || (code & 2)) { 645 if (((code == 1 || code == 5) && ib_new->clen == 0) || (code & 2))
646 {
328 item_bin_add_coord(ib_new, &p1, 1); 647 item_bin_add_coord(ib_new, &p1, 1);
329 } 648 }
330 if (code) { 649 if (code)
650 {
331 item_bin_add_coord(ib_new, &p2, 1); 651 item_bin_add_coord(ib_new, &p2, 1);
332 } 652 }
333 if (i == count-1 || (code & 4)) { 653 if (i == count - 1 || (code & 4))
654 {
334 if (ib_new->clen) 655 if (ib_new->clen)
335 item_bin_write_clipped(ib_new, param, out); 656 item_bin_write_clipped(ib_new, param, out);
336 item_bin_init(ib_new, ib->type); 657 item_bin_init(ib_new, ib->type);
337 } 658 }
338#else 659#else
339 if (code) { 660 if (code)
661 {
340 item_bin_init(ib_new, ib->type); 662 item_bin_init(ib_new, ib->type);
341 item_bin_add_coord(ib_new, &p1, 1); 663 item_bin_add_coord(ib_new, &p1, 1);
342 item_bin_add_coord(ib_new, &p2, 1); 664 item_bin_add_coord(ib_new, &p2, 1);
343 item_bin_write_clipped(ib_new, param, out); 665 item_bin_write_clipped(ib_new, param, out);
344 } 666 }
345#endif 667#endif
346 } 668 }
347 } 669 }
348} 670}
349 671
350static int
351is_inside(struct coord *p, struct rect *r, int edge) 672static int is_inside(struct coord *p, struct rect *r, int edge)
352{ 673{
353 switch(edge) { 674 switch (edge)
675 {
354 case 0: 676 case 0:
355 return p->x >= r->l.x; 677 return p->x >= r->l.x;
356 case 1: 678 case 1:
357 return p->x <= r->h.x; 679 return p->x <= r->h.x;
358 case 2: 680 case 2:
359 return p->y >= r->l.y; 681 return p->y >= r->l.y;
360 case 3: 682 case 3:
361 return p->y <= r->h.y; 683 return p->y <= r->h.y;
362 default: 684 default:
363 return 0; 685 return 0;
364 } 686 }
365} 687}
366 688
367static void
368poly_intersection(struct coord *p1, struct coord *p2, struct rect *r, int edge, struct coord *ret) 689static void poly_intersection(struct coord *p1, struct coord *p2, struct rect *r, int edge, struct coord *ret)
369{ 690{
370 int dx=p2->x-p1->x; 691 int dx = p2->x - p1->x;
371 int dy=p2->y-p1->y; 692 int dy = p2->y - p1->y;
372 switch(edge) { 693 switch (edge)
694 {
373 case 0: 695 case 0:
374 ret->y=p1->y+(r->l.x-p1->x)*dy/dx; 696 ret->y = p1->y + (r->l.x - p1->x) * dy / dx;
375 ret->x=r->l.x; 697 ret->x = r->l.x;
376 break; 698 break;
377 case 1: 699 case 1:
378 ret->y=p1->y+(r->h.x-p1->x)*dy/dx; 700 ret->y = p1->y + (r->h.x - p1->x) * dy / dx;
379 ret->x=r->h.x; 701 ret->x = r->h.x;
380 break; 702 break;
381 case 2: 703 case 2:
382 ret->x=p1->x+(r->l.y-p1->y)*dx/dy; 704 ret->x = p1->x + (r->l.y - p1->y) * dx / dy;
383 ret->y=r->l.y; 705 ret->y = r->l.y;
384 break; 706 break;
385 case 3: 707 case 3:
386 ret->x=p1->x+(r->h.y-p1->y)*dx/dy; 708 ret->x = p1->x + (r->h.y - p1->y) * dx / dy;
387 ret->y=r->h.y; 709 ret->y = r->h.y;
388 break; 710 break;
389 } 711 }
390} 712}
391 713
392void
393clip_polygon(struct item_bin *ib, struct rect *r, struct tile_parameter *param, struct item_bin_sink *out) 714void clip_polygon(struct item_bin *ib, struct rect *r, struct tile_parameter *param, struct item_bin_sink *out)
394{ 715{
395 int count_in=ib->clen/2; 716 int count_in = ib->clen / 2;
396 struct coord *pin,*p,*s,pi; 717 struct coord *pin, *p, *s, pi;
397 char *buffer1=g_alloca(sizeof(char)*(ib->len*4+ib->clen*7+32)); 718 char *buffer1 = g_alloca(sizeof(char) * (ib->len * 4 + ib->clen * 7 + 32));
398 struct item_bin *ib1=(struct item_bin *)buffer1; 719 struct item_bin *ib1 = (struct item_bin *) buffer1;
399 char *buffer2=g_alloca(sizeof(char)*(ib->len*4+ib->clen*7+32)); 720 char *buffer2 = g_alloca(sizeof(char) * (ib->len * 4 + ib->clen * 7 + 32));
400 struct item_bin *ib2=(struct item_bin *)buffer2; 721 struct item_bin *ib2 = (struct item_bin *) buffer2;
401 struct item_bin *ib_in,*ib_out; 722 struct item_bin *ib_in, *ib_out;
402 int edge,i; 723 int edge, i;
403 ib_out=ib1; 724 ib_out = ib1;
404 ib_in=ib; 725 ib_in = ib;
405 for (edge = 0 ; edge < 4 ; edge++) { 726 for (edge = 0; edge < 4; edge++)
727 {
406 count_in=ib_in->clen/2; 728 count_in = ib_in->clen / 2;
407 pin=(struct coord *)(ib_in+1); 729 pin = (struct coord *) (ib_in + 1);
408 p=pin; 730 p = pin;
409 s=pin+count_in-1; 731 s = pin + count_in - 1;
410 item_bin_init(ib_out, ib_in->type); 732 item_bin_init(ib_out, ib_in->type);
411 for (i = 0 ; i < count_in ; i++) { 733 for (i = 0; i < count_in; i++)
734 {
412 if (is_inside(p, r, edge)) { 735 if (is_inside(p, r, edge))
736 {
413 if (! is_inside(s, r, edge)) { 737 if (!is_inside(s, r, edge))
738 {
414 poly_intersection(s,p,r,edge,&pi); 739 poly_intersection(s, p, r, edge, &pi);
415 item_bin_add_coord(ib_out, &pi, 1); 740 item_bin_add_coord(ib_out, &pi, 1);
416 } 741 }
417 item_bin_add_coord(ib_out, p, 1); 742 item_bin_add_coord(ib_out, p, 1);
743 }
418 } else { 744 else
745 {
419 if (is_inside(s, r, edge)) { 746 if (is_inside(s, r, edge))
747 {
420 poly_intersection(p,s,r,edge,&pi); 748 poly_intersection(p, s, r, edge, &pi);
421 item_bin_add_coord(ib_out, &pi, 1); 749 item_bin_add_coord(ib_out, &pi, 1);
422 } 750 }
423 } 751 }
424 s=p; 752 s = p;
425 p++; 753 p++;
426 } 754 }
427 if (ib_in == ib1) { 755 if (ib_in == ib1)
756 {
428 ib_in=ib2; 757 ib_in = ib2;
429 ib_out=ib1; 758 ib_out = ib1;
759 }
430 } else { 760 else
431 ib_in=ib1; 761 {
762 ib_in = ib1;
432 ib_out=ib2; 763 ib_out = ib2;
433 } 764 }
434 } 765 }
435 if (ib_in->clen) 766 if (ib_in->clen)
436 item_bin_write_clipped(ib_in, param, out); 767 item_bin_write_clipped(ib_in, param, out);
437} 768}
769

Legend:
Removed from v.8  
changed lines
  Added in v.31

   
Visit the ZANavi Wiki