]> mj.ucw.cz Git - leo.git/blob - osm.c
Added an interface for overriding tags
[leo.git] / 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 }