]> mj.ucw.cz Git - leo.git/blob - osm.c
Parametrized drawing of map scale
[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 <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 }