Add:maptool:Experimental boundary polygon matching

git-svn-id: http://svn.code.sf.net/p/navit/code/trunk/navit@3253 ffa7fe5e-494d-0410-b361-a75ebd5db220

8 files changed, 315 insertions, 10 deletions

diff --git a/navit/maptool/Makefile.am b/navit/maptool/Makefile.am
index 5f2f1e752..1aa53e1fd 100644
--- a/navit/maptool/Makefile.am
+++ b/navit/maptool/Makefile.am
@@ -5,6 +5,6 @@ if !SUPPORT_ANDROID
 endif
 
 AM_CPPFLAGS = @NAVIT_CFLAGS@ -I$(top_srcdir)/navit @ZLIB_CFLAGS@ @POSTGRESQL_CFLAGS@ -DMODULE=maptool
-libmaptool_la_SOURCES = buffer.c ch.c coastline.c geom.c itembin.c itembin_buffer.c misc.c osm.c sourcesink.c tempfile.c tile.c zip.c maptool.h
+libmaptool_la_SOURCES = boundaries.c buffer.c ch.c coastline.c geom.c itembin.c itembin_buffer.c misc.c osm.c sourcesink.c tempfile.c tile.c zip.c maptool.h
 maptool_SOURCES = maptool.c
 maptool_LDADD = libmaptool.la ../libnavit.la @NAVIT_LIBS@ @WORDEXP_LIBS@ @ZLIB_LIBS@ @POSTGRESQL_LIBS@ @CRYPTO_LIBS@ @INTLLIBS@ @LIBC_LIBS@
diff --git a/navit/maptool/boundaries.c b/navit/maptool/boundaries.c
new file mode 100644
index 000000000..af6f3109d
--- /dev/null
+++ b/navit/maptool/boundaries.c
@@ -0,0 +1,209 @@
+#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[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;
+}
diff --git a/navit/maptool/geom.c b/navit/maptool/geom.c
index 1632ad9dd..5d4bbcc08 100644
--- a/navit/maptool/geom.c
+++ b/navit/maptool/geom.c
@@ -187,6 +187,25 @@ geom_poly_segments_sort(GList *in, enum geom_poly_segment_type type)
 	return ret;
 }
 
+int
+geom_poly_segments_point_inside(GList *in, struct coord *c)
+{
+	int ret=0;
+	struct coord *cp;
+	while (in) {
+		struct geom_poly_segment *seg=in->data;
+		cp=seg->first;
+		while (cp < seg->last) {
+			if ((cp[0].y > c->y) != (cp[1].y > c->y) &&
+				c->x < (cp[1].x-cp[0].x)*(c->y-cp[0].y)/(cp[1].y-cp[0].y)+cp[0].x)
+				ret=!ret;
+			cp++;
+		}
+		in=g_list_next(in);
+	}
+	return ret;
+}
+
 struct geom_poly_segment *
 item_bin_to_poly_segment(struct item_bin *ib, int type)
 {
diff --git a/navit/maptool/itembin.c b/navit/maptool/itembin.c
index 451c8de80..ea0bf1715 100644
--- a/navit/maptool/itembin.c
+++ b/navit/maptool/itembin.c
@@ -201,6 +201,16 @@ item_bin_write(struct item_bin *ib, FILE *out)
 	fwrite(ib, (ib->len+1)*4, 1, out);
 }
 
+struct item_bin *
+item_bin_dup(struct item_bin *ib)
+{
+	int len=(ib->len+1)*4;
+	struct item_bin *ret=g_malloc(len);
+	memcpy(ret, ib, len);
+
+	return ret;
+}
+
 void
 item_bin_write_range(struct item_bin *ib, FILE *out, int min, int max)
 {
diff --git a/navit/maptool/maptool.c b/navit/maptool/maptool.c
index 226382ff4..99ce397f0 100644
--- a/navit/maptool/maptool.c
+++ b/navit/maptool/maptool.c
@@ -129,7 +129,7 @@ usage(FILE *f)
 
 int main(int argc, char **argv)
 {
-	FILE *ways=NULL,*ways_split=NULL,*ways_split_index=NULL,*nodes=NULL,*turn_restrictions=NULL,*graph=NULL,*coastline=NULL,*tilesdir,*coords,*relations=NULL;
+	FILE *ways=NULL,*ways_split=NULL,*ways_split_index=NULL,*nodes=NULL,*turn_restrictions=NULL,*graph=NULL,*coastline=NULL,*tilesdir,*coords,*relations=NULL,*boundaries=NULL;
 	FILE *files[10];
 	FILE *references[10];
 
@@ -319,6 +319,8 @@ int main(int argc, char **argv)
 			nodes=tempfile(suffix,"nodes",1);
 		if (process_ways && process_nodes) 
 			turn_restrictions=tempfile(suffix,"turn_restrictions",1);
+		if (process_relations)
+			boundaries=tempfile(suffix,"boundaries",1);
 		phase=1;
 		fprintf(stderr,"PROGRESS: Phase 1: collecting data\n");
 #ifdef HAVE_POSTGRESQL
@@ -336,7 +338,7 @@ int main(int argc, char **argv)
 			}
 		}
 		else
-			map_collect_data_osm(input_file,ways,nodes,turn_restrictions);
+			map_collect_data_osm(input_file,ways,nodes,turn_restrictions,boundaries);
 		if (slices) {
 			fprintf(stderr,"%d slices\n",slices);
 			flush_nodes(1);
@@ -354,6 +356,8 @@ int main(int argc, char **argv)
 			fclose(nodes);
 		if (turn_restrictions)
 			fclose(turn_restrictions);
+		if (boundaries)
+			fclose(boundaries);
 	}
 	if (!slices) {
 		if (end == 1 || dump_coordinates)
@@ -422,6 +426,14 @@ int main(int argc, char **argv)
 		fprintf(stderr,"PROGRESS: Phase 3: sorting countries, generating turn restrictions\n");
 		sort_countries(keep_tmpfiles);
 		if (process_relations) {
+#if 0
+			boundaries=tempfile(suffix,"boundaries",0);
+			ways_split=tempfile(suffix,"ways_split",0);
+			process_boundaries(boundaries, ways_split);
+			fclose(boundaries);
+			fclose(ways_split);
+			exit(0);
+#endif
 			turn_restrictions=tempfile(suffix,"turn_restrictions",0);
 			if (turn_restrictions) {
 				relations=tempfile(suffix,"relations",1);
diff --git a/navit/maptool/maptool.h b/navit/maptool/maptool.h
index e5e3d3d96..e9ee17f14 100644
--- a/navit/maptool/maptool.h
+++ b/navit/maptool/maptool.h
@@ -91,6 +91,10 @@ struct zip_info {
 	FILE *dir;
 };
 
+/* boundaries.c */
+
+int process_boundaries(FILE *boundaries, FILE *ways);
+
 /* buffer.c */
 struct buffer {
 	int malloced_step;
@@ -160,6 +164,7 @@ void item_bin_add_attr_longlong(struct item_bin *ib, enum attr_type type, long l
 void item_bin_add_attr_string(struct item_bin *ib, enum attr_type type, char *str);
 void item_bin_add_attr_range(struct item_bin *ib, enum attr_type type, short min, short max);
 void item_bin_write(struct item_bin *ib, FILE *out);
+struct item_bin *item_bin_dup(struct item_bin *ib);
 void item_bin_write_range(struct item_bin *ib, FILE *out, int min, int max);
 void item_bin_write_clipped(struct item_bin *ib, struct tile_parameter *param, struct item_bin_sink *out);
 void item_bin_dump(struct item_bin *ib, FILE *out);
@@ -197,6 +202,9 @@ extern struct rect world_bbox;
 void bbox_extend(struct coord *c, struct rect *r);
 void bbox(struct coord *c, int count, struct rect *r);
 int contains_bbox(int xl, int yl, int xh, int yh, struct rect *r);
+int bbox_contains_coord(struct rect *r, struct coord *c);
+int bbox_contains_bbox(struct rect *out, struct rect *in);
+long long bbox_area(struct rect *r);
 void phase1_map(GList *maps, FILE *out_ways, FILE *out_nodes);
 void dump(FILE *in);
 int phase4(FILE **in, int in_count, int with_range, char *suffix, FILE *tilesdir_out, struct zip_info *zip_info);
@@ -213,7 +221,7 @@ void flush_nodes(int final);
 void sort_countries(int keep_tmpfiles);
 void process_turn_restrictions(FILE *in, FILE *coords, FILE *ways, FILE *ways_index, FILE *out);
 int resolve_ways(FILE *in, FILE *out);
-int map_collect_data_osm(FILE *in, FILE *out_ways, FILE *out_nodes, FILE *out_turn_restrictions);
+int map_collect_data_osm(FILE *in, FILE *out_ways, FILE *out_nodes, FILE *out_turn_restrictions, FILE *out_boundaries);
 int map_collect_data_osm_db(char *dbstr, FILE *out_ways, FILE *out_nodes);
 int map_find_intersections(FILE *in, FILE *out, FILE *out_index, FILE *out_graph, FILE *out_coastline, int final);
 void write_countrydir(struct zip_info *zip_info);
diff --git a/navit/maptool/misc.c b/navit/maptool/misc.c
index 02ec8a4ce..5e5f1e5ef 100644
--- a/navit/maptool/misc.c
+++ b/navit/maptool/misc.c
@@ -95,6 +95,40 @@ contains_bbox(int xl, int yl, int xh, int yh, struct rect *r)
 	return 1;
 }
 
+int
+bbox_contains_coord(struct rect *r, struct coord *c)
+{
+	if (r->h.x < c->x)
+		return 0;
+	if (r->l.x > c->x)
+		return 0;
+	if (r->h.y < c->y)
+		return 0;
+	if (r->l.y > c->y)
+		return 0;
+	return 1;
+}
+
+int
+bbox_contains_bbox(struct rect *out, struct rect *in)
+{
+	if (out->h.x < in->h.x)
+		return 0;
+	if (out->l.x > in->l.x)
+		return 0;
+	if (out->h.y < in->h.y)
+		return 0;
+	if (out->l.y > in->l.y)
+		return 0;
+	return 1;
+}
+
+long long
+bbox_area(struct rect *r)
+{
+	return ((long long)r->h.x-r->l.x)*(r->h.y-r->l.y);
+}
+
 void
 phase1_map(GList *maps, FILE *out_ways, FILE *out_nodes)
 {
diff --git a/navit/maptool/osm.c b/navit/maptool/osm.c
index 5b0d42be8..18653c5a6 100644
--- a/navit/maptool/osm.c
+++ b/navit/maptool/osm.c
@@ -1229,10 +1229,10 @@ parse_relation(char *p)
 }
 
 static void
-end_relation(FILE *turn_restrictions)
+end_relation(FILE *turn_restrictions, FILE *boundaries)
 {
+	if ((!strcmp(relation_type, "multipolygon") || !strcmp(relation_type, "boundary")) && boundary) {
 #if 0
-	if (!strcmp(relation_type, "multipolygon") && boundary && admin_level != -1) {
 		if (admin_level == 2) {
 			FILE *f;
 			fprintf(stderr,"Multipolygon for %s\n", iso_code);
@@ -1241,8 +1241,9 @@ end_relation(FILE *turn_restrictions)
 			item_bin_write(item_bin, f);
 			fclose(f);
 		}
-	}
 #endif
+		item_bin_write(item_bin, boundaries);
+	}
 
 	if (!strcmp(relation_type, "restriction") && (item_bin->type == type_street_turn_restriction_no || item_bin->type == type_street_turn_restriction_only))
 		item_bin_write(item_bin, turn_restrictions);
@@ -1284,16 +1285,21 @@ parse_member(char *p)
 static void
 relation_add_tag(char *k, char *v)
 {
+	int add_tag=1;
 #if 0
 	fprintf(stderr,"add tag %s %s\n",k,v);
 #endif
-	if (!strcmp(k,"type")) 
+	if (!strcmp(k,"type")) {
 		strcpy(relation_type, v);
+		add_tag=0;
+	}
 	else if (!strcmp(k,"restriction")) {
 		if (!strncmp(v,"no_",3)) {
 			item_bin->type=type_street_turn_restriction_no;
+			add_tag=0;
 		} else if (!strncmp(v,"only_",5)) {
 			item_bin->type=type_street_turn_restriction_only;
+			add_tag=0;
 		} else {
 			item_bin->type=type_none;
 			osm_warning("relation", current_id, 0, "Unknown restriction %s\n",v);
@@ -1307,6 +1313,13 @@ relation_add_tag(char *k, char *v)
 	} else if (!strcmp(k,"ISO3166-1")) {
 		strcpy(iso_code, v);
 	}
+#if 0
+	if (add_tag) {
+		char tag[strlen(k)+strlen(v)+2];
+		sprintf(tag,"%s=%s",k,v);
+		item_bin_add_attr_string(item_bin, attr_osm_tag, tag);
+	}
+#endif
 }
 
 
@@ -1846,7 +1859,7 @@ parse_nd(char *p)
 }
 
 int
-map_collect_data_osm(FILE *in, FILE *out_ways, FILE *out_nodes, FILE *out_turn_restrictions)
+map_collect_data_osm(FILE *in, FILE *out_ways, FILE *out_nodes, FILE *out_turn_restrictions, FILE *out_boundaries)
 {
 	int size=BUFFER_SIZE;
 	char buffer[size];
@@ -1893,7 +1906,7 @@ map_collect_data_osm(FILE *in, FILE *out_ways, FILE *out_nodes, FILE *out_turn_r
 			end_way(out_ways);
 		} else if (!strncmp(p, "</relation>",11)) {
 			in_relation=0;
-			end_relation(out_turn_restrictions);
+			end_relation(out_turn_restrictions, out_boundaries);
 		} else if (!strncmp(p, "</osm>",6)) {
 		} else {
 			fprintf(stderr,"WARNING: unknown tag in %s\n", buffer);