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

Contents of /navit/navit/maptool/geom.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 57 - (hide annotations) (download)
Sun Mar 19 16:46:08 2017 UTC (4 years ago) by zoff99
File MIME type: text/plain
File size: 17966 byte(s)
updates
1 zoff99 8 /**
2 zoff99 37 * 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 zoff99 8 * 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 zoff99 36 #include <math.h>
40 zoff99 8 #include "maptool.h"
41    
42 zoff99 37 void geom_coord_copy(struct coord *from, struct coord *to, int count, int reverse)
43 zoff99 8 {
44     int i;
45 zoff99 37 if (!reverse)
46     {
47     memcpy(to, from, count * sizeof(struct coord));
48 zoff99 8 return;
49     }
50 zoff99 37 from += count;
51     for (i = 0; i < count; i++)
52     {
53     *to++ = *--from;
54     }
55 zoff99 8 }
56    
57 zoff99 37
58 zoff99 36 /**
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 zoff99 37 int geom_line_middle(struct coord *p, int count, struct coord *c)
66 zoff99 36 {
67 zoff99 37 double length = 0, half = 0, len = 0;
68 zoff99 36 int i;
69    
70 zoff99 37 if (count == 1)
71     {
72 zoff99 36 *c=*p;
73     return 0;
74     }
75    
76 zoff99 37 for (i=0; i<count-1; i++)
77     {
78 zoff99 36 length+=sqrt(sq(p[i].x-p[i+1].x)+sq(p[i].y-p[i+1].y));
79     }
80    
81 zoff99 37 length /= 2;
82     for (i=0; (i<count-1) && (half<length); i++)
83     {
84 zoff99 36 len=sqrt(sq(p[i].x-p[i+1].x)+sq(p[i].y-p[i+1].y));
85 zoff99 37 half += len;
86 zoff99 36 }
87 zoff99 37
88     if (i > 0)
89     {
90 zoff99 36 i--;
91 zoff99 37 half -= length;
92     if (len)
93     {
94 zoff99 36 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 zoff99 37 }
97     else
98     {
99     *c = p[i];
100     }
101     }
102     else
103     {
104     *c = p[0];
105     }
106    
107 zoff99 36 return i;
108     }
109    
110 zoff99 37 void geom_coord_revert(struct coord *c, int count)
111 zoff99 8 {
112 zoff99 34 struct coord tmp;
113 zoff99 31 int i;
114    
115 zoff99 37 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 zoff99 31 }
121     }
122    
123 zoff99 37 long long geom_poly_area(struct coord *c, int count)
124 zoff99 8 {
125 zoff99 37 long long area = 0;
126     int i, j = 0;
127 zoff99 8 #if 0
128     fprintf(stderr,"count=%d\n",count);
129     #endif
130 zoff99 37 for (i = 0; i < count; i++)
131     {
132 zoff99 8 if (++j == count)
133 zoff99 37 j = 0;
134 zoff99 8 #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 zoff99 37 area += (long long) (c[i].x + c[j].x) * (c[i].y - c[j].y);
138 zoff99 8 #if 0
139     fprintf(stderr,"area="LONGLONG_FMT"\n",area);
140     #endif
141     }
142 zoff99 37 return area / 2;
143 zoff99 8 }
144    
145 zoff99 36 /**
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 zoff99 37
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 zoff99 36 */
158     int
159     geom_poly_centroid(struct coord *p, int count, struct coord *c)
160     {
161 zoff99 37 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 zoff99 36 return 1;
194     }
195 zoff99 37 c->x = x0;
196     c->y = y0;
197    
198 zoff99 36 return 0;
199     }
200    
201 zoff99 37
202 zoff99 36 /**
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 zoff99 57
216     if (count<2)
217     {
218 zoff99 36 c->x=pl->x;
219     c->y=pl->y;
220     return 0;
221     }
222 zoff99 57
223     for (i=0;i<count-1;i++)
224     {
225 zoff99 36 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 zoff99 57
231     if(u!=0)
232     {
233 zoff99 36 u=((p->x-xi)*(xj-xi)+(p->y-yi)*(yj-yi))*1000/u;
234     }
235 zoff99 57
236     if(u<0)
237     {
238 zoff99 36 u=0;
239 zoff99 57 }
240     else if (u>1000)
241     {
242 zoff99 36 u=1000;
243 zoff99 57 }
244    
245 zoff99 36 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 zoff99 57
249     if (i==0 || d<dmin)
250     {
251 zoff99 36 dmin=d;
252     c->x=x;
253     c->y=y;
254     vertex=i;
255     }
256     }
257 zoff99 57
258 zoff99 36 return vertex;
259     }
260    
261     /**
262 zoff99 37 * Check if point is inside polygon
263 zoff99 36 * @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 zoff99 37 while (cp < last)
274     {
275 zoff99 36 if ((cp[0].y > c->y) != (cp[1].y > c->y) &&
276 zoff99 37 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 zoff99 36 #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 zoff99 8 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 zoff99 37 return NULL; ret=g_new(struct geom_poly_segment, 1);
301 zoff99 57
302 zoff99 37 ret->type = second->type;
303     count = (second->last - second->first) + 1;
304     if (first)
305     count += (first->last - first->first);
306 zoff99 57
307 zoff99 8 if (third)
308 zoff99 37 count += (third->last - third->first);
309 zoff99 57
310 zoff99 8 #if 0
311 zoff99 37 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 zoff99 8 #endif
319     ret->first=g_new(struct coord, count);
320 zoff99 37 pos = ret->first;
321 zoff99 57
322 zoff99 37 if (first)
323     {
324     count = (first->last - first->first) + 1;
325 zoff99 8 geom_coord_copy(first->first, pos, count, coord_is_equal(*first->first, *second->first));
326 zoff99 37 pos += count - 1;
327 zoff99 8 }
328 zoff99 57
329 zoff99 37 count = (second->last - second->first) + 1;
330 zoff99 8 geom_coord_copy(second->first, pos, count, 0);
331 zoff99 37 pos += count;
332 zoff99 57
333 zoff99 37 if (third)
334     {
335 zoff99 8 pos--;
336 zoff99 37 count = (third->last - third->first) + 1;
337 zoff99 8 geom_coord_copy(third->first, pos, count, coord_is_equal(*third->last, *second->last));
338 zoff99 37 pos += count;
339 zoff99 8 }
340 zoff99 57
341 zoff99 37 ret->last = pos - 1;
342 zoff99 8 #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 zoff99 37 list = g_list_prepend(list, ret);
346 zoff99 8 #if 0
347     fprintf(stderr,"List=%p\n",list);
348     #endif
349 zoff99 57
350 zoff99 8 return list;
351     }
352    
353 zoff99 37 void geom_poly_segment_destroy(struct geom_poly_segment *seg)
354 zoff99 8 {
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 zoff99 37 if (seg)
363     {
364     list = g_list_remove(list, seg);
365 zoff99 8 geom_poly_segment_destroy(seg);
366     }
367     return list;
368     }
369    
370 zoff99 37 int geom_poly_segment_compatible(struct geom_poly_segment *s1, struct geom_poly_segment *s2, int dir)
371 zoff99 8 {
372 zoff99 37 int same = 0, opposite = 0;
373 zoff99 8 if (s1->type == geom_poly_segment_type_none || s2->type == geom_poly_segment_type_none)
374     return 0;
375 zoff99 57
376 zoff99 37 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 zoff99 36 }
383     }
384 zoff99 57
385 zoff99 8 if (s1->type == geom_poly_segment_type_way_left_side && s2->type == geom_poly_segment_type_way_right_side)
386 zoff99 37 opposite = 1;
387 zoff99 57
388 zoff99 8 if (s1->type == geom_poly_segment_type_way_right_side && s2->type == geom_poly_segment_type_way_left_side)
389 zoff99 37 opposite = 1;
390 zoff99 57
391 zoff99 37 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 zoff99 8 }
396 zoff99 57
397 zoff99 37 if (dir < 0)
398     {
399     if ((opposite && coord_is_equal(*s1->first, *s2->first)) || (same && coord_is_equal(*s1->first, *s2->last)))
400 zoff99 8 return 1;
401 zoff99 57
402 zoff99 37 }
403     else
404     {
405     if ((opposite && coord_is_equal(*s1->last, *s2->last)) || (same && coord_is_equal(*s1->last, *s2->first)))
406 zoff99 8 return 1;
407 zoff99 57
408 zoff99 8 }
409 zoff99 57
410 zoff99 8 return 0;
411     }
412    
413     GList *
414     geom_poly_segments_sort(GList *in, enum geom_poly_segment_type type)
415     {
416 zoff99 37 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 zoff99 57
423 zoff99 37 while (tmp)
424     {
425     struct geom_poly_segment *cseg = tmp->data;
426 zoff99 57
427 zoff99 8 if (geom_poly_segment_compatible(seg, cseg, -1))
428 zoff99 37 merge_first = cseg;
429 zoff99 57
430 zoff99 8 if (geom_poly_segment_compatible(seg, cseg, 1))
431 zoff99 37 merge_last = cseg;
432 zoff99 57
433 zoff99 37 tmp = g_list_next(tmp);
434 zoff99 8 }
435 zoff99 57
436 zoff99 8 if (merge_first == merge_last)
437 zoff99 37 {
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 zoff99 8 }
445 zoff99 37
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 zoff99 8 }
457     }
458 zoff99 37 in = g_list_next(in);
459 zoff99 8 }
460     return ret;
461     }
462    
463 zoff99 37 int geom_poly_segments_point_inside(GList *in, struct coord *c)
464 zoff99 8 {
465 zoff99 37 int open_matches = 0, closed_matches = 0;
466 zoff99 8 struct coord *cp;
467 zoff99 37
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 zoff99 36 #if 0
480     fprintf(stderr," inside");
481     #endif
482 zoff99 37 if (coord_is_equal(*seg->first, *seg->last))
483     {
484 zoff99 36 closed_matches++;
485 zoff99 37 }
486 zoff99 36 else
487 zoff99 37 {
488 zoff99 36 open_matches++;
489 zoff99 37 }
490     }
491     else
492     {
493 zoff99 36 #if 0
494     fprintf(stderr," outside");
495     #endif
496 zoff99 8 }
497 zoff99 37 in = g_list_next(in);
498 zoff99 8 }
499 zoff99 36 #if 0
500     fprintf(stderr,"\n");
501     fprintf(stderr,"open_matches %d closed_matches %d\n",open_matches,closed_matches);
502     #endif
503 zoff99 37 if (closed_matches)
504     {
505 zoff99 36 if (closed_matches & 1)
506     return 1;
507     else
508     return 0;
509     }
510 zoff99 57
511 zoff99 37 if (open_matches)
512     {
513 zoff99 36 if (open_matches & 1)
514     return -1;
515     else
516     return 0;
517     }
518     return 0;
519 zoff99 8 }
520    
521 zoff99 37 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 zoff99 57
529     if (count <= 1)
530 zoff99 37 {
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 zoff99 8 struct geom_poly_segment *
555     item_bin_to_poly_segment(struct item_bin *ib, int type)
556     {
557 zoff99 37 //fprintf(stderr,"item_bin_to_poly_segment:001\n");
558    
559 zoff99 8 struct geom_poly_segment *ret=g_new(struct geom_poly_segment, 1);
560 zoff99 37 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 zoff99 8 ret->first=g_new(struct coord, count);
567 zoff99 37 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 zoff99 8 return ret;
581     }
582    
583 zoff99 37 static int clipcode(struct coord *p, struct rect *r)
584 zoff99 8 {
585 zoff99 37 int code = 0;
586 zoff99 57
587 zoff99 8 if (p->x < r->l.x)
588 zoff99 37 code = 1;
589 zoff99 8 if (p->x > r->h.x)
590 zoff99 37 code = 2;
591 zoff99 8 if (p->y < r->l.y)
592 zoff99 37 code |= 4;
593 zoff99 8 if (p->y > r->h.y)
594 zoff99 37 code |= 8;
595 zoff99 57
596 zoff99 8 return code;
597     }
598    
599 zoff99 37 static int clip_line_code(struct coord *p1, struct coord *p2, struct rect *r)
600 zoff99 8 {
601 zoff99 37 int code1, code2, ret = 1;
602     long long dx, dy;
603     code1 = clipcode(p1, r);
604 zoff99 57
605 zoff99 8 if (code1)
606     ret |= 2;
607 zoff99 57
608 zoff99 37 code2 = clipcode(p2, r);
609 zoff99 57
610 zoff99 8 if (code2)
611     ret |= 4;
612 zoff99 57
613 zoff99 37 dx = p2->x - p1->x;
614     dy = p2->y - p1->y;
615 zoff99 57
616 zoff99 37 while (code1 || code2)
617     {
618 zoff99 8 if (code1 & code2)
619     return 0;
620 zoff99 57
621 zoff99 37 if (code1 & 1)
622     {
623     p1->y += (r->l.x - p1->x) * dy / dx;
624     p1->x = r->l.x;
625 zoff99 8 }
626 zoff99 37 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 zoff99 57
642 zoff99 37 code1 = clipcode(p1, r);
643 zoff99 57
644 zoff99 8 if (code1 & code2)
645     return 0;
646 zoff99 57
647 zoff99 37 if (code2 & 1)
648     {
649     p2->y += (r->l.x - p2->x) * dy / dx;
650     p2->x = r->l.x;
651 zoff99 8 }
652 zoff99 37 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 zoff99 57
668 zoff99 37 code2 = clipcode(p2, r);
669 zoff99 57
670 zoff99 8 }
671 zoff99 57
672 zoff99 8 if (p1->x == p2->x && p1->y == p2->y)
673 zoff99 37 ret = 0;
674 zoff99 57
675 zoff99 8 return ret;
676     }
677    
678 zoff99 37 void clip_line(struct item_bin *ib, struct rect *r, struct tile_parameter *param, struct item_bin_sink *out)
679 zoff99 8 {
680 zoff99 37 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 zoff99 8 item_bin_init(ib_new, ib->type);
687 zoff99 57
688 zoff99 37 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 zoff99 8 /* 0 = invisible, 1 = completely visible, 3 = start point clipped, 5 = end point clipped, 7 both points clipped */
697 zoff99 37 code = clip_line_code(&p1, &p2, r);
698 zoff99 8 #if 1
699 zoff99 37 if (((code == 1 || code == 5) && ib_new->clen == 0) || (code & 2))
700     {
701 zoff99 8 item_bin_add_coord(ib_new, &p1, 1);
702     }
703 zoff99 57
704 zoff99 37 if (code)
705     {
706 zoff99 8 item_bin_add_coord(ib_new, &p2, 1);
707     }
708 zoff99 57
709 zoff99 37 if (i == count - 1 || (code & 4))
710     {
711 zoff99 8 if (ib_new->clen)
712     item_bin_write_clipped(ib_new, param, out);
713 zoff99 57
714 zoff99 8 item_bin_init(ib_new, ib->type);
715     }
716     #else
717 zoff99 37 if (code)
718     {
719 zoff99 8 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 zoff99 37 static int is_inside(struct coord *p, struct rect *r, int edge)
730 zoff99 8 {
731 zoff99 37 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 zoff99 8 }
744     }
745    
746 zoff99 37 static void poly_intersection(struct coord *p1, struct coord *p2, struct rect *r, int edge, struct coord *ret)
747 zoff99 8 {
748 zoff99 37 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 zoff99 8 }
769     }
770    
771 zoff99 37 void clip_polygon(struct item_bin *ib, struct rect *r, struct tile_parameter *param, struct item_bin_sink *out)
772 zoff99 8 {
773 zoff99 37 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 zoff99 8 item_bin_init(ib_out, ib_in->type);
790 zoff99 37 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 zoff99 8 item_bin_add_coord(ib_out, &pi, 1);
798     }
799     item_bin_add_coord(ib_out, p, 1);
800 zoff99 37 }
801     else
802     {
803     if (is_inside(s, r, edge))
804     {
805     poly_intersection(p, s, r, edge, &pi);
806 zoff99 8 item_bin_add_coord(ib_out, &pi, 1);
807     }
808     }
809 zoff99 37 s = p;
810 zoff99 8 p++;
811     }
812 zoff99 37 if (ib_in == ib1)
813     {
814     ib_in = ib2;
815     ib_out = ib1;
816 zoff99 8 }
817 zoff99 37 else
818     {
819     ib_in = ib1;
820     ib_out = ib2;
821     }
822 zoff99 8 }
823     if (ib_in->clen)
824     item_bin_write_clipped(ib_in, param, out);
825     }
826 zoff99 37
827 zoff99 57

   
Visit the ZANavi Wiki