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 |
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 |
*/
|
253 |
int
|
254 |
geom_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 |
|
276 |
|
277 |
GList *
|
278 |
geom_poly_segments_insert(GList *list, struct geom_poly_segment *first, struct geom_poly_segment *second, struct geom_poly_segment *third)
|
279 |
{
|
280 |
int count;
|
281 |
struct geom_poly_segment *ret;
|
282 |
struct coord *pos;
|
283 |
|
284 |
if (!second)
|
285 |
return NULL; ret=g_new(struct geom_poly_segment, 1);
|
286 |
ret->type = second->type;
|
287 |
count = (second->last - second->first) + 1;
|
288 |
if (first)
|
289 |
count += (first->last - first->first);
|
290 |
if (third)
|
291 |
count += (third->last - third->first);
|
292 |
#if 0
|
293 |
fprintf(stderr,"count=%d first=%p second=%p third=%p\n",count,first,second,third);
|
294 |
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);
|
296 |
if (second)
|
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);
|
298 |
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);
|
300 |
#endif
|
301 |
ret->first=g_new(struct coord, count);
|
302 |
pos = ret->first;
|
303 |
if (first)
|
304 |
{
|
305 |
count = (first->last - first->first) + 1;
|
306 |
geom_coord_copy(first->first, pos, count, coord_is_equal(*first->first, *second->first));
|
307 |
pos += count - 1;
|
308 |
}
|
309 |
count = (second->last - second->first) + 1;
|
310 |
geom_coord_copy(second->first, pos, count, 0);
|
311 |
pos += count;
|
312 |
if (third)
|
313 |
{
|
314 |
pos--;
|
315 |
count = (third->last - third->first) + 1;
|
316 |
geom_coord_copy(third->first, pos, count, coord_is_equal(*third->last, *second->last));
|
317 |
pos += count;
|
318 |
}
|
319 |
ret->last = pos - 1;
|
320 |
#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);
|
322 |
#endif
|
323 |
list = g_list_prepend(list, ret);
|
324 |
#if 0
|
325 |
fprintf(stderr,"List=%p\n",list);
|
326 |
#endif
|
327 |
return list;
|
328 |
}
|
329 |
|
330 |
void geom_poly_segment_destroy(struct geom_poly_segment *seg)
|
331 |
{
|
332 |
g_free(seg->first);
|
333 |
g_free(seg);
|
334 |
}
|
335 |
|
336 |
GList *
|
337 |
geom_poly_segments_remove(GList *list, struct geom_poly_segment *seg)
|
338 |
{
|
339 |
if (seg)
|
340 |
{
|
341 |
list = g_list_remove(list, seg);
|
342 |
geom_poly_segment_destroy(seg);
|
343 |
}
|
344 |
return list;
|
345 |
}
|
346 |
|
347 |
int geom_poly_segment_compatible(struct geom_poly_segment *s1, struct geom_poly_segment *s2, int dir)
|
348 |
{
|
349 |
int same = 0, opposite = 0;
|
350 |
if (s1->type == geom_poly_segment_type_none || s2->type == geom_poly_segment_type_none)
|
351 |
return 0;
|
352 |
if (s1->type == s2->type)
|
353 |
{
|
354 |
same = 1;
|
355 |
if (s1->type == geom_poly_segment_type_way_inner || s1->type == geom_poly_segment_type_way_outer)
|
356 |
{
|
357 |
opposite = 1;
|
358 |
}
|
359 |
}
|
360 |
if (s1->type == geom_poly_segment_type_way_left_side && s2->type == geom_poly_segment_type_way_right_side)
|
361 |
opposite = 1;
|
362 |
if (s1->type == geom_poly_segment_type_way_right_side && s2->type == geom_poly_segment_type_way_left_side)
|
363 |
opposite = 1;
|
364 |
if (s1->type == geom_poly_segment_type_way_unknown || s2->type == geom_poly_segment_type_way_unknown)
|
365 |
{
|
366 |
same = 1;
|
367 |
opposite = 1;
|
368 |
}
|
369 |
if (dir < 0)
|
370 |
{
|
371 |
if ((opposite && coord_is_equal(*s1->first, *s2->first)) || (same && coord_is_equal(*s1->first, *s2->last)))
|
372 |
return 1;
|
373 |
}
|
374 |
else
|
375 |
{
|
376 |
if ((opposite && coord_is_equal(*s1->last, *s2->last)) || (same && coord_is_equal(*s1->last, *s2->first)))
|
377 |
return 1;
|
378 |
}
|
379 |
return 0;
|
380 |
}
|
381 |
|
382 |
GList *
|
383 |
geom_poly_segments_sort(GList *in, enum geom_poly_segment_type type)
|
384 |
{
|
385 |
GList *ret = NULL;
|
386 |
while (in)
|
387 |
{
|
388 |
struct geom_poly_segment *seg = in->data;
|
389 |
GList *tmp = ret;
|
390 |
struct geom_poly_segment *merge_first = NULL, *merge_last = NULL;
|
391 |
while (tmp)
|
392 |
{
|
393 |
struct geom_poly_segment *cseg = tmp->data;
|
394 |
if (geom_poly_segment_compatible(seg, cseg, -1))
|
395 |
merge_first = cseg;
|
396 |
if (geom_poly_segment_compatible(seg, cseg, 1))
|
397 |
merge_last = cseg;
|
398 |
tmp = g_list_next(tmp);
|
399 |
}
|
400 |
if (merge_first == merge_last)
|
401 |
{
|
402 |
merge_last = NULL;
|
403 |
}
|
404 |
ret = geom_poly_segments_insert(ret, merge_first, seg, merge_last);
|
405 |
ret = geom_poly_segments_remove(ret, merge_first);
|
406 |
ret = geom_poly_segments_remove(ret, merge_last);
|
407 |
in = g_list_next(in);
|
408 |
}
|
409 |
|
410 |
in = ret;
|
411 |
while (in)
|
412 |
{
|
413 |
struct geom_poly_segment *seg = in->data;
|
414 |
if (coord_is_equal(*seg->first, *seg->last))
|
415 |
{
|
416 |
long long area = geom_poly_area(seg->first, seg->last - seg->first + 1);
|
417 |
if (type == geom_poly_segment_type_way_right_side && seg->type == geom_poly_segment_type_way_right_side)
|
418 |
{
|
419 |
seg->type = area > 0 ? geom_poly_segment_type_way_outer : geom_poly_segment_type_way_inner;
|
420 |
}
|
421 |
}
|
422 |
in = g_list_next(in);
|
423 |
}
|
424 |
return ret;
|
425 |
}
|
426 |
|
427 |
int 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 |
|
484 |
int
|
485 |
item_bin_is_closed_poly(struct item_bin *ib)
|
486 |
{
|
487 |
// int is_closed_poly = 0;
|
488 |
|
489 |
int i;
|
490 |
int count = ib->clen / 2;
|
491 |
if (count <= 1)
|
492 |
{
|
493 |
return 0;
|
494 |
}
|
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;
|
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;
|
513 |
return 0;
|
514 |
}
|
515 |
|
516 |
struct geom_poly_segment *
|
517 |
item_bin_to_poly_segment(struct item_bin *ib, int type)
|
518 |
{
|
519 |
//fprintf(stderr,"item_bin_to_poly_segment:001\n");
|
520 |
|
521 |
struct geom_poly_segment *ret=g_new(struct geom_poly_segment, 1);
|
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 |
|
527 |
ret->type = type;
|
528 |
ret->first=g_new(struct coord, count);
|
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 |
|
538 |
geom_coord_copy((struct coord *) (ib + 1), ret->first, count, 0);
|
539 |
|
540 |
//fprintf(stderr,"item_bin_to_poly_segment:099\n");
|
541 |
|
542 |
return ret;
|
543 |
}
|
544 |
|
545 |
static int clipcode(struct coord *p, struct rect *r)
|
546 |
{
|
547 |
int code = 0;
|
548 |
if (p->x < r->l.x)
|
549 |
code = 1;
|
550 |
if (p->x > r->h.x)
|
551 |
code = 2;
|
552 |
if (p->y < r->l.y)
|
553 |
code |= 4;
|
554 |
if (p->y > r->h.y)
|
555 |
code |= 8;
|
556 |
return code;
|
557 |
}
|
558 |
|
559 |
static int clip_line_code(struct coord *p1, struct coord *p2, struct rect *r)
|
560 |
{
|
561 |
int code1, code2, ret = 1;
|
562 |
long long dx, dy;
|
563 |
code1 = clipcode(p1, r);
|
564 |
if (code1)
|
565 |
ret |= 2;
|
566 |
code2 = clipcode(p2, r);
|
567 |
if (code2)
|
568 |
ret |= 4;
|
569 |
dx = p2->x - p1->x;
|
570 |
dy = p2->y - p1->y;
|
571 |
while (code1 || code2)
|
572 |
{
|
573 |
if (code1 & code2)
|
574 |
return 0;
|
575 |
if (code1 & 1)
|
576 |
{
|
577 |
p1->y += (r->l.x - p1->x) * dy / dx;
|
578 |
p1->x = r->l.x;
|
579 |
}
|
580 |
else if (code1 & 2)
|
581 |
{
|
582 |
p1->y += (r->h.x - p1->x) * dy / dx;
|
583 |
p1->x = r->h.x;
|
584 |
}
|
585 |
else if (code1 & 4)
|
586 |
{
|
587 |
p1->x += (r->l.y - p1->y) * dx / dy;
|
588 |
p1->y = r->l.y;
|
589 |
}
|
590 |
else if (code1 & 8)
|
591 |
{
|
592 |
p1->x += (r->h.y - p1->y) * dx / dy;
|
593 |
p1->y = r->h.y;
|
594 |
}
|
595 |
code1 = clipcode(p1, r);
|
596 |
if (code1 & code2)
|
597 |
return 0;
|
598 |
if (code2 & 1)
|
599 |
{
|
600 |
p2->y += (r->l.x - p2->x) * dy / dx;
|
601 |
p2->x = r->l.x;
|
602 |
}
|
603 |
else if (code2 & 2)
|
604 |
{
|
605 |
p2->y += (r->h.x - p2->x) * dy / dx;
|
606 |
p2->x = r->h.x;
|
607 |
}
|
608 |
else if (code2 & 4)
|
609 |
{
|
610 |
p2->x += (r->l.y - p2->y) * dx / dy;
|
611 |
p2->y = r->l.y;
|
612 |
}
|
613 |
else if (code2 & 8)
|
614 |
{
|
615 |
p2->x += (r->h.y - p2->y) * dx / dy;
|
616 |
p2->y = r->h.y;
|
617 |
}
|
618 |
code2 = clipcode(p2, r);
|
619 |
}
|
620 |
if (p1->x == p2->x && p1->y == p2->y)
|
621 |
ret = 0;
|
622 |
return ret;
|
623 |
}
|
624 |
|
625 |
void clip_line(struct item_bin *ib, struct rect *r, struct tile_parameter *param, struct item_bin_sink *out)
|
626 |
{
|
627 |
char *buffer = g_alloca(sizeof(char) * (ib->len * 4 + 32));
|
628 |
struct item_bin *ib_new = (struct item_bin *) buffer;
|
629 |
struct coord *pa = (struct coord *) (ib + 1);
|
630 |
int count = ib->clen / 2;
|
631 |
struct coord p1, p2;
|
632 |
int i, code;
|
633 |
item_bin_init(ib_new, ib->type);
|
634 |
for (i = 0; i < count; i++)
|
635 |
{
|
636 |
if (i)
|
637 |
{
|
638 |
p1.x = pa[i - 1].x;
|
639 |
p1.y = pa[i - 1].y;
|
640 |
p2.x = pa[i].x;
|
641 |
p2.y = pa[i].y;
|
642 |
/* 0 = invisible, 1 = completely visible, 3 = start point clipped, 5 = end point clipped, 7 both points clipped */
|
643 |
code = clip_line_code(&p1, &p2, r);
|
644 |
#if 1
|
645 |
if (((code == 1 || code == 5) && ib_new->clen == 0) || (code & 2))
|
646 |
{
|
647 |
item_bin_add_coord(ib_new, &p1, 1);
|
648 |
}
|
649 |
if (code)
|
650 |
{
|
651 |
item_bin_add_coord(ib_new, &p2, 1);
|
652 |
}
|
653 |
if (i == count - 1 || (code & 4))
|
654 |
{
|
655 |
if (ib_new->clen)
|
656 |
item_bin_write_clipped(ib_new, param, out);
|
657 |
item_bin_init(ib_new, ib->type);
|
658 |
}
|
659 |
#else
|
660 |
if (code)
|
661 |
{
|
662 |
item_bin_init(ib_new, ib->type);
|
663 |
item_bin_add_coord(ib_new, &p1, 1);
|
664 |
item_bin_add_coord(ib_new, &p2, 1);
|
665 |
item_bin_write_clipped(ib_new, param, out);
|
666 |
}
|
667 |
#endif
|
668 |
}
|
669 |
}
|
670 |
}
|
671 |
|
672 |
static int is_inside(struct coord *p, struct rect *r, int edge)
|
673 |
{
|
674 |
switch (edge)
|
675 |
{
|
676 |
case 0:
|
677 |
return p->x >= r->l.x;
|
678 |
case 1:
|
679 |
return p->x <= r->h.x;
|
680 |
case 2:
|
681 |
return p->y >= r->l.y;
|
682 |
case 3:
|
683 |
return p->y <= r->h.y;
|
684 |
default:
|
685 |
return 0;
|
686 |
}
|
687 |
}
|
688 |
|
689 |
static void poly_intersection(struct coord *p1, struct coord *p2, struct rect *r, int edge, struct coord *ret)
|
690 |
{
|
691 |
int dx = p2->x - p1->x;
|
692 |
int dy = p2->y - p1->y;
|
693 |
switch (edge)
|
694 |
{
|
695 |
case 0:
|
696 |
ret->y = p1->y + (r->l.x - p1->x) * dy / dx;
|
697 |
ret->x = r->l.x;
|
698 |
break;
|
699 |
case 1:
|
700 |
ret->y = p1->y + (r->h.x - p1->x) * dy / dx;
|
701 |
ret->x = r->h.x;
|
702 |
break;
|
703 |
case 2:
|
704 |
ret->x = p1->x + (r->l.y - p1->y) * dx / dy;
|
705 |
ret->y = r->l.y;
|
706 |
break;
|
707 |
case 3:
|
708 |
ret->x = p1->x + (r->h.y - p1->y) * dx / dy;
|
709 |
ret->y = r->h.y;
|
710 |
break;
|
711 |
}
|
712 |
}
|
713 |
|
714 |
void clip_polygon(struct item_bin *ib, struct rect *r, struct tile_parameter *param, struct item_bin_sink *out)
|
715 |
{
|
716 |
int count_in = ib->clen / 2;
|
717 |
struct coord *pin, *p, *s, pi;
|
718 |
char *buffer1 = g_alloca(sizeof(char) * (ib->len * 4 + ib->clen * 7 + 32));
|
719 |
struct item_bin *ib1 = (struct item_bin *) buffer1;
|
720 |
char *buffer2 = g_alloca(sizeof(char) * (ib->len * 4 + ib->clen * 7 + 32));
|
721 |
struct item_bin *ib2 = (struct item_bin *) buffer2;
|
722 |
struct item_bin *ib_in, *ib_out;
|
723 |
int edge, i;
|
724 |
ib_out = ib1;
|
725 |
ib_in = ib;
|
726 |
for (edge = 0; edge < 4; edge++)
|
727 |
{
|
728 |
count_in = ib_in->clen / 2;
|
729 |
pin = (struct coord *) (ib_in + 1);
|
730 |
p = pin;
|
731 |
s = pin + count_in - 1;
|
732 |
item_bin_init(ib_out, ib_in->type);
|
733 |
for (i = 0; i < count_in; i++)
|
734 |
{
|
735 |
if (is_inside(p, r, edge))
|
736 |
{
|
737 |
if (!is_inside(s, r, edge))
|
738 |
{
|
739 |
poly_intersection(s, p, r, edge, &pi);
|
740 |
item_bin_add_coord(ib_out, &pi, 1);
|
741 |
}
|
742 |
item_bin_add_coord(ib_out, p, 1);
|
743 |
}
|
744 |
else
|
745 |
{
|
746 |
if (is_inside(s, r, edge))
|
747 |
{
|
748 |
poly_intersection(p, s, r, edge, &pi);
|
749 |
item_bin_add_coord(ib_out, &pi, 1);
|
750 |
}
|
751 |
}
|
752 |
s = p;
|
753 |
p++;
|
754 |
}
|
755 |
if (ib_in == ib1)
|
756 |
{
|
757 |
ib_in = ib2;
|
758 |
ib_out = ib1;
|
759 |
}
|
760 |
else
|
761 |
{
|
762 |
ib_in = ib1;
|
763 |
ib_out = ib2;
|
764 |
}
|
765 |
}
|
766 |
if (ib_in->clen)
|
767 |
item_bin_write_clipped(ib_in, param, out);
|
768 |
}
|
769 |
|