navit/navit/maptool/boundaries.c

   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_member {
  24         long long wayid;
  25         enum geom_poly_segment_type role;
  26         struct boundary *boundary;
  27 };
  28
  29 static guint
  30 boundary_member_hash(gconstpointer key)
  31 {
  32         const struct boundary_member *memb=key;
  33         return (memb->wayid >> 32)^(memb->wayid & 0xffffffff);
  34 }
  35
  36 static gboolean
  37 boundary_member_equal(gconstpointer a, gconstpointer b)
  38 {
  39         const struct boundary_member *memba=a;
  40         const struct boundary_member *membb=b;
  41         return (memba->wayid == membb->wayid);
  42 }
  43
  44 GHashTable *member_hash;
  45
  46 static char *
  47 osm_tag_value(struct item_bin *ib, char *key)
  48 {
  49         char *tag=NULL;
  50         int len=strlen(key);
  51         while ((tag=item_bin_get_attr(ib, attr_osm_tag, tag))) {
  52                 if (!strncmp(tag,key,len) && tag[len] == '=')
  53                         return tag+len+1;
  54         }
  55         return NULL;
  56 }
  57
  58 static char *
  59 osm_tag_name(struct item_bin *ib)
  60 {
  61         return osm_tag_value(ib, "name");
  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                 char *admin_level=osm_tag_value(ib, "admin_level");
  74                 char *iso=osm_tag_value(ib, "ISO3166-1");
  75                 if (admin_level && !strcmp(admin_level, "2")) {
  76                         if (iso) {
  77                                 struct country_table *country=country_from_iso2(iso);
  78                                 if (!country)
  79                                         osm_warning("relation",item_bin_get_relationid(ib),0,"Country Boundary contains unknown ISO3166-1 value '%s'\n",iso);
  80                                 boundary->country=country;
  81                         } else
  82                                 osm_warning("relation",item_bin_get_relationid(ib),0,"Country Boundary doesn't contain an ISO3166-1 tag\n");
  83                 }
  84                 while ((member=item_bin_get_attr(ib, attr_osm_member, member))) {
  85                         long long wayid;
  86                         int read=0;
  87                         if (sscanf(member,"2:%Ld:%n",&wayid,&read) >= 1) {
  88                                 struct boundary_member *memb=g_new(struct boundary_member, 1);
  89                                 char *role=member+read;
  90                                 memb->wayid=wayid;
  91                                 memb->boundary=boundary;
  92                                 if (!strcmp(role,"outer"))
  93                                         memb->role=geom_poly_segment_type_way_outer;
  94                                 else if (!strcmp(role,"inner"))
  95                                         memb->role=geom_poly_segment_type_way_inner;
  96                                 else if (!strcmp(role,""))
  97                                         memb->role=geom_poly_segment_type_way_unknown;
  98                                 else {
  99                                         printf("Unknown role %s\n",role);
 100                                         memb->role=geom_poly_segment_type_none;
 101                                 }
 102                                 g_hash_table_insert(member_hash, memb, g_list_append(g_hash_table_lookup(member_hash, memb), memb));
 103
 104                         }
 105                 }
 106                 boundary->ib=item_bin_dup(ib);
 107                 boundaries_list=g_list_append(boundaries_list, boundary);
 108         }
 109         return boundaries_list;
 110 }
 111
 112 GList *
 113 boundary_find_matches(GList *l, struct coord *c)
 114 {
 115         GList *ret=NULL;
 116         while (l) {
 117                 struct boundary *boundary=l->data;
 118                 if (bbox_contains_coord(&boundary->r, c)) {
 119                         if (geom_poly_segments_point_inside(boundary->sorted_segments,c))
 120                                 ret=g_list_prepend(ret, boundary);
 121                         ret=g_list_concat(ret,boundary_find_matches(boundary->children, c));
 122                 }
 123                 l=g_list_next(l);
 124         }
 125         return ret;
 126 }
 127
 128 static void
 129 test(GList *boundaries_list)
 130 {
 131         struct item_bin *ib;
 132         FILE *f=fopen("country_276.bin.unsorted","r");
 133         printf("start\n");
 134         while ((ib=read_item(f))) {
 135                 struct coord *c=(struct coord *)(ib+1);
 136                 char *name=item_bin_get_attr(ib, attr_town_name, NULL);
 137                 printf("%s:",name);
 138                 boundary_find_matches(boundaries_list, c);
 139                 printf("\n");
 140         }
 141         fclose(f);
 142         printf("end\n");
 143 }
 144
 145 static void
 146 dump_hierarchy(GList *l, char *prefix)
 147 {
 148         char *newprefix=g_alloca(sizeof(char)*(strlen(prefix)+2));
 149         strcpy(newprefix, prefix);
 150         strcat(newprefix," ");
 151         while (l) {
 152                 struct boundary *boundary=l->data;
 153                 printf("%s:%s\n",prefix,osm_tag_name(boundary->ib));
 154                 dump_hierarchy(boundary->children, newprefix);
 155                 l=g_list_next(l);
 156         }
 157 }
 158
 159 static gint
 160 boundary_bbox_compare(gconstpointer a, gconstpointer b)
 161 {
 162         const struct boundary *boundarya=a;
 163         const struct boundary *boundaryb=b;
 164         long long areaa=bbox_area(&boundarya->r);
 165         long long areab=bbox_area(&boundaryb->r);
 166         if (areaa > areab)
 167                 return 1;
 168         if (areaa < areab)
 169                 return -1;
 170         return 0;
 171 }
 172
 173 GList *
 174 process_boundaries(FILE *boundaries, FILE *ways)
 175 {
 176         struct item_bin *ib;
 177         GList *boundaries_list,*l,*sl,*l2,*ln;
 178
 179         member_hash=g_hash_table_new_full(boundary_member_hash, boundary_member_equal, NULL, NULL);
 180         boundaries_list=build_boundaries(boundaries);
 181         while ((ib=read_item(ways))) {
 182                 long long *wayid=item_bin_get_attr(ib, attr_osm_wayid, NULL);
 183                 if (wayid) {
 184                         GList *l=g_hash_table_lookup(member_hash, wayid);
 185                         while (l) {
 186                                 struct boundary_member *memb=l->data;
 187                                 memb->boundary->segments=g_list_prepend(memb->boundary->segments,item_bin_to_poly_segment(ib, memb->role));
 188
 189                                 l=g_list_next(l);
 190                         }
 191                 }
 192         }
 193         l=boundaries_list;
 194         while (l) {
 195                 struct boundary *boundary=l->data;
 196                 int first=1;
 197                 boundary->sorted_segments=geom_poly_segments_sort(boundary->segments, geom_poly_segment_type_way_right_side);
 198                 sl=boundary->sorted_segments;
 199                 while (sl) {
 200                         struct geom_poly_segment *gs=sl->data;
 201                         struct coord *c=gs->first;
 202                         while (c <= gs->last) {
 203                                 if (first) {
 204                                         boundary->r.l=*c;
 205                                         boundary->r.h=*c;
 206                                         first=0;
 207                                 } else
 208                                         bbox_extend(c, &boundary->r);
 209                                 c++;
 210                         }
 211                         sl=g_list_next(sl);
 212                 }
 213                 l=g_list_next(l);
 214
 215         }
 216 #if 0
 217         printf("hierarchy\n");
 218 #endif
 219         boundaries_list=g_list_sort(boundaries_list, boundary_bbox_compare);
 220         l=boundaries_list;
 221         while (l) {
 222                 struct boundary *boundary=l->data;
 223                 ln=l2=g_list_next(l);
 224                 while (l2) {
 225                         struct boundary *boundary2=l2->data;
 226                         if (bbox_contains_bbox(&boundary2->r, &boundary->r)) {
 227                                 boundaries_list=g_list_remove(boundaries_list, boundary);
 228                                 boundary2->children=g_list_append(boundary2->children, boundary);
 229 #if 0
 230                                 printf("found\n");
 231 #endif
 232                                 break;
 233                         }
 234                         l2=g_list_next(l2);
 235                 }
 236                 l=ln;
 237         }
 238 #if 0
 239         printf("hierarchy done\n");
 240         dump_hierarchy(boundaries_list,"");
 241         printf("test\n");
 242         test(boundaries_list);
 243 #endif
 244         return boundaries_list;
 245 }