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

Diff of /navit/navit/maptool/geom.c

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

Revision 35 Revision 36
… …
15 * along with this program; if not, write to the 15 * along with this program; if not, write to the
16 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 16 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17 * Boston, MA 02110-1301, USA. 17 * Boston, MA 02110-1301, USA.
18 */ 18 */
19#include <string.h> 19#include <string.h>
20#include <math.h>
20#include "maptool.h" 21#include "maptool.h"
21 22
22void 23void
23geom_coord_copy(struct coord *from, struct coord *to, int count, int reverse) 24geom_coord_copy(struct coord *from, struct coord *to, int count, int reverse)
24{ 25{
… …
30 from+=count; 31 from+=count;
31 for (i = 0 ; i < count ; i++) 32 for (i = 0 ; i < count ; i++)
32 *to++=*--from; 33 *to++=*--from;
33} 34}
34 35
36/**
37 * Get coordinates of polyline middle point.
38 * @param in *p array of poly vertex coordinates
39 * @param in count count of poly vertexes
40 * @param out *c coordinates of middle point
41 * @returns number of first vertex of segment containing middle point
42 */
43int
44geom_line_middle(struct coord *p, int count, struct coord *c)
45{
46 double length=0,half=0,len=0;
47 int i;
48
49 if(count==1) {
50 *c=*p;
51 return 0;
52 }
53
54 for (i=0; i<count-1; i++) {
55 length+=sqrt(sq(p[i].x-p[i+1].x)+sq(p[i].y-p[i+1].y));
56 }
57
58 length/=2;
59 for (i=0; (i<count-1) && (half<length); i++) {
60 len=sqrt(sq(p[i].x-p[i+1].x)+sq(p[i].y-p[i+1].y));
61 half+=len;
62 }
63 if (i > 0) {
64 i--;
65 half-=length;
66 if (len) {
67 c->x=(p[i].x*half+p[i+1].x*(len-half))/len;
68 c->y=(p[i].y*half+p[i+1].y*(len-half))/len;
69 } else
70 *c=p[i];
71 } else
72 *c=p[0];
73 return i;
74}
75
76
35void 77void
36geom_coord_revert(struct coord *c, int count) 78geom_coord_revert(struct coord *c, int count)
37{ 79{
38 struct coord tmp; 80 struct coord tmp;
39 int i; 81 int i;
… …
58 if (++j == count) 100 if (++j == count)
59 j=0; 101 j=0;
60#if 0 102#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)); 103 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 104#endif
63 area+=(long long)(c[i].x+c[j].x)*(c[i].y-c[j].y); 105 area+=(long long)(c[i].x+c[j].x)*(c[i].y-c[j].y);
64#if 0 106#if 0
65 fprintf(stderr,"area="LONGLONG_FMT"\n",area); 107 fprintf(stderr,"area="LONGLONG_FMT"\n",area);
66#endif 108#endif
67 } 109 }
68 return area/2; 110 return area/2;
69} 111}
112
113/**
114 * Get poly centroid coordinates.
115 * @param in *p array of poly vertex coordinates
116 * @param in count count of poly vertexes
117 * @param out *c coordinates of poly centroid
118 * @returns 1 on success, 0 if poly area is 0
119 */
120int
121geom_poly_centroid(struct coord *p, int count, struct coord *c)
122{
123 long long area=0;
124 long long sx=0,sy=0,tmp;
125 int i,j;
126 long long x0=p[0].x, y0=p[0].y, xi, yi, xj, yj;
127
128 /*fprintf(stderr,"area="LONGLONG_FMT"\n", area );*/
129 for (i=0,j=0; i<count; i++) {
130 if (++j == count)
131 j=0;
132 xi=p[i].x-x0;
133 yi=p[i].y-y0;
134 xj=p[j].x-x0;
135 yj=p[j].y-y0;
136 tmp=(xi*yj-xj*yi);
137 sx+=(xi+xj)*tmp;
138 sy+=(yi+yj)*tmp;
139 area+=xi*yj-xj*yi;
140 }
141 if(area!=0) {
142 c->x=x0+sx/3/area;
143 c->y=y0+sy/3/area;
144 return 1;
145 }
146 return 0;
147}
148
149/**
150 * Get coordinates of polyline point c most close to given point p.
151 * @param in *pl array of polyline vertex coordinates
152 * @param in count count of polyline vertexes
153 * @param in *p point coordinates
154 * @param out *c coordinates of polyline point most close to given point.
155 * @returns first vertex number of polyline segment to which c belongs
156 */
157int
158geom_poly_closest_point(struct coord *pl, int count, struct coord *p, struct coord *c)
159{
160 int i,vertex=0;
161 long long x, y, xi, xj, yi, yj, u, d, dmin=0;
162 if(count<2) {
163 c->x=pl->x;
164 c->y=pl->y;
165 return 0;
166 }
167 for(i=0;i<count-1;i++) {
168 xi=pl[i].x;
169 yi=pl[i].y;
170 xj=pl[i+1].x;
171 yj=pl[i+1].y;
172 u=(xj-xi)*(xj-xi)+(yj-yi)*(yj-yi);
173 if(u!=0) {
174 u=((p->x-xi)*(xj-xi)+(p->y-yi)*(yj-yi))*1000/u;
175 }
176 if(u<0)
177 u=0;
178 else if (u>1000)
179 u=1000;
180 x=xi+u*(xj-xi)/1000;
181 y=yi+u*(yj-yi)/1000;
182 d=(p->x-x)*(p->x-x)+(p->y-y)*(p->y-y);
183 if(i==0 || d<dmin) {
184 dmin=d;
185 c->x=x;
186 c->y=y;
187 vertex=i;
188 }
189 }
190 return vertex;
191}
192
193/**
194 * Check if point is inside polgone.
195 * @param in *cp array of polygon vertex coordinates
196 * @param in count count of polygon vertexes
197 * @param in *c point coordinates
198 * @returns 1 - inside, 0 - outside
199 */
200int
201geom_poly_point_inside(struct coord *cp, int count, struct coord *c)
202{
203 int ret=0;
204 struct coord *last=cp+count-1;
205 while (cp < last) {
206 if ((cp[0].y > c->y) != (cp[1].y > c->y) &&
207 c->x < ((long long)cp[1].x-cp[0].x)*(c->y-cp[0].y)/(cp[1].y-cp[0].y)+cp[0].x) {
208#if 0
209 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);
210 printf("type=selected_line\n");
211 coord_print(projection_mg, &cp[0], stdout);
212 coord_print(projection_mg, &cp[1], stdout);
213#endif
214 ret=!ret;
215 }
216 cp++;
217 }
218 return ret;
219}
220
221
70 222
71GList * 223GList *
72geom_poly_segments_insert(GList *list, struct geom_poly_segment *first, struct geom_poly_segment *second, struct geom_poly_segment *third) 224geom_poly_segments_insert(GList *list, struct geom_poly_segment *first, struct geom_poly_segment *second, struct geom_poly_segment *third)
73{ 225{
74 int count; 226 int count;
… …
141geom_poly_segment_compatible(struct geom_poly_segment *s1, struct geom_poly_segment *s2, int dir) 293geom_poly_segment_compatible(struct geom_poly_segment *s1, struct geom_poly_segment *s2, int dir)
142{ 294{
143 int same=0,opposite=0; 295 int same=0,opposite=0;
144 if (s1->type == geom_poly_segment_type_none || s2->type == geom_poly_segment_type_none) 296 if (s1->type == geom_poly_segment_type_none || s2->type == geom_poly_segment_type_none)
145 return 0; 297 return 0;
146 if (s1->type == s2->type) 298 if (s1->type == s2->type) {
147 same=1; 299 same=1;
148 if (s1->type == geom_poly_segment_type_way_inner && s2->type == geom_poly_segment_type_way_outer) 300 if (s1->type == geom_poly_segment_type_way_inner || s1->type == geom_poly_segment_type_way_outer) {
149 opposite=1; 301 opposite=1;
150 if (s1->type == geom_poly_segment_type_way_outer && s2->type == geom_poly_segment_type_way_inner) 302 }
151 opposite=1; 303 }
152 if (s1->type == geom_poly_segment_type_way_left_side && s2->type == geom_poly_segment_type_way_right_side) 304 if (s1->type == geom_poly_segment_type_way_left_side && s2->type == geom_poly_segment_type_way_right_side)
153 opposite=1; 305 opposite=1;
154 if (s1->type == geom_poly_segment_type_way_right_side && s2->type == geom_poly_segment_type_way_left_side) 306 if (s1->type == geom_poly_segment_type_way_right_side && s2->type == geom_poly_segment_type_way_left_side)
155 opposite=1; 307 opposite=1;
156 if (s1->type == geom_poly_segment_type_way_unknown || s2->type == geom_poly_segment_type_way_unknown) { 308 if (s1->type == geom_poly_segment_type_way_unknown || s2->type == geom_poly_segment_type_way_unknown) {
… …
206} 358}
207 359
208int 360int
209geom_poly_segments_point_inside(GList *in, struct coord *c) 361geom_poly_segments_point_inside(GList *in, struct coord *c)
210{ 362{
211 int ret=0; 363 int open_matches=0,closed_matches=0;
212 struct coord *cp; 364 struct coord *cp;
365#if 0
366 fprintf(stderr,"try 0x%x,0x%x:",c->x,c->y);
367#endif
213 while (in) { 368 while (in) {
214 struct geom_poly_segment *seg=in->data; 369 struct geom_poly_segment *seg=in->data;
215 cp=seg->first; 370 cp=seg->first;
216 while (cp < seg->last) { 371 if (geom_poly_point_inside(seg->first, seg->last-seg->first+1, c)) {
217 if ((cp[0].y > c->y) != (cp[1].y > c->y) && 372#if 0
218 c->x < (cp[1].x-cp[0].x)*(c->y-cp[0].y)/(cp[1].y-cp[0].y)+cp[0].x) 373 fprintf(stderr," inside");
219 ret=!ret; 374#endif
220 cp++; 375 if (coord_is_equal(*seg->first,*seg->last))
376 closed_matches++;
377 else
378 open_matches++;
379 } else {
380#if 0
381 fprintf(stderr," outside");
382#endif
221 } 383 }
222 in=g_list_next(in); 384 in=g_list_next(in);
223 } 385 }
386#if 0
387 fprintf(stderr,"\n");
388 fprintf(stderr,"open_matches %d closed_matches %d\n",open_matches,closed_matches);
389#endif
390 if (closed_matches) {
391 if (closed_matches & 1)
392 return 1;
393 else
394 return 0;
395 }
396 if (open_matches) {
397 if (open_matches & 1)
398 return -1;
399 else
400 return 0;
401 }
224 return ret; 402 return 0;
225} 403}
226 404
227struct geom_poly_segment * 405struct geom_poly_segment *
228item_bin_to_poly_segment(struct item_bin *ib, int type) 406item_bin_to_poly_segment(struct item_bin *ib, int type)
229{ 407{
Legend:
Removed from v.35  
changed lines
  Added in v.36
   
Visit the ZANavi Wiki