2 * Hic Est Leo -- OSM Data Representation
4 * (c) 2014 Martin Mares <mj@ucw.cz>
11 #include <ucw/mempool.h>
12 #include <ucw/stkstring.h>
13 #include <ucw/strtonum.h>
21 /*** Generic objects ***/
23 struct osm_id_to_obj {
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",
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>
50 osm_id_t osm_parse_id(const char *str)
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;
60 struct osm_object *osm_obj_find_by_id(enum osm_object_type type, osm_id_t id)
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;
67 static void *osm_obj_new(enum osm_object_type type, osm_id_t id, uns size)
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);
72 die("Id %ju for type %s defined twice", (uintmax_t) id, osm_obj_type_names[type]);
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]++;
80 clist_init(&o->backrefs);
85 void osm_ref_add(struct osm_object *parent, clist *list, struct osm_object *son, osm_val_t role)
87 ASSERT(parent != son);
89 struct osm_ref *ref = mp_alloc(osm_this->pool, sizeof(*ref));
92 clist_add_tail(list, &ref->n);
94 struct osm_ref *backref = mp_alloc(osm_this->pool, sizeof(*ref));
97 clist_add_tail(&son->backrefs, &backref->n);
100 void osm_obj_dump(struct osm_object *o)
105 osm_node_dump((struct osm_node *) o);
108 osm_way_dump((struct osm_way *) o);
110 case OSM_TYPE_RELATION:
111 osm_relation_dump((struct osm_relation *) o);
113 case OSM_TYPE_MULTIPOLYGON:
114 osm_multipolygon_dump((struct osm_multipolygon *) o);
121 void osm_obj_warn(struct osm_object *o, const char *mesg, ...)
124 va_start(args, mesg);
125 msg(L_WARN, "%s: %s", STK_OSM_NAME(o), stk_vprintf(mesg, args));
131 struct dict osm_key_dict, osm_value_dict;
133 void osm_obj_add_tag_raw(struct osm_object *o, osm_key_t key, osm_val_t val)
135 struct osm_tag *t = mp_alloc(osm_this->pool, sizeof(*t));
138 clist_add_tail(&o->tags, &t->n);
141 void osm_obj_add_tag(struct osm_object *o, const char *key, const char *val)
143 osm_obj_add_tag_raw(o, osm_key_encode(key), osm_val_encode(val));
146 osm_val_t osm_obj_find_tag(struct osm_object *o, osm_key_t key)
148 CLIST_FOR_EACH(struct osm_tag *, t, o->tags)
154 void osm_tag_dump(struct osm_tag *t)
156 printf("\t%s = %s\n", osm_key_decode(t->key), osm_val_decode(t->val));
159 static const char * const osm_wk_keys[] = {
161 #define P(x,y) [KEY_##x] = y,
162 #include "dict-keys.h"
167 static const char * const osm_wk_values[] = {
169 #define P(x,y) [VALUE_##x] = y,
170 #include "dict-values.h"
175 static void osm_tag_init(void)
177 dict_init(&osm_key_dict, osm_wk_keys);
178 dict_init(&osm_value_dict, osm_wk_values);
183 struct osm_node *osm_node_new(osm_id_t id)
185 struct osm_node *n = osm_obj_new(OSM_TYPE_NODE, id, sizeof(*n));
189 void osm_node_dump(struct osm_node *n)
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)
196 void osm_node_dump_all(void)
198 printf("Known nodes:\n");
199 CLIST_FOR_EACH(struct osm_node *, n, osm_this->obj_list[OSM_TYPE_NODE])
206 struct osm_way *osm_way_new(osm_id_t id)
208 struct osm_way *w = osm_obj_new(OSM_TYPE_WAY, id, sizeof(*w));
209 clist_init(&w->nodes);
213 void osm_way_add_node(struct osm_way *w, struct osm_node *n)
215 osm_ref_add(&w->o, &w->nodes, &n->o, 0);
218 void osm_way_dump(struct osm_way *w)
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)
223 OSM_FOR_EACH_BEGIN(struct osm_node *, n, w->nodes)
225 printf("\tNode %ju\n", (uintmax_t) n->o.id);
230 void osm_way_dump_all(void)
232 printf("Known ways:\n");
233 CLIST_FOR_EACH(struct osm_way *, w, osm_this->obj_list[OSM_TYPE_WAY])
238 bool osm_way_cyclic_p(struct osm_way *w)
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);
249 struct osm_relation *osm_relation_new(osm_id_t id)
251 struct osm_relation *r = osm_obj_new(OSM_TYPE_RELATION, id, sizeof(*r));
252 clist_init(&r->members);
256 void osm_relation_add_member(struct osm_relation *r, struct osm_object *o, const char *role)
258 osm_ref_add(&r->o, &r->members, o, (role && role[0] ? osm_val_encode(role) : 0));
261 void osm_relation_dump(struct osm_relation *r)
263 printf("Relation %ju\n", (uintmax_t) r->o.id);
264 CLIST_FOR_EACH(struct osm_tag *, t, r->o.tags)
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);
270 void osm_relation_dump_all(void)
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);
278 /*** Multipolygons ***/
280 void osm_multipolygon_dump(struct osm_multipolygon *m)
282 printf("Multipolygon %ju\n", (uintmax_t) m->o.id);
283 CLIST_FOR_EACH(struct osm_tag *, t, m->o.tags)
285 CLIST_FOR_EACH(struct osm_mpg_boundary *, b, m->boundaries)
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);
293 void osm_multipolygon_dump_all(void)
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);
301 static struct mempool *mpg_pool;
302 static struct osm_multipolygon *mpg_current;
306 struct osm_object *o;
307 clist edges; // of mpg_edge's
313 struct mpg_edge *twin;
314 struct mpg_vertex *dest;
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>
328 static void mpg_insert_way(struct osm_way *w)
330 struct mpg_vertex *prev = NULL;
331 OSM_FOR_EACH_BEGIN(struct osm_node *, n, w->nodes)
334 struct mpg_vertex *v = mpg_vertex_hash_lookup(n->o.id, &new);
337 clist_init(&v->edges);
343 struct mpg_edge *e1 = mp_alloc_zero(mpg_pool, sizeof(*e1));
344 struct mpg_edge *e2 = mp_alloc_zero(mpg_pool, sizeof(*e2));
347 clist_add_tail(&prev->edges, &e1->n);
350 clist_add_tail(&v->edges, &e2->n);
357 static void UNUSED mpg_dump(void)
359 printf("=== Multipolygon graph for relation %ju ===\n", (uintmax_t) mpg_current->o.id);
360 HASH_FOR_ALL(mpg_vertex_hash, v)
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);
370 static void mpg_walk_boundary(struct osm_multipolygon *m, bool inner)
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)
378 struct osm_mpg_boundary *b = mp_alloc(osm_this->pool, sizeof(*b));
379 clist_add_tail(&m->boundaries, &b->n);
381 clist_init(&b->nodes);
383 struct mpg_vertex *w = v;
384 while (w && !w->visited)
387 struct osm_ref *f = mp_alloc(osm_this->pool, sizeof(*f));
388 clist_add_tail(&b->nodes, &f->n);
392 struct mpg_vertex *dest = NULL;
393 CLIST_FOR_EACH(struct mpg_edge *, e, w->edges)
400 osm_obj_warn(&mpg_current->o, "Suspicious vertex degree of node %ju", (uintmax_t) w->o->id);
415 osm_obj_warn(&mpg_current->o, "Boundary not closed");
417 osm_obj_warn(&mpg_current->o, "Boundary not closed at node %ju", (uintmax_t) w->o->id);
419 struct osm_ref *f = mp_alloc(osm_this->pool, sizeof(*f));
420 clist_add_tail(&b->nodes, &f->n);
428 static void osm_multipolygon_make(struct osm_relation *r)
430 struct osm_multipolygon *m = osm_obj_new(OSM_TYPE_MULTIPOLYGON, r->o.id, sizeof(*m));
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);
437 for (int inner=0; inner<2; inner++)
440 mpg_pool = mp_new(4096);
441 mpg_vertex_hash_init();
443 CLIST_FOR_EACH(struct osm_ref *, f, r->members)
445 struct osm_object *o = f->o;
446 if (f->role != VALUE_INNER && f->role != VALUE_OUTER)
449 osm_obj_warn(o, "Unknown role %s in multipolygon relation", osm_val_decode(f->role));
452 if ((f->role == VALUE_INNER) != inner)
454 if (o->type == OSM_TYPE_WAY)
455 mpg_insert_way((struct osm_way *) o);
457 osm_obj_warn(o, "Only ways are supported in multipolygon boundaries");
460 if (debug_dump_multipolygons)
463 mpg_walk_boundary(m, inner);
468 void osm_make_multipolygons(void)
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)
475 osm_multipolygon_make(r);
478 msg(L_INFO, "Converted %u relations to multipolygons", mpg_cnt);
483 static projPJ osm_pj;
485 void osm_project(const char *spec)
487 osm_pj = pj_init_plus(spec);
489 die("Unable to initialize projection %s", spec);
491 CLIST_FOR_EACH(struct osm_node *, n, osm_this->obj_list[OSM_TYPE_NODE])
494 p.u = n->x * DEG_TO_RAD;
495 p.v = n->y * DEG_TO_RAD;
496 p = pj_fwd(p, osm_pj);
502 /*** Object centers ***/
504 bool osm_obj_center(struct osm_object *o, double *xp, double *yp)
510 struct osm_node *n = (struct osm_node *) o;
517 struct osm_way *w = (struct osm_way *) o;
518 double sx = 0, sy = 0;
520 OSM_FOR_EACH_BEGIN(struct osm_node *, n, w->nodes)
533 case OSM_TYPE_MULTIPOLYGON:
535 struct osm_multipolygon *m = (struct osm_multipolygon *) o;
536 double sx = 0, sy = 0;
538 CLIST_FOR_EACH(struct osm_mpg_boundary *, b, m->boundaries)
542 OSM_FOR_EACH_BEGIN(struct osm_node *, n, b->nodes)
563 struct osm *osm_init(void)
565 struct mempool *mp = mp_new(65536);
566 struct osm *osm = mp_alloc_zero(mp, sizeof(*osm));
569 for (int i=0; i<OSM_TYPE_MAX; i++)
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]);
587 osm_relation_dump_all();
588 osm_multipolygon_dump_all();
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]);