osm.c

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