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

Contents of /navit/navit/maptool/boundaries.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 8 - (hide annotations) (download)
Fri Oct 28 21:39:42 2011 UTC (12 years, 5 months ago) by zoff99
File MIME type: text/plain
File size: 5895 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 <stdio.h>
20     #include <string.h>
21     #include "maptool.h"
22    
23     struct boundary {
24     struct item_bin *ib;
25     GList *segments,*sorted_segments;
26     GList *children;
27     struct rect r;
28     };
29    
30     struct boundary_member {
31     long long wayid;
32     enum geom_poly_segment_type role;
33     struct boundary *boundary;
34     };
35    
36     static guint
37     boundary_member_hash(gconstpointer key)
38     {
39     const struct boundary_member *memb=key;
40     return (memb->wayid >> 32)^(memb->wayid & 0xffffffff);
41     }
42    
43     static gboolean
44     boundary_member_equal(gconstpointer a, gconstpointer b)
45     {
46     const struct boundary_member *memba=a;
47     const struct boundary_member *membb=b;
48     return (memba->wayid == membb->wayid);
49     }
50    
51     GHashTable *member_hash;
52    
53     static char *
54     osm_tag_name(struct item_bin *ib)
55     {
56     char *tag=NULL;
57     while ((tag=item_bin_get_attr(ib, attr_osm_tag, tag))) {
58     if (!strncmp(tag,"name=",5))
59     return tag+5;
60     }
61     return NULL;
62     }
63    
64     static GList *
65     build_boundaries(FILE *boundaries)
66     {
67     struct item_bin *ib;
68     GList *boundaries_list=NULL;
69    
70     while ((ib=read_item(boundaries))) {
71     char *member=NULL;
72     struct boundary *boundary=g_new0(struct boundary, 1);
73     while ((member=item_bin_get_attr(ib, attr_osm_member, member))) {
74     long long wayid;
75     int read=0;
76     if (sscanf(member,"2:%Ld:%n",&wayid,&read) >= 1) {
77     struct boundary_member *memb=g_new(struct boundary_member, 1);
78     char *role=member+read;
79     memb->wayid=wayid;
80     memb->boundary=boundary;
81     if (!strcmp(role,"outer"))
82     memb->role=geom_poly_segment_type_way_outer;
83     else if (!strcmp(role,"inner"))
84     memb->role=geom_poly_segment_type_way_inner;
85     else if (!strcmp(role,""))
86     memb->role=geom_poly_segment_type_way_unknown;
87     else {
88     printf("Unknown role %s\n",role);
89     memb->role=geom_poly_segment_type_none;
90     }
91     g_hash_table_insert(member_hash, memb, g_list_append(g_hash_table_lookup(member_hash, memb), memb));
92    
93     }
94     }
95     boundary->ib=item_bin_dup(ib);
96     boundaries_list=g_list_append(boundaries_list, boundary);
97     }
98     return boundaries_list;
99     }
100    
101     static void
102     find_matches(GList *l, struct coord *c)
103     {
104     while (l) {
105     struct boundary *boundary=l->data;
106     if (bbox_contains_coord(&boundary->r, c)) {
107     struct item_bin *ib=boundary->ib;
108     if (geom_poly_segments_point_inside(boundary->sorted_segments,c))
109     printf("%s,",osm_tag_name(ib));
110     find_matches(boundary->children, c);
111     }
112     l=g_list_next(l);
113     }
114     }
115    
116     static void
117     test(GList *boundaries_list)
118     {
119     struct item_bin *ib;
120     FILE *f=fopen("country_276.bin.unsorted","r");
121     printf("start\n");
122     while ((ib=read_item(f))) {
123     struct coord *c=(struct coord *)(ib+1);
124     char *name=item_bin_get_attr(ib, attr_town_name, NULL);
125     printf("%s:",name);
126     find_matches(boundaries_list, c);
127     printf("\n");
128     }
129     fclose(f);
130     printf("end\n");
131     }
132    
133     static void
134     dump_hierarchy(GList *l, char *prefix)
135     {
136     char *newprefix=g_alloca(sizeof(char)*(strlen(prefix)+2));
137     strcpy(newprefix, prefix);
138     strcat(newprefix," ");
139     while (l) {
140     struct boundary *boundary=l->data;
141     printf("%s:%s\n",prefix,osm_tag_name(boundary->ib));
142     dump_hierarchy(boundary->children, newprefix);
143     l=g_list_next(l);
144     }
145     }
146    
147     static gint
148     boundary_bbox_compare(gconstpointer a, gconstpointer b)
149     {
150     const struct boundary *boundarya=a;
151     const struct boundary *boundaryb=b;
152     long long areaa=bbox_area(&boundarya->r);
153     long long areab=bbox_area(&boundaryb->r);
154     if (areaa > areab)
155     return 1;
156     if (areaa < areab)
157     return -1;
158     return 0;
159     }
160    
161     int
162     process_boundaries(FILE *boundaries, FILE *ways)
163     {
164     struct item_bin *ib;
165     GList *boundaries_list,*l,*sl,*l2,*ln;
166    
167     member_hash=g_hash_table_new_full(boundary_member_hash, boundary_member_equal, NULL, NULL);
168     boundaries_list=build_boundaries(boundaries);
169     while ((ib=read_item(ways))) {
170     long long *wayid=item_bin_get_attr(ib, attr_osm_wayid, NULL);
171     if (wayid) {
172     GList *l=g_hash_table_lookup(member_hash, wayid);
173     while (l) {
174     struct boundary_member *memb=l->data;
175     memb->boundary->segments=g_list_prepend(memb->boundary->segments,item_bin_to_poly_segment(ib, memb->role));
176    
177     l=g_list_next(l);
178     }
179     }
180     }
181     l=boundaries_list;
182     while (l) {
183     struct boundary *boundary=l->data;
184     int first=1;
185     boundary->sorted_segments=geom_poly_segments_sort(boundary->segments, geom_poly_segment_type_way_right_side);
186     sl=boundary->sorted_segments;
187     while (sl) {
188     struct geom_poly_segment *gs=sl->data;
189     struct coord *c=gs->first;
190     while (c <= gs->last) {
191     if (first) {
192     boundary->r.l=*c;
193     boundary->r.h=*c;
194     first=0;
195     } else
196     bbox_extend(c, &boundary->r);
197     c++;
198     }
199     sl=g_list_next(sl);
200     }
201     l=g_list_next(l);
202    
203     }
204     printf("hierarchy\n");
205     boundaries_list=g_list_sort(boundaries_list, boundary_bbox_compare);
206     l=boundaries_list;
207     while (l) {
208     struct boundary *boundary=l->data;
209     ln=l2=g_list_next(l);
210     while (l2) {
211     struct boundary *boundary2=l2->data;
212     if (bbox_contains_bbox(&boundary2->r, &boundary->r)) {
213     boundaries_list=g_list_remove(boundaries_list, boundary);
214     boundary2->children=g_list_append(boundary2->children, boundary);
215     printf("found\n");
216     break;
217     }
218     l2=g_list_next(l2);
219     }
220     l=ln;
221     }
222     printf("hierarchy done\n");
223     dump_hierarchy(boundaries_list,"");
224     printf("test\n");
225     test(boundaries_list);
226     return 1;
227     }

   
Visit the ZANavi Wiki