/[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 - (show annotations) (download)
Fri Oct 28 21:39:42 2011 UTC (12 years, 5 months ago) by zoff99
File MIME type: text/plain
File size: 11160 byte(s)
import
1 /**
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