navit/maptool/boundaries.c

/**
 * Navit, a modular navigation system.
 * Copyright (C) 2005-2011 Navit Team
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * version 2 as published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the
 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA  02110-1301, USA.
 */
#include <stdio.h>
#include <string.h>
#include "maptool.h"

struct boundary {
        struct item_bin *ib;
        GList *segments,*sorted_segments;
        GList *children;
        struct rect r;
};

struct boundary_member {
        long long wayid;
        enum geom_poly_segment_type role;
        struct boundary *boundary;
};

static guint
boundary_member_hash(gconstpointer key)
{
        const struct boundary_member *memb=key;
        return (memb->wayid >> 32)^(memb->wayid & 0xffffffff);
}

static gboolean
boundary_member_equal(gconstpointer a, gconstpointer b)
{
        const struct boundary_member *memba=a;
        const struct boundary_member *membb=b;
        return (memba->wayid == membb->wayid);
}

GHashTable *member_hash;

static char *
osm_tag_name(struct item_bin *ib)
{
        char *tag=NULL;
        while ((tag=item_bin_get_attr(ib, attr_osm_tag, tag))) {
                if (!strncmp(tag,"name=",5))
                        return tag+5;
        }
        return NULL;
}

static GList *
build_boundaries(FILE *boundaries)
{
        struct item_bin *ib;
        GList *boundaries_list=NULL;

        while ((ib=read_item(boundaries))) {
                char *member=NULL;
                struct boundary *boundary=g_new0(struct boundary, 1);
                while ((member=item_bin_get_attr(ib, attr_osm_member, member))) {
                        long long wayid;
                        int read=0;
                        if (sscanf(member,"2:%Ld:%n",&wayid,&read) >= 1) {
                                struct boundary_member *memb=g_new(struct boundary_member, 1);
                                char *role=member+read;
                                memb->wayid=wayid;
                                memb->boundary=boundary;
                                if (!strcmp(role,"outer"))
                                        memb->role=geom_poly_segment_type_way_outer;
                                else if (!strcmp(role,"inner"))
                                        memb->role=geom_poly_segment_type_way_inner;
                                else if (!strcmp(role,""))
                                        memb->role=geom_poly_segment_type_way_unknown;
                                else {
                                        printf("Unknown role %s\n",role);
                                        memb->role=geom_poly_segment_type_none;
                                }
                                g_hash_table_insert(member_hash, memb, g_list_append(g_hash_table_lookup(member_hash, memb), memb));

                        }
                }
                boundary->ib=item_bin_dup(ib);
                boundaries_list=g_list_append(boundaries_list, boundary);
        }
        return boundaries_list;
}

static void
find_matches(GList *l, struct coord *c)
{
        while (l) {
                struct boundary *boundary=l->data;
                if (bbox_contains_coord(&boundary->r, c)) {
                        struct item_bin *ib=boundary->ib;
                        if (geom_poly_segments_point_inside(boundary->sorted_segments,c)) 
                                printf("%s,",osm_tag_name(ib));
                        find_matches(boundary->children, c);
                }
                l=g_list_next(l);
        }
}

static void
test(GList *boundaries_list)
{
        struct item_bin *ib;
        FILE *f=fopen("country_276.bin.unsorted","r");
        printf("start\n");
        while ((ib=read_item(f))) {
                struct coord *c=(struct coord *)(ib+1);
                char *name=item_bin_get_attr(ib, attr_town_name, NULL);
                printf("%s:",name);
                find_matches(boundaries_list, c);
                printf("\n");
        }
        fclose(f);
        printf("end\n");
}

static void
dump_hierarchy(GList *l, char *prefix)
{
        char *newprefix=g_alloca(sizeof(char)*(strlen(prefix)+2));
        strcpy(newprefix, prefix);
        strcat(newprefix," ");
        while (l) {
                struct boundary *boundary=l->data;
                printf("%s:%s\n",prefix,osm_tag_name(boundary->ib));
                dump_hierarchy(boundary->children, newprefix);
                l=g_list_next(l);
        }
}

static gint
boundary_bbox_compare(gconstpointer a, gconstpointer b)
{
        const struct boundary *boundarya=a;
        const struct boundary *boundaryb=b;
        long long areaa=bbox_area(&boundarya->r);
        long long areab=bbox_area(&boundaryb->r);
        if (areaa > areab)
                return 1;
        if (areaa < areab)
                return -1;
        return 0;
}

int
process_boundaries(FILE *boundaries, FILE *ways)
{
        struct item_bin *ib;
        GList *boundaries_list,*l,*sl,*l2,*ln;

        member_hash=g_hash_table_new_full(boundary_member_hash, boundary_member_equal, NULL, NULL);
        boundaries_list=build_boundaries(boundaries);
        while ((ib=read_item(ways))) {
                long long *wayid=item_bin_get_attr(ib, attr_osm_wayid, NULL);
                if (wayid) {
                        GList *l=g_hash_table_lookup(member_hash, wayid);
                        while (l) {
                                struct boundary_member *memb=l->data;
                                memb->boundary->segments=g_list_prepend(memb->boundary->segments,item_bin_to_poly_segment(ib, memb->role));

                                l=g_list_next(l);
                        }
                }
        }
        l=boundaries_list;
        while (l) {
                struct boundary *boundary=l->data;
                int first=1;
                boundary->sorted_segments=geom_poly_segments_sort(boundary->segments, geom_poly_segment_type_way_right_side);
                sl=boundary->sorted_segments;
                while (sl) {
                        struct geom_poly_segment *gs=sl->data;
                        struct coord *c=gs->first;
                        while (c <= gs->last) {
                                if (first) {
                                        boundary->r.l=*c;
                                        boundary->r.h=*c;
                                        first=0;
                                } else
                                        bbox_extend(c, &boundary->r);
                                c++;
                        }
                        sl=g_list_next(sl);
                }       
                l=g_list_next(l);
                
        }
        printf("hierarchy\n");
        boundaries_list=g_list_sort(boundaries_list, boundary_bbox_compare);
        l=boundaries_list;
        while (l) {
                struct boundary *boundary=l->data;
                ln=l2=g_list_next(l);
                while (l2) {
                        struct boundary *boundary2=l2->data;
                        if (bbox_contains_bbox(&boundary2->r, &boundary->r)) {
                                boundaries_list=g_list_remove(boundaries_list, boundary);
                                boundary2->children=g_list_append(boundary2->children, boundary);
                                printf("found\n");
                                break;
                        }
                        l2=g_list_next(l2);
                }
                l=ln;
        }
        printf("hierarchy done\n");
        dump_hierarchy(boundaries_list,"");
        printf("test\n");
        test(boundaries_list);
        return 1;
}
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 <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	}