osm.c

   1 /*
   2  *      Hic Est Leo -- OSM Data Representation
   3  *
   4  *      (c) 2014 Martin Mares <mj@ucw.cz>
   5  */
   6
   7 #include <ucw/lib.h>
   8 #include <ucw/gary.h>
   9 #include <ucw/mempool.h>
  10 #include <ucw/stkstring.h>
  11 #include <ucw/strtonum.h>
  12
  13 #include <stdarg.h>
  14 #include <stdio.h>
  15 #include <proj_api.h>
  16
  17 #include "leo.h"
  18 #include "osm.h"
  19
  20 struct osm *osm_this;
  21
  22 /*** Generic objects ***/
  23
  24 struct osm_id_to_obj {
  25   osm_id_t id;
  26   struct osm_object *o;
  27 };
  28
  29 #define P(x) [OSM_TYPE_##x] = #x,
  30 const char * const osm_obj_type_names[OSM_TYPE_MAX] = {
  31   [OSM_TYPE_INVALID] = "Invalid",
  32   [OSM_TYPE_NODE] = "Node",
  33   [OSM_TYPE_WAY] = "Way",
  34   [OSM_TYPE_RELATION] = "Relation",
  35   [OSM_TYPE_MULTIPOLYGON] = "Multipolygon",
  36 };
  37 #undef P
  38
  39 #define HASH_NODE struct osm_id_to_obj
  40 #define HASH_PREFIX(x) osm_id_hash_##x
  41 #define HASH_KEY_ATOMIC id
  42 #define HASH_ATOMIC_TYPE osm_id_t
  43 #define HASH_WANT_FIND
  44 #define HASH_WANT_LOOKUP
  45 #define HASH_TABLE_VARS struct mempool *pool;
  46 #define HASH_USE_POOL table->pool
  47 #define HASH_ZERO_FILL
  48 #define HASH_TABLE_DYNAMIC
  49 #include <ucw/hashtable.h>
  50
  51 osm_id_t osm_parse_id(const char *str)
  52 {
  53   uintmax_t id;
  54   const char *err = str_to_uintmax(&id, str, NULL, STN_WHOLE | STN_MINUS | 10);
  55   if (err || id != (osm_id_t)id)
  56     return OSM_INVALID_ID;
  57   else
  58     return id;
  59 }
  60
  61 struct osm_object *osm_obj_find_by_id(enum osm_object_type type, osm_id_t id)
  62 {
  63   ASSERT(type != OSM_TYPE_INVALID && type < OSM_TYPE_MAX);
  64   struct osm_id_to_obj *ii = osm_id_hash_find(osm_this->id_hash[type], id);
  65   return ii ? ii->o : NULL;
  66 }
  67
  68 static void *osm_obj_new(enum osm_object_type type, osm_id_t id, uns size)
  69 {
  70   ASSERT(type != OSM_TYPE_INVALID && type < OSM_TYPE_MAX);
  71   struct osm_id_to_obj *ii = osm_id_hash_lookup(osm_this->id_hash[type], id);
  72   if (ii->o)
  73     die("Id %ju for type %s defined twice", (uintmax_t) id, osm_obj_type_names[type]);
  74
  75   struct osm_object *o = mp_alloc_zero(osm_this->pool, size);
  76   clist_add_tail(&osm_this->obj_list[type], &o->n);
  77   osm_this->obj_cnt[type]++;
  78   o->type = type;
  79   o->id = id;
  80   clist_init(&o->tags);
  81   clist_init(&o->backrefs);
  82   ii->o = o;
  83   return o;
  84 }
  85
  86 void osm_ref_add(struct osm_object *parent, clist *list, struct osm_object *son, osm_val_t role)
  87 {
  88   ASSERT(parent != son);
  89
  90   struct osm_ref *ref = mp_alloc(osm_this->pool, sizeof(*ref));
  91   ref->o = son;
  92   ref->role = role;
  93   clist_add_tail(list, &ref->n);
  94
  95   struct osm_ref *backref = mp_alloc(osm_this->pool, sizeof(*ref));
  96   backref->o = parent;
  97   backref->role = 0;
  98   clist_add_tail(&son->backrefs, &backref->n);
  99 }
 100
 101 void osm_obj_dump(struct osm_object *o)
 102 {
 103   switch (o->type)
 104     {
 105     case OSM_TYPE_NODE:
 106       osm_node_dump((struct osm_node *) o);
 107       break;
 108     case OSM_TYPE_WAY:
 109       osm_way_dump((struct osm_way *) o);
 110       break;
 111     case OSM_TYPE_RELATION:
 112       osm_relation_dump((struct osm_relation *) o);
 113       break;
 114     case OSM_TYPE_MULTIPOLYGON:
 115       osm_multipolygon_dump((struct osm_multipolygon *) o);
 116       break;
 117     default:
 118       ASSERT(0);
 119     }
 120 }
 121
 122 void osm_obj_warn(struct osm_object *o, const char *mesg, ...)
 123 {
 124   va_list args;
 125   va_start(args, mesg);
 126   msg(L_WARN, "%s: %s", STK_OSM_NAME(o), stk_vprintf(mesg, args));
 127   va_end(args);
 128 }
 129
 130 /*** Tags ***/
 131
 132 struct dict osm_key_dict, osm_value_dict;
 133
 134 void osm_obj_add_tag_raw(struct osm_object *o, osm_key_t key, osm_val_t val)
 135 {
 136   struct osm_tag *t = mp_alloc(osm_this->pool, sizeof(*t));
 137   t->key = key;
 138   t->val = val;
 139   clist_add_tail(&o->tags, &t->n);
 140 }
 141
 142 void osm_obj_add_tag(struct osm_object *o, const char *key, const char *val)
 143 {
 144   osm_obj_add_tag_raw(o, osm_key_encode(key), osm_val_encode(val));
 145 }
 146
 147 osm_val_t osm_obj_find_tag(struct osm_object *o, osm_key_t key)
 148 {
 149   CLIST_FOR_EACH(struct osm_tag *, t, o->tags)
 150     if (t->key == key)
 151       return t->val;
 152   return 0;
 153 }
 154
 155 void osm_tag_dump(struct osm_tag *t)
 156 {
 157   printf("\t%s = %s\n", osm_key_decode(t->key), osm_val_decode(t->val));
 158 }
 159
 160 static const char * const osm_wk_keys[] = {
 161   NULL,
 162 #define P(x,y) [KEY_##x] = y,
 163 #include "dict-keys.h"
 164 #undef P
 165   NULL
 166 };
 167
 168 static const char * const osm_wk_values[] = {
 169   NULL,
 170 #define P(x,y) [VALUE_##x] = y,
 171 #include "dict-values.h"
 172 #undef P
 173   NULL
 174 };
 175
 176 static void osm_tag_init(void)
 177 {
 178   dict_init(&osm_key_dict, osm_wk_keys);
 179   dict_init(&osm_value_dict, osm_wk_values);
 180 }
 181
 182 /*** Nodes ***/
 183
 184 struct osm_node *osm_node_new(osm_id_t id)
 185 {
 186   struct osm_node *n = osm_obj_new(OSM_TYPE_NODE, id, sizeof(*n));
 187   return n;
 188 }
 189
 190 void osm_node_dump(struct osm_node *n)
 191 {
 192   printf("Node %ju: (%f,%f)\n", (uintmax_t) n->o.id, n->x, n->y);
 193   CLIST_FOR_EACH(struct osm_tag *, t, n->o.tags)
 194     osm_tag_dump(t);
 195 }
 196
 197 void osm_node_dump_all(void)
 198 {
 199   printf("Known nodes:\n");
 200   CLIST_FOR_EACH(struct osm_node *, n, osm_this->obj_list[OSM_TYPE_NODE])
 201     osm_node_dump(n);
 202   putchar('\n');
 203 }
 204
 205 /*** Ways ***/
 206
 207 struct osm_way *osm_way_new(osm_id_t id)
 208 {
 209   struct osm_way *w = osm_obj_new(OSM_TYPE_WAY, id, sizeof(*w));
 210   clist_init(&w->nodes);
 211   return w;
 212 }
 213
 214 void osm_way_add_node(struct osm_way *w, struct osm_node *n)
 215 {
 216   osm_ref_add(&w->o, &w->nodes, &n->o, 0);
 217 }
 218
 219 void osm_way_dump(struct osm_way *w)
 220 {
 221   printf("Way %ju%s\n", (uintmax_t) w->o.id, (osm_way_cyclic_p(w) ? " (cyclic)" : ""));
 222   CLIST_FOR_EACH(struct osm_tag *, t, w->o.tags)
 223     osm_tag_dump(t);
 224   OSM_FOR_EACH_BEGIN(struct osm_node *, n, w->nodes)
 225     {
 226       printf("\tNode %ju\n", (uintmax_t) n->o.id);
 227     }
 228   OSM_FOR_EACH_END;
 229 }
 230
 231 void osm_way_dump_all(void)
 232 {
 233   printf("Known ways:\n");
 234   CLIST_FOR_EACH(struct osm_way *, w, osm_this->obj_list[OSM_TYPE_WAY])
 235     osm_way_dump(w);
 236   putchar('\n');
 237 }
 238
 239 bool osm_way_cyclic_p(struct osm_way *w)
 240 {
 241   struct osm_ref *first_ref = clist_head(&w->nodes);
 242   struct osm_ref *last_ref = clist_tail(&w->nodes);
 243   return (first_ref && last_ref &&
 244           first_ref != last_ref &&
 245           first_ref->o == last_ref->o);
 246 }
 247
 248 /*** Relations ***/
 249
 250 struct osm_relation *osm_relation_new(osm_id_t id)
 251 {
 252   struct osm_relation *r = osm_obj_new(OSM_TYPE_RELATION, id, sizeof(*r));
 253   clist_init(&r->members);
 254   return r;
 255 }
 256
 257 void osm_relation_add_member(struct osm_relation *r, struct osm_object *o, const char *role)
 258 {
 259   osm_ref_add(&r->o, &r->members, o, (role && role[0] ? osm_val_encode(role) : 0));
 260 }
 261
 262 void osm_relation_dump(struct osm_relation *r)
 263 {
 264   printf("Relation %ju\n", (uintmax_t) r->o.id);
 265   CLIST_FOR_EACH(struct osm_tag *, t, r->o.tags)
 266     osm_tag_dump(t);
 267   CLIST_FOR_EACH(struct osm_ref *, f, r->members)
 268     printf("\tRole %s: %s %ju\n", (f->role ? osm_val_decode(f->role) : "<none>"), osm_obj_type_names[f->o->type], (uintmax_t) f->o->id);
 269 }
 270
 271 void osm_relation_dump_all(void)
 272 {
 273   printf("Known relations:\n");
 274   CLIST_FOR_EACH(struct osm_relation *, r, osm_this->obj_list[OSM_TYPE_RELATION])
 275     osm_relation_dump(r);
 276   putchar('\n');
 277 }
 278
 279 /*** Multipolygons ***/
 280
 281 void osm_multipolygon_dump(struct osm_multipolygon *m)
 282 {
 283   printf("Multipolygon %ju\n", (uintmax_t) m->o.id);
 284   CLIST_FOR_EACH(struct osm_tag *, t, m->o.tags)
 285     osm_tag_dump(t);
 286   CLIST_FOR_EACH(struct osm_mpg_boundary *, b, m->boundaries)
 287     {
 288       printf("\tBoundary inner=%u\n", b->inner);
 289       CLIST_FOR_EACH(struct osm_ref *, f, b->nodes)
 290         printf("\t\tNode %ju\n", (uintmax_t) f->o->id);
 291     }
 292 }
 293
 294 void osm_multipolygon_dump_all(void)
 295 {
 296   printf("Known multipolygons:\n");
 297   CLIST_FOR_EACH(struct osm_multipolygon *, r, osm_this->obj_list[OSM_TYPE_MULTIPOLYGON])
 298     osm_multipolygon_dump(r);
 299   putchar('\n');
 300 }
 301
 302 static struct mempool *mpg_pool;
 303 static struct osm_multipolygon *mpg_current;
 304
 305 struct mpg_vertex {
 306   osm_id_t id;
 307   struct osm_object *o;
 308   clist edges;                  // of mpg_edge's
 309   bool visited;
 310 };
 311
 312 struct mpg_edge {
 313   cnode n;
 314   struct mpg_edge *twin;
 315   struct mpg_vertex *dest;
 316   bool used;
 317 };
 318
 319 #define HASH_NODE struct mpg_vertex
 320 #define HASH_PREFIX(x) mpg_vertex_hash_##x
 321 #define HASH_KEY_ATOMIC id
 322 #define HASH_ATOMIC_TYPE osm_id_t
 323 #define HASH_USE_POOL mpg_pool
 324 #define HASH_TABLE_ALLOC
 325 #define HASH_WANT_LOOKUP
 326 #define HASH_LOOKUP_DETECT_NEW
 327 #include <ucw/hashtable.h>
 328
 329 static void mpg_insert_way(struct osm_way *w)
 330 {
 331   struct mpg_vertex *prev = NULL;
 332   OSM_FOR_EACH_BEGIN(struct osm_node *, n, w->nodes)
 333     {
 334       int new = 0;
 335       struct mpg_vertex *v = mpg_vertex_hash_lookup(n->o.id, &new);
 336       if (new)
 337         {
 338           clist_init(&v->edges);
 339           v->visited = 0;
 340           v->o = &n->o;
 341         }
 342       if (prev)
 343         {
 344           struct mpg_edge *e1 = mp_alloc_zero(mpg_pool, sizeof(*e1));
 345           struct mpg_edge *e2 = mp_alloc_zero(mpg_pool, sizeof(*e2));
 346           e1->twin = e2;
 347           e1->dest = v;
 348           clist_add_tail(&prev->edges, &e1->n);
 349           e2->twin = e1;
 350           e2->dest = prev;
 351           clist_add_tail(&v->edges, &e2->n);
 352         }
 353       prev = v;
 354     }
 355   OSM_FOR_EACH_END;
 356 }
 357
 358 static void UNUSED mpg_dump(void)
 359 {
 360   printf("=== Multipolygon graph for relation %ju ===\n", (uintmax_t) mpg_current->o.id);
 361   HASH_FOR_ALL(mpg_vertex_hash, v)
 362     {
 363       printf("Vertex %ju\n", (uintmax_t) v->id);
 364       CLIST_FOR_EACH(struct mpg_edge *, e, v->edges)
 365         printf("\t-> %ju\n", (uintmax_t) e->dest->id);
 366     }
 367   HASH_END_FOR;
 368   puts("=== End ===");
 369 }
 370
 371 static void mpg_walk_boundary(struct osm_multipolygon *m, bool inner)
 372 {
 373   // FIXME: Replace by a better algorithm, which respects geometry
 374   // and is able to cope with higher degree vertices.
 375   HASH_FOR_ALL(mpg_vertex_hash, v)
 376     {
 377       if (!v->visited)
 378         {
 379           struct osm_mpg_boundary *b = mp_alloc(osm_this->pool, sizeof(*b));
 380           clist_add_tail(&m->boundaries, &b->n);
 381           b->inner = inner;
 382           clist_init(&b->nodes);
 383
 384           struct mpg_vertex *w = v;
 385           while (w && !w->visited)
 386             {
 387               w->visited = 1;
 388               struct osm_ref *f = mp_alloc(osm_this->pool, sizeof(*f));
 389               clist_add_tail(&b->nodes, &f->n);
 390               f->o = w->o;
 391               f->role = 0;
 392
 393               struct mpg_vertex *dest = NULL;
 394               CLIST_FOR_EACH(struct mpg_edge *, e, w->edges)
 395                 {
 396                   if (e->used)
 397                     continue;
 398                   if (dest)
 399                     {
 400                       if (w != v)
 401                         osm_obj_warn(&mpg_current->o, "Suspicious vertex degree of node %ju", (uintmax_t) w->o->id);
 402                       break;
 403                     }
 404                   else
 405                     {
 406                       dest = e->dest;
 407                       e->used = 1;
 408                       e->twin->used = 1;
 409                     }
 410                 }
 411
 412               w = dest;
 413             }
 414
 415           if (!w)
 416             osm_obj_warn(&mpg_current->o, "Boundary not closed");
 417           else if (w != v)
 418             osm_obj_warn(&mpg_current->o, "Boundary not closed at node %ju", (uintmax_t) w->o->id);
 419
 420           struct osm_ref *f = mp_alloc(osm_this->pool, sizeof(*f));
 421           clist_add_tail(&b->nodes, &f->n);
 422           f->o = v->o;
 423           f->role = 0;
 424         }
 425     }
 426   HASH_END_FOR;
 427 }
 428
 429 static void osm_multipolygon_make(struct osm_relation *r)
 430 {
 431   struct osm_multipolygon *m = osm_obj_new(OSM_TYPE_MULTIPOLYGON, r->o.id, sizeof(*m));
 432   mpg_current = m;
 433   m->rel = r;
 434   CLIST_FOR_EACH(struct osm_tag *, t, r->o.tags)
 435     osm_obj_add_tag_raw(&m->o, t->key, t->val);
 436   clist_init(&m->boundaries);
 437
 438   for (int inner=0; inner<2; inner++)
 439     {
 440       if (!mpg_pool)
 441         mpg_pool = mp_new(4096);
 442       mpg_vertex_hash_init();
 443
 444       CLIST_FOR_EACH(struct osm_ref *, f, r->members)
 445         {
 446           struct osm_object *o = f->o;
 447           if (f->role != VALUE_INNER && f->role != VALUE_OUTER)
 448             {
 449               if (!inner)
 450                 osm_obj_warn(o, "Unknown role %s in multipolygon relation", osm_val_decode(f->role));
 451               continue;
 452             }
 453           if ((f->role == VALUE_INNER) != inner)
 454             continue;
 455           if (o->type == OSM_TYPE_WAY)
 456             mpg_insert_way((struct osm_way *) o);
 457           else
 458             osm_obj_warn(o, "Only ways are supported in multipolygon boundaries");
 459         }
 460
 461       if (debug_dump_multipolygons)
 462         mpg_dump();
 463
 464       mpg_walk_boundary(m, inner);
 465       mp_flush(mpg_pool);
 466     }
 467 }
 468
 469 void osm_make_multipolygons(void)
 470 {
 471   uns mpg_cnt = 0;
 472
 473   CLIST_FOR_EACH(struct osm_relation *, r, osm_this->obj_list[OSM_TYPE_RELATION])
 474     if (osm_obj_find_tag(&r->o, KEY_TYPE) == VALUE_MULTIPOLYGON)
 475       {
 476         osm_multipolygon_make(r);
 477         mpg_cnt++;
 478       }
 479   msg(L_INFO, "Converted %u relations to multipolygons", mpg_cnt);
 480 }
 481
 482 /*** Projection ***/
 483
 484 static projPJ osm_pj;
 485
 486 void osm_project(const char *spec)
 487 {
 488   osm_pj = pj_init_plus(spec);
 489   if (!osm_pj)
 490     die("Unable to initialize projection %s", spec);
 491
 492   CLIST_FOR_EACH(struct osm_node *, n, osm_this->obj_list[OSM_TYPE_NODE])
 493     {
 494       projUV p;
 495       p.u = n->x * DEG_TO_RAD;
 496       p.v = n->y * DEG_TO_RAD;
 497       p = pj_fwd(p, osm_pj);
 498       n->x = p.u;
 499       n->y = p.v;
 500     }
 501 }
 502
 503 /*** Object centers ***/
 504
 505 bool osm_obj_center(struct osm_object *o, double *xp, double *yp)
 506 {
 507   switch (o->type)
 508     {
 509     case OSM_TYPE_NODE:
 510       {
 511         struct osm_node *n = (struct osm_node *) o;
 512         *xp = n->x;
 513         *yp = n->y;
 514         return 1;
 515       }
 516     case OSM_TYPE_WAY:
 517       {
 518         struct osm_way *w = (struct osm_way *) o;
 519         double sx = 0, sy = 0;
 520         uns nn = 0;
 521         OSM_FOR_EACH_BEGIN(struct osm_node *, n, w->nodes)
 522           {
 523             sx += n->x;
 524             sy += n->y;
 525             nn++;
 526           }
 527         OSM_FOR_EACH_END;
 528         if (!nn)
 529           return 0;
 530         *xp = sx / nn;
 531         *yp = sy / nn;
 532         return 1;
 533       }
 534     case OSM_TYPE_MULTIPOLYGON:
 535       {
 536         struct osm_multipolygon *m = (struct osm_multipolygon *) o;
 537         double sx = 0, sy = 0;
 538         uns nn = 0;
 539         CLIST_FOR_EACH(struct osm_mpg_boundary *, b, m->boundaries)
 540           {
 541             if (b->inner)
 542               continue;
 543             OSM_FOR_EACH_BEGIN(struct osm_node *, n, b->nodes)
 544               {
 545                 sx += n->x;
 546                 sy += n->y;
 547                 nn++;
 548               }
 549             OSM_FOR_EACH_END;
 550           }
 551         if (!nn)
 552           return 0;
 553         *xp = sx / nn;
 554         *yp = sy / nn;
 555         return 1;
 556       }
 557     default:
 558       return 0;
 559     }
 560 }
 561
 562 /*** Globals ***/
 563
 564 struct osm *osm_init(void)
 565 {
 566   struct mempool *mp = mp_new(65536);
 567   struct osm *osm = mp_alloc_zero(mp, sizeof(*osm));
 568   osm->pool = mp;
 569
 570   for (int i=0; i<OSM_TYPE_MAX; i++)
 571     {
 572       clist_init(&osm->obj_list[i]);
 573       osm->id_hash[i] = mp_alloc(mp, sizeof(struct osm_id_hash_table));
 574       osm->id_hash[i]->pool = mp;
 575       osm_id_hash_init(osm->id_hash[i]);
 576     }
 577
 578   if (!osm_this)
 579     osm_tag_init();
 580   osm_this = osm;
 581   return osm;
 582 }
 583
 584 void osm_dump(void)
 585 {
 586   osm_node_dump_all();
 587   osm_way_dump_all();
 588   osm_relation_dump_all();
 589   osm_multipolygon_dump_all();
 590 }
 591
 592 void osm_stats(void)
 593 {
 594   msg(L_INFO, "Loaded %u nodes, %u ways, %u relations",
 595     osm_this->obj_cnt[OSM_TYPE_NODE],
 596     osm_this->obj_cnt[OSM_TYPE_WAY],
 597     osm_this->obj_cnt[OSM_TYPE_RELATION]);
 598 }