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