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 |
|
20 |
/**
|
21 |
* Navit, a modular navigation system.
|
22 |
* Copyright (C) 2005-2011 Navit Team
|
23 |
*
|
24 |
* This program is free software; you can redistribute it and/or
|
25 |
* modify it under the terms of the GNU General Public License
|
26 |
* version 2 as published by the Free Software Foundation.
|
27 |
*
|
28 |
* This program is distributed in the hope that it will be useful,
|
29 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
30 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
31 |
* GNU General Public License for more details.
|
32 |
*
|
33 |
* You should have received a copy of the GNU General Public License
|
34 |
* along with this program; if not, write to the
|
35 |
* Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
|
36 |
* Boston, MA 02110-1301, USA.
|
37 |
*/
|
38 |
#include <string.h>
|
39 |
#include <math.h>
|
40 |
#include "maptool.h"
|
41 |
|
42 |
void geom_coord_copy(struct coord *from, struct coord *to, int count, int reverse)
|
43 |
{
|
44 |
int i;
|
45 |
if (!reverse)
|
46 |
{
|
47 |
memcpy(to, from, count * sizeof(struct coord));
|
48 |
return;
|
49 |
}
|
50 |
from += count;
|
51 |
for (i = 0; i < count; i++)
|
52 |
{
|
53 |
*to++ = *--from;
|
54 |
}
|
55 |
}
|
56 |
|
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 |
*/
|
65 |
int 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 |
|
110 |
void geom_coord_revert(struct coord *c, int count)
|
111 |
{
|
112 |
struct coord tmp;
|
113 |
int i;
|
114 |
|
115 |
for (i = 0; i < count / 2; i++)
|
116 |
{
|
117 |
tmp = c[i];
|
118 |
c[i] = c[count - 1 - i];
|
119 |
c[count - 1 - i] = tmp;
|
120 |
}
|
121 |
}
|
122 |
|
123 |
long long geom_poly_area(struct coord *c, int count)
|
124 |
{
|
125 |
long long area = 0;
|
126 |
int i, j = 0;
|
127 |
#if 0
|
128 |
fprintf(stderr,"count=%d\n",count);
|
129 |
#endif
|
130 |
for (i = 0; i < count; i++)
|
131 |
{
|
132 |
if (++j == count)
|
133 |
j = 0;
|
134 |
#if 0
|
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));
|
136 |
#endif
|
137 |
area += (long long) (c[i].x + c[j].x) * (c[i].y - c[j].y);
|
138 |
#if 0
|
139 |
fprintf(stderr,"area="LONGLONG_FMT"\n",area);
|
140 |
#endif
|
141 |
}
|
142 |
return area / 2;
|
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 |
|
152 |
new version taken from mapnik source:
|
153 |
https://github.com/mapnik/mapnik/blob/master/include/mapnik/geometry.hpp
|
154 |
function:
|
155 |
label_position
|
156 |
|
157 |
*/
|
158 |
int
|
159 |
geom_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 |
*/
|
210 |
int
|
211 |
geom_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 |
|
216 |
if (count<2)
|
217 |
{
|
218 |
c->x=pl->x;
|
219 |
c->y=pl->y;
|
220 |
return 0;
|
221 |
}
|
222 |
|
223 |
for (i=0;i<count-1;i++)
|
224 |
{
|
225 |
xi=pl[i].x;
|
226 |
yi=pl[i].y;
|
227 |
xj=pl[i+1].x;
|
228 |
yj=pl[i+1].y;
|
229 |
u=(xj-xi)*(xj-xi)+(yj-yi)*(yj-yi);
|
230 |
|
231 |
if(u!=0)
|
232 |
{
|
233 |
u=((p->x-xi)*(xj-xi)+(p->y-yi)*(yj-yi))*1000/u;
|
234 |
}
|
235 |
|
236 |
if(u<0)
|
237 |
{
|
238 |
u=0;
|
239 |
}
|
240 |
else if (u>1000)
|
241 |
{
|
242 |
u=1000;
|
243 |
}
|
244 |
|
245 |
x=xi+u*(xj-xi)/1000;
|
246 |
y=yi+u*(yj-yi)/1000;
|
247 |
d=(p->x-x)*(p->x-x)+(p->y-y)*(p->y-y);
|
248 |
|
249 |
if (i==0 || d<dmin)
|
250 |
{
|
251 |
dmin=d;
|
252 |
c->x=x;
|
253 |
c->y=y;
|
254 |
vertex=i;
|
255 |
}
|
256 |
}
|
257 |
|
258 |
return vertex;
|
259 |
}
|
260 |
|
261 |
/**
|
262 |
* Check if point is inside polygon
|
263 |
* @param in *cp array of polygon vertex coordinates
|
264 |
* @param in count count of polygon vertexes
|
265 |
* @param in *c point coordinates
|
266 |
* @returns 1 - inside, 0 - outside
|
267 |
*/
|
268 |
int
|
269 |
geom_poly_point_inside(struct coord *cp, int count, struct coord *c)
|
270 |
{
|
271 |
int ret=0;
|
272 |
struct coord *last=cp+count-1;
|
273 |
while (cp < last)
|
274 |
{
|
275 |
if ((cp[0].y > c->y) != (cp[1].y > c->y) &&
|
276 |
c->x < ((long long)cp[1].x-cp[0].x)*(c->y-cp[0].y)/(cp[1].y-cp[0].y)+cp[0].x)
|
277 |
{
|
278 |
#if 0
|
279 |
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);
|
280 |
printf("type=selected_line\n");
|
281 |
coord_print(projection_mg, &cp[0], stdout);
|
282 |
coord_print(projection_mg, &cp[1], stdout);
|
283 |
#endif
|
284 |
ret=!ret;
|
285 |
}
|
286 |
cp++;
|
287 |
}
|
288 |
return ret;
|
289 |
}
|
290 |
|
291 |
|
292 |
GList *
|
293 |
geom_poly_segments_insert(GList *list, struct geom_poly_segment *first, struct geom_poly_segment *second, struct geom_poly_segment *third)
|
294 |
{
|
295 |
int count;
|
296 |
struct geom_poly_segment *ret;
|
297 |
struct coord *pos;
|
298 |
|
299 |
if (!second)
|
300 |
return NULL; ret=g_new(struct geom_poly_segment, 1);
|
301 |
|
302 |
ret->type = second->type;
|
303 |
count = (second->last - second->first) + 1;
|
304 |
if (first)
|
305 |
count += (first->last - first->first);
|
306 |
|
307 |
if (third)
|
308 |
count += (third->last - third->first);
|
309 |
|
310 |
#if 0
|
311 |
fprintf(stderr,"count=%d first=%p second=%p third=%p\n",count,first,second,third);
|
312 |
if (first)
|
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);
|
314 |
if (second)
|
315 |
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);
|
316 |
if (third)
|
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);
|
318 |
#endif
|
319 |
ret->first=g_new(struct coord, count);
|
320 |
pos = ret->first;
|
321 |
|
322 |
if (first)
|
323 |
{
|
324 |
count = (first->last - first->first) + 1;
|
325 |
geom_coord_copy(first->first, pos, count, coord_is_equal(*first->first, *second->first));
|
326 |
pos += count - 1;
|
327 |
}
|
328 |
|
329 |
count = (second->last - second->first) + 1;
|
330 |
geom_coord_copy(second->first, pos, count, 0);
|
331 |
pos += count;
|
332 |
|
333 |
if (third)
|
334 |
{
|
335 |
pos--;
|
336 |
count = (third->last - third->first) + 1;
|
337 |
geom_coord_copy(third->first, pos, count, coord_is_equal(*third->last, *second->last));
|
338 |
pos += count;
|
339 |
}
|
340 |
|
341 |
ret->last = pos - 1;
|
342 |
#if 0
|
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);
|
344 |
#endif
|
345 |
list = g_list_prepend(list, ret);
|
346 |
#if 0
|
347 |
fprintf(stderr,"List=%p\n",list);
|
348 |
#endif
|
349 |
|
350 |
return list;
|
351 |
}
|
352 |
|
353 |
void geom_poly_segment_destroy(struct geom_poly_segment *seg)
|
354 |
{
|
355 |
g_free(seg->first);
|
356 |
g_free(seg);
|
357 |
}
|
358 |
|
359 |
GList *
|
360 |
geom_poly_segments_remove(GList *list, struct geom_poly_segment *seg)
|
361 |
{
|
362 |
if (seg)
|
363 |
{
|
364 |
list = g_list_remove(list, seg);
|
365 |
geom_poly_segment_destroy(seg);
|
366 |
}
|
367 |
return list;
|
368 |
}
|
369 |
|
370 |
int geom_poly_segment_compatible(struct geom_poly_segment *s1, struct geom_poly_segment *s2, int dir)
|
371 |
{
|
372 |
int same = 0, opposite = 0;
|
373 |
if (s1->type == geom_poly_segment_type_none || s2->type == geom_poly_segment_type_none)
|
374 |
return 0;
|
375 |
|
376 |
if (s1->type == s2->type)
|
377 |
{
|
378 |
same = 1;
|
379 |
if (s1->type == geom_poly_segment_type_way_inner || s1->type == geom_poly_segment_type_way_outer)
|
380 |
{
|
381 |
opposite = 1;
|
382 |
}
|
383 |
}
|
384 |
|
385 |
if (s1->type == geom_poly_segment_type_way_left_side && s2->type == geom_poly_segment_type_way_right_side)
|
386 |
opposite = 1;
|
387 |
|
388 |
if (s1->type == geom_poly_segment_type_way_right_side && s2->type == geom_poly_segment_type_way_left_side)
|
389 |
opposite = 1;
|
390 |
|
391 |
if (s1->type == geom_poly_segment_type_way_unknown || s2->type == geom_poly_segment_type_way_unknown)
|
392 |
{
|
393 |
same = 1;
|
394 |
opposite = 1;
|
395 |
}
|
396 |
|
397 |
if (dir < 0)
|
398 |
{
|
399 |
if ((opposite && coord_is_equal(*s1->first, *s2->first)) || (same && coord_is_equal(*s1->first, *s2->last)))
|
400 |
return 1;
|
401 |
|
402 |
}
|
403 |
else
|
404 |
{
|
405 |
if ((opposite && coord_is_equal(*s1->last, *s2->last)) || (same && coord_is_equal(*s1->last, *s2->first)))
|
406 |
return 1;
|
407 |
|
408 |
}
|
409 |
|
410 |
return 0;
|
411 |
}
|
412 |
|
413 |
GList *
|
414 |
geom_poly_segments_sort(GList *in, enum geom_poly_segment_type type)
|
415 |
{
|
416 |
GList *ret = NULL;
|
417 |
while (in)
|
418 |
{
|
419 |
struct geom_poly_segment *seg = in->data;
|
420 |
GList *tmp = ret;
|
421 |
struct geom_poly_segment *merge_first = NULL, *merge_last = NULL;
|
422 |
|
423 |
while (tmp)
|
424 |
{
|
425 |
struct geom_poly_segment *cseg = tmp->data;
|
426 |
|
427 |
if (geom_poly_segment_compatible(seg, cseg, -1))
|
428 |
merge_first = cseg;
|
429 |
|
430 |
if (geom_poly_segment_compatible(seg, cseg, 1))
|
431 |
merge_last = cseg;
|
432 |
|
433 |
tmp = g_list_next(tmp);
|
434 |
}
|
435 |
|
436 |
if (merge_first == merge_last)
|
437 |
{
|
438 |
merge_last = NULL;
|
439 |
}
|
440 |
ret = geom_poly_segments_insert(ret, merge_first, seg, merge_last);
|
441 |
ret = geom_poly_segments_remove(ret, merge_first);
|
442 |
ret = geom_poly_segments_remove(ret, merge_last);
|
443 |
in = g_list_next(in);
|
444 |
}
|
445 |
|
446 |
in = ret;
|
447 |
while (in)
|
448 |
{
|
449 |
struct geom_poly_segment *seg = in->data;
|
450 |
if (coord_is_equal(*seg->first, *seg->last))
|
451 |
{
|
452 |
long long area = geom_poly_area(seg->first, seg->last - seg->first + 1);
|
453 |
if (type == geom_poly_segment_type_way_right_side && seg->type == geom_poly_segment_type_way_right_side)
|
454 |
{
|
455 |
seg->type = area > 0 ? geom_poly_segment_type_way_outer : geom_poly_segment_type_way_inner;
|
456 |
}
|
457 |
}
|
458 |
in = g_list_next(in);
|
459 |
}
|
460 |
return ret;
|
461 |
}
|
462 |
|
463 |
int geom_poly_segments_point_inside(GList *in, struct coord *c)
|
464 |
{
|
465 |
int open_matches = 0, closed_matches = 0;
|
466 |
struct coord *cp;
|
467 |
|
468 |
//fprintf(stderr,"point: x=%d, y=%d\n",c->x,c->y);
|
469 |
|
470 |
while (in)
|
471 |
{
|
472 |
struct geom_poly_segment *seg = in->data;
|
473 |
cp = seg->first;
|
474 |
|
475 |
//fprintf(stderr, " seg x=%d, y=%d\n", seg->first[0].x, seg->first[0].y);
|
476 |
|
477 |
if (geom_poly_point_inside(seg->first, seg->last - seg->first + 1, c))
|
478 |
{
|
479 |
#if 0
|
480 |
fprintf(stderr," inside");
|
481 |
#endif
|
482 |
if (coord_is_equal(*seg->first, *seg->last))
|
483 |
{
|
484 |
closed_matches++;
|
485 |
}
|
486 |
else
|
487 |
{
|
488 |
open_matches++;
|
489 |
}
|
490 |
}
|
491 |
else
|
492 |
{
|
493 |
#if 0
|
494 |
fprintf(stderr," outside");
|
495 |
#endif
|
496 |
}
|
497 |
in = g_list_next(in);
|
498 |
}
|
499 |
#if 0
|
500 |
fprintf(stderr,"\n");
|
501 |
fprintf(stderr,"open_matches %d closed_matches %d\n",open_matches,closed_matches);
|
502 |
#endif
|
503 |
if (closed_matches)
|
504 |
{
|
505 |
if (closed_matches & 1)
|
506 |
return 1;
|
507 |
else
|
508 |
return 0;
|
509 |
}
|
510 |
|
511 |
if (open_matches)
|
512 |
{
|
513 |
if (open_matches & 1)
|
514 |
return -1;
|
515 |
else
|
516 |
return 0;
|
517 |
}
|
518 |
return 0;
|
519 |
}
|
520 |
|
521 |
int
|
522 |
item_bin_is_closed_poly(struct item_bin *ib)
|
523 |
{
|
524 |
// int is_closed_poly = 0;
|
525 |
|
526 |
int i;
|
527 |
int count = ib->clen / 2;
|
528 |
|
529 |
if (count <= 1)
|
530 |
{
|
531 |
return 0;
|
532 |
}
|
533 |
|
534 |
struct coord *c = (struct coord *) (ib + 1);
|
535 |
//for (i = 0; i < count; i++) // loop thru all the coordinates (nodes) of this way
|
536 |
//{
|
537 |
//}
|
538 |
|
539 |
if ((c[0].x == c[count-1].x) && (c[0].y == c[count-1].y))
|
540 |
{
|
541 |
//fprintf(stderr,"%d,%d %d,%d\n", c[0].x,c[0].y,c[count-1].x,c[count-1].y);
|
542 |
// is_closed_poly = 1;
|
543 |
return 1;
|
544 |
}
|
545 |
//else
|
546 |
//{
|
547 |
// //fprintf(stderr,"%d .. %d,%d %d,%d\n", count, c[0].x,c[0].y,c[count-1].x,c[count-1].y);
|
548 |
//}
|
549 |
|
550 |
// return is_closed_poly;
|
551 |
return 0;
|
552 |
}
|
553 |
|
554 |
struct geom_poly_segment *
|
555 |
item_bin_to_poly_segment(struct item_bin *ib, int type)
|
556 |
{
|
557 |
//fprintf(stderr,"item_bin_to_poly_segment:001\n");
|
558 |
|
559 |
struct geom_poly_segment *ret=g_new(struct geom_poly_segment, 1);
|
560 |
int count = ib->clen * sizeof(int) / sizeof(struct coord);
|
561 |
|
562 |
//fprintf(stderr, "item id:%lld\n", item_bin_get_attr(ib, attr_osm_wayid, NULL));
|
563 |
//fprintf(stderr,"item_bin_to_poly_segment:count=%d\n", ib->clen);
|
564 |
|
565 |
ret->type = type;
|
566 |
ret->first=g_new(struct coord, count);
|
567 |
ret->last = ret->first + count - 1;
|
568 |
|
569 |
//fprintf(stderr,"item_bin_to_poly_segment:002.f %d %d\n", ret->first->x, ret->first->y);
|
570 |
//fprintf(stderr,"item_bin_to_poly_segment:002.l %d %d\n", ret->last->x, ret->last->y);
|
571 |
|
572 |
//fprintf(stderr,"********DUMP***********\n");
|
573 |
//dump_itembin(ib);
|
574 |
//fprintf(stderr,"********DUMP***********\n");
|
575 |
|
576 |
geom_coord_copy((struct coord *) (ib + 1), ret->first, count, 0);
|
577 |
|
578 |
//fprintf(stderr,"item_bin_to_poly_segment:099\n");
|
579 |
|
580 |
return ret;
|
581 |
}
|
582 |
|
583 |
static int clipcode(struct coord *p, struct rect *r)
|
584 |
{
|
585 |
int code = 0;
|
586 |
|
587 |
if (p->x < r->l.x)
|
588 |
code = 1;
|
589 |
if (p->x > r->h.x)
|
590 |
code = 2;
|
591 |
if (p->y < r->l.y)
|
592 |
code |= 4;
|
593 |
if (p->y > r->h.y)
|
594 |
code |= 8;
|
595 |
|
596 |
return code;
|
597 |
}
|
598 |
|
599 |
static int clip_line_code(struct coord *p1, struct coord *p2, struct rect *r)
|
600 |
{
|
601 |
int code1, code2, ret = 1;
|
602 |
long long dx, dy;
|
603 |
code1 = clipcode(p1, r);
|
604 |
|
605 |
if (code1)
|
606 |
ret |= 2;
|
607 |
|
608 |
code2 = clipcode(p2, r);
|
609 |
|
610 |
if (code2)
|
611 |
ret |= 4;
|
612 |
|
613 |
dx = p2->x - p1->x;
|
614 |
dy = p2->y - p1->y;
|
615 |
|
616 |
while (code1 || code2)
|
617 |
{
|
618 |
if (code1 & code2)
|
619 |
return 0;
|
620 |
|
621 |
if (code1 & 1)
|
622 |
{
|
623 |
p1->y += (r->l.x - p1->x) * dy / dx;
|
624 |
p1->x = r->l.x;
|
625 |
}
|
626 |
else if (code1 & 2)
|
627 |
{
|
628 |
p1->y += (r->h.x - p1->x) * dy / dx;
|
629 |
p1->x = r->h.x;
|
630 |
}
|
631 |
else if (code1 & 4)
|
632 |
{
|
633 |
p1->x += (r->l.y - p1->y) * dx / dy;
|
634 |
p1->y = r->l.y;
|
635 |
}
|
636 |
else if (code1 & 8)
|
637 |
{
|
638 |
p1->x += (r->h.y - p1->y) * dx / dy;
|
639 |
p1->y = r->h.y;
|
640 |
}
|
641 |
|
642 |
code1 = clipcode(p1, r);
|
643 |
|
644 |
if (code1 & code2)
|
645 |
return 0;
|
646 |
|
647 |
if (code2 & 1)
|
648 |
{
|
649 |
p2->y += (r->l.x - p2->x) * dy / dx;
|
650 |
p2->x = r->l.x;
|
651 |
}
|
652 |
else if (code2 & 2)
|
653 |
{
|
654 |
p2->y += (r->h.x - p2->x) * dy / dx;
|
655 |
p2->x = r->h.x;
|
656 |
}
|
657 |
else if (code2 & 4)
|
658 |
{
|
659 |
p2->x += (r->l.y - p2->y) * dx / dy;
|
660 |
p2->y = r->l.y;
|
661 |
}
|
662 |
else if (code2 & 8)
|
663 |
{
|
664 |
p2->x += (r->h.y - p2->y) * dx / dy;
|
665 |
p2->y = r->h.y;
|
666 |
}
|
667 |
|
668 |
code2 = clipcode(p2, r);
|
669 |
|
670 |
}
|
671 |
|
672 |
if (p1->x == p2->x && p1->y == p2->y)
|
673 |
ret = 0;
|
674 |
|
675 |
return ret;
|
676 |
}
|
677 |
|
678 |
void clip_line(struct item_bin *ib, struct rect *r, struct tile_parameter *param, struct item_bin_sink *out)
|
679 |
{
|
680 |
char *buffer = g_alloca(sizeof(char) * (ib->len * 4 + 32));
|
681 |
struct item_bin *ib_new = (struct item_bin *) buffer;
|
682 |
struct coord *pa = (struct coord *) (ib + 1);
|
683 |
int count = ib->clen / 2;
|
684 |
struct coord p1, p2;
|
685 |
int i, code;
|
686 |
item_bin_init(ib_new, ib->type);
|
687 |
|
688 |
for (i = 0; i < count; i++)
|
689 |
{
|
690 |
if (i)
|
691 |
{
|
692 |
p1.x = pa[i - 1].x;
|
693 |
p1.y = pa[i - 1].y;
|
694 |
p2.x = pa[i].x;
|
695 |
p2.y = pa[i].y;
|
696 |
/* 0 = invisible, 1 = completely visible, 3 = start point clipped, 5 = end point clipped, 7 both points clipped */
|
697 |
code = clip_line_code(&p1, &p2, r);
|
698 |
#if 1
|
699 |
if (((code == 1 || code == 5) && ib_new->clen == 0) || (code & 2))
|
700 |
{
|
701 |
item_bin_add_coord(ib_new, &p1, 1);
|
702 |
}
|
703 |
|
704 |
if (code)
|
705 |
{
|
706 |
item_bin_add_coord(ib_new, &p2, 1);
|
707 |
}
|
708 |
|
709 |
if (i == count - 1 || (code & 4))
|
710 |
{
|
711 |
if (ib_new->clen)
|
712 |
item_bin_write_clipped(ib_new, param, out);
|
713 |
|
714 |
item_bin_init(ib_new, ib->type);
|
715 |
}
|
716 |
#else
|
717 |
if (code)
|
718 |
{
|
719 |
item_bin_init(ib_new, ib->type);
|
720 |
item_bin_add_coord(ib_new, &p1, 1);
|
721 |
item_bin_add_coord(ib_new, &p2, 1);
|
722 |
item_bin_write_clipped(ib_new, param, out);
|
723 |
}
|
724 |
#endif
|
725 |
}
|
726 |
}
|
727 |
}
|
728 |
|
729 |
static int is_inside(struct coord *p, struct rect *r, int edge)
|
730 |
{
|
731 |
switch (edge)
|
732 |
{
|
733 |
case 0:
|
734 |
return p->x >= r->l.x;
|
735 |
case 1:
|
736 |
return p->x <= r->h.x;
|
737 |
case 2:
|
738 |
return p->y >= r->l.y;
|
739 |
case 3:
|
740 |
return p->y <= r->h.y;
|
741 |
default:
|
742 |
return 0;
|
743 |
}
|
744 |
}
|
745 |
|
746 |
static void poly_intersection(struct coord *p1, struct coord *p2, struct rect *r, int edge, struct coord *ret)
|
747 |
{
|
748 |
int dx = p2->x - p1->x;
|
749 |
int dy = p2->y - p1->y;
|
750 |
switch (edge)
|
751 |
{
|
752 |
case 0:
|
753 |
ret->y = p1->y + (r->l.x - p1->x) * dy / dx;
|
754 |
ret->x = r->l.x;
|
755 |
break;
|
756 |
case 1:
|
757 |
ret->y = p1->y + (r->h.x - p1->x) * dy / dx;
|
758 |
ret->x = r->h.x;
|
759 |
break;
|
760 |
case 2:
|
761 |
ret->x = p1->x + (r->l.y - p1->y) * dx / dy;
|
762 |
ret->y = r->l.y;
|
763 |
break;
|
764 |
case 3:
|
765 |
ret->x = p1->x + (r->h.y - p1->y) * dx / dy;
|
766 |
ret->y = r->h.y;
|
767 |
break;
|
768 |
}
|
769 |
}
|
770 |
|
771 |
void clip_polygon(struct item_bin *ib, struct rect *r, struct tile_parameter *param, struct item_bin_sink *out)
|
772 |
{
|
773 |
int count_in = ib->clen / 2;
|
774 |
struct coord *pin, *p, *s, pi;
|
775 |
char *buffer1 = g_alloca(sizeof(char) * (ib->len * 4 + ib->clen * 7 + 32));
|
776 |
struct item_bin *ib1 = (struct item_bin *) buffer1;
|
777 |
char *buffer2 = g_alloca(sizeof(char) * (ib->len * 4 + ib->clen * 7 + 32));
|
778 |
struct item_bin *ib2 = (struct item_bin *) buffer2;
|
779 |
struct item_bin *ib_in, *ib_out;
|
780 |
int edge, i;
|
781 |
ib_out = ib1;
|
782 |
ib_in = ib;
|
783 |
for (edge = 0; edge < 4; edge++)
|
784 |
{
|
785 |
count_in = ib_in->clen / 2;
|
786 |
pin = (struct coord *) (ib_in + 1);
|
787 |
p = pin;
|
788 |
s = pin + count_in - 1;
|
789 |
item_bin_init(ib_out, ib_in->type);
|
790 |
for (i = 0; i < count_in; i++)
|
791 |
{
|
792 |
if (is_inside(p, r, edge))
|
793 |
{
|
794 |
if (!is_inside(s, r, edge))
|
795 |
{
|
796 |
poly_intersection(s, p, r, edge, &pi);
|
797 |
item_bin_add_coord(ib_out, &pi, 1);
|
798 |
}
|
799 |
item_bin_add_coord(ib_out, p, 1);
|
800 |
}
|
801 |
else
|
802 |
{
|
803 |
if (is_inside(s, r, edge))
|
804 |
{
|
805 |
poly_intersection(p, s, r, edge, &pi);
|
806 |
item_bin_add_coord(ib_out, &pi, 1);
|
807 |
}
|
808 |
}
|
809 |
s = p;
|
810 |
p++;
|
811 |
}
|
812 |
if (ib_in == ib1)
|
813 |
{
|
814 |
ib_in = ib2;
|
815 |
ib_out = ib1;
|
816 |
}
|
817 |
else
|
818 |
{
|
819 |
ib_in = ib1;
|
820 |
ib_out = ib2;
|
821 |
}
|
822 |
}
|
823 |
if (ib_in->clen)
|
824 |
item_bin_write_clipped(ib_in, param, out);
|
825 |
}
|
826 |
|
827 |
|