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 char *
  24 osm_tag_value(struct item_bin *ib, char *key)
  25 {
  26         char *tag=NULL;
  27         int len=strlen(key);
  28         while ((tag=item_bin_get_attr(ib, attr_osm_tag, tag))) {
  29                 if (!strncmp(tag,key,len) && tag[len] == '=')
  30                         return tag+len+1;
  31         }
  32         return NULL;
  33 }
  34
  35 static char *
  36 osm_tag_name(struct item_bin *ib)
  37 {
  38         return osm_tag_value(ib, "name");
  39 }
  40
  41 osmid
  42 boundary_relid(struct boundary *b)
  43 {
  44         long long *id;
  45         if (!b)
  46                 return 0;
  47         if (!b->ib)
  48                 return 0;
  49         id=item_bin_get_attr(b->ib, attr_osm_relationid, NULL);
  50         if (id)
  51                 return *id;
  52         return 0;
  53 }
  54 static void
  55 process_boundaries_member(void *func_priv, void *relation_priv, struct item_bin *member, void *member_priv)
  56 {
  57         struct boundary *b=relation_priv;
  58         enum geom_poly_segment_type role=(long)member_priv;
  59         b->segments=g_list_prepend(b->segments,item_bin_to_poly_segment(member, role));
  60 }
  61
  62 static GList *
  63 process_boundaries_setup(FILE *boundaries, struct relations *relations)
  64 {
  65         struct item_bin *ib;
  66         GList *boundaries_list=NULL;
  67         struct relations_func *relations_func;
  68
  69         relations_func=relations_func_new(process_boundaries_member, NULL);
  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                 /* disable spain for now since it creates a too large index */
  76                 if (admin_level && !strcmp(admin_level, "2") && (!iso || strcasecmp(iso,"es"))) {
  77                         if (iso) {
  78                                 struct country_table *country=country_from_iso2(iso);
  79                                 if (!country)
  80                                         osm_warning("relation",item_bin_get_relationid(ib),0,"Country Boundary contains unknown ISO3166-1 value '%s'\n",iso);
  81                                 else {
  82                                         boundary->iso2=g_strdup(iso);
  83                                         osm_info("relation",item_bin_get_relationid(ib),0,"Country Boundary for '%s'\n",iso);
  84                                 }
  85                                 boundary->country=country;
  86                         } else
  87                                 osm_warning("relation",item_bin_get_relationid(ib),0,"Country Boundary doesn't contain an ISO3166-1 tag\n");
  88                 }
  89                 while ((member=item_bin_get_attr(ib, attr_osm_member, member))) {
  90                         long long wayid;
  91                         int read=0;
  92                         if (sscanf(member,"2:"LONGLONG_FMT":%n",&wayid,&read) >= 1) {
  93                                 char *rolestr=member+read;
  94                                 enum geom_poly_segment_type role;
  95                                 if (!strcmp(rolestr,"outer") || !strcmp(rolestr,"exclave"))
  96                                         role=geom_poly_segment_type_way_outer;
  97                                 else if (!strcmp(rolestr,"inner") || !strcmp(rolestr,"enclave"))
  98                                         role=geom_poly_segment_type_way_inner;
  99                                 else if (!strcmp(rolestr,""))
 100                                         role=geom_poly_segment_type_way_unknown;
 101                                 else {
 102                                         osm_warning("relation",item_bin_get_relationid(ib),0,"Unknown role %s in member ",rolestr);
 103                                         osm_warning("way",wayid,1,"\n");
 104                                         role=geom_poly_segment_type_none;
 105                                 }
 106                                 relations_add_func(relations, relations_func, boundary, (gpointer)role, 2, wayid);
 107                         }
 108                 }
 109                 boundary->ib=item_bin_dup(ib);
 110                 boundaries_list=g_list_append(boundaries_list, boundary);
 111         }
 112         return boundaries_list;
 113 }
 114
 115 GList *
 116 boundary_find_matches(GList *l, struct coord *c)
 117 {
 118         GList *ret=NULL;
 119         while (l) {
 120                 struct boundary *boundary=l->data;
 121                 if (bbox_contains_coord(&boundary->r, c)) {
 122                         if (geom_poly_segments_point_inside(boundary->sorted_segments,c) > 0)
 123                                 ret=g_list_prepend(ret, boundary);
 124                         ret=g_list_concat(ret,boundary_find_matches(boundary->children, c));
 125                 }
 126                 l=g_list_next(l);
 127         }
 128         return ret;
 129 }
 130
 131 static void
 132 test(GList *boundaries_list)
 133 {
 134         struct item_bin *ib;
 135         FILE *f=fopen("country_276.bin.unsorted","r");
 136         printf("start\n");
 137         while ((ib=read_item(f))) {
 138                 struct coord *c=(struct coord *)(ib+1);
 139                 char *name=item_bin_get_attr(ib, attr_town_name, NULL);
 140                 printf("%s:",name);
 141                 boundary_find_matches(boundaries_list, c);
 142                 printf("\n");
 143         }
 144         fclose(f);
 145         printf("end\n");
 146 }
 147
 148 static void
 149 dump_hierarchy(GList *l, char *prefix)
 150 {
 151         char *newprefix=g_alloca(sizeof(char)*(strlen(prefix)+2));
 152         strcpy(newprefix, prefix);
 153         strcat(newprefix," ");
 154         while (l) {
 155                 struct boundary *boundary=l->data;
 156                 fprintf(stderr,"%s:%s (0x%x,0x%x)-(0x%x,0x%x)\n",prefix,osm_tag_name(boundary->ib),boundary->r.l.x,boundary->r.l.y,boundary->r.h.x,boundary->r.h.y);
 157                 dump_hierarchy(boundary->children, newprefix);
 158                 l=g_list_next(l);
 159         }
 160 }
 161
 162 static gint
 163 boundary_bbox_compare(gconstpointer a, gconstpointer b)
 164 {
 165         const struct boundary *boundarya=a;
 166         const struct boundary *boundaryb=b;
 167         long long areaa=bbox_area(&boundarya->r);
 168         long long areab=bbox_area(&boundaryb->r);
 169         if (areaa > areab)
 170                 return 1;
 171         if (areaa < areab)
 172                 return -1;
 173         return 0;
 174 }
 175
 176 static GList *
 177 process_boundaries_insert(GList *list, struct boundary *boundary)
 178 {
 179         GList *l=list;
 180         while (l) {
 181                 struct boundary *b=l->data;
 182                 if (bbox_contains_bbox(&boundary->r, &b->r)) {
 183                         list=g_list_remove(list, b);
 184                         boundary->children=g_list_prepend(boundary->children, b);
 185                         l=list;
 186                 } else if (bbox_contains_bbox(&b->r, &boundary->r)) {
 187                         b->children=process_boundaries_insert(b->children, boundary);
 188                         return list;
 189                 } else
 190                         l=g_list_next(l);
 191         }
 192         return g_list_prepend(list, boundary);
 193 }
 194
 195
 196 static GList *
 197 process_boundaries_finish(GList *boundaries_list)
 198 {
 199         GList *l,*sl;
 200         GList *ret=NULL;
 201         l=boundaries_list;
 202         while (l) {
 203                 struct boundary *boundary=l->data;
 204                 int first=1;
 205                 FILE *f=NULL,*fu=NULL;
 206                 if (boundary->country) {
 207                         char *name=g_strdup_printf("country_%s_poly",boundary->iso2);
 208                         f=tempfile("",name,1);
 209                         g_free(name);
 210                 }
 211                 boundary->sorted_segments=geom_poly_segments_sort(boundary->segments, geom_poly_segment_type_way_right_side);
 212                 sl=boundary->sorted_segments;
 213                 while (sl) {
 214                         struct geom_poly_segment *gs=sl->data;
 215                         struct coord *c=gs->first;
 216                         while (c <= gs->last) {
 217                                 if (first) {
 218                                         boundary->r.l=*c;
 219                                         boundary->r.h=*c;
 220                                         first=0;
 221                                 } else
 222                                         bbox_extend(c, &boundary->r);
 223                                 c++;
 224                         }
 225                         if (f) {
 226                                 struct item_bin *ib=item_bin;
 227                                 item_bin_init(ib, type_selected_line);
 228                                 item_bin_add_coord(ib, gs->first, gs->last-gs->first+1);
 229                                 item_bin_write(ib, f);
 230                         }
 231                         if (boundary->country) {
 232                                 if (!coord_is_equal(*gs->first,*gs->last)) {
 233                                         struct item_bin *ib;
 234                                         if (!fu) {
 235                                                 char *name=g_strdup_printf("country_%s_broken",boundary->iso2);
 236                                                 fu=tempfile("",name,1);
 237                                                 g_free(name);
 238                                         }
 239                                         ib=item_bin;
 240                                         item_bin_init(ib, type_selected_point);
 241                                         item_bin_add_coord(ib, gs->first, 1);
 242                                         item_bin_write(ib, fu);
 243                                         item_bin_init(ib, type_selected_point);
 244                                         item_bin_add_coord(ib, gs->last, 1);
 245                                         item_bin_write(ib, fu);
 246                                 }
 247                         }
 248                         sl=g_list_next(sl);
 249                 }
 250                 ret=process_boundaries_insert(ret, boundary);
 251                 l=g_list_next(l);
 252                 if (f)
 253                         fclose(f);
 254                 if (fu) {
 255                         if (boundary->country)
 256                                 osm_warning("relation",item_bin_get_relationid(boundary->ib),0,"Broken country polygon '%s'\n",boundary->iso2);
 257                         fclose(fu);
 258                 }
 259
 260         }
 261 #if 0
 262         printf("hierarchy\n");
 263 #endif
 264 #if 0
 265         boundaries_list=g_list_sort(boundaries_list, boundary_bbox_compare);
 266         l=boundaries_list;
 267         while (l) {
 268                 struct boundary *boundary=l->data;
 269                 GList *l2,*ln;
 270                 ln=l2=g_list_next(l);
 271                 while (l2) {
 272                         struct boundary *boundary2=l2->data;
 273                         if (bbox_contains_bbox(&boundary2->r, &boundary->r)) {
 274                                 boundaries_list=g_list_remove(boundaries_list, boundary);
 275                                 boundary2->children=g_list_append(boundary2->children, boundary);
 276 #if 0
 277                                 printf("found\n");
 278 #endif
 279                                 break;
 280                         }
 281                         l2=g_list_next(l2);
 282                 }
 283                 l=ln;
 284         }
 285         dump_hierarchy(boundaries_list,"");
 286 #if 0
 287         printf("hierarchy done\n");
 288         printf("test\n");
 289         test(boundaries_list);
 290 #endif
 291 #endif
 292         return ret;
 293 }
 294
 295 GList *
 296 process_boundaries(FILE *boundaries, FILE *ways)
 297 {
 298         GList *boundaries_list;
 299         struct relations *relations=relations_new();
 300
 301         boundaries_list=process_boundaries_setup(boundaries, relations);
 302         relations_process(relations, NULL, ways, NULL);
 303         return process_boundaries_finish(boundaries_list);
 304 }