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

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

Parent Directory Parent Directory | Revision Log Revision Log


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

   
Visit the ZANavi Wiki