simplify.c

   1 /*
   2  *      Hic Est Leo -- Map Simplification
   3  *
   4  *      (c) 2022 Martin Mares <mj@ucw.cz>
   5  */
   6
   7 // #define LOCAL_DEBUG
   8 // #pragma GCC optimize("-O0")
   9
  10 #include "leo.h"
  11
  12 #include <ucw/lib.h>
  13 #include <ucw/clists.h>
  14 #include <ucw/mempool.h>
  15
  16 #include <stdio.h>
  17 #include <math.h>
  18
  19 #include "osm.h"
  20 #include "map.h"
  21 #include "sym.h"
  22 #include "simplify.h"
  23
  24 static struct mempool *simp_pool;
  25 static struct osm *simp_osm;
  26 static osm_id_t simp_last_id;
  27
  28 struct coords {
  29   double x, y;
  30 };
  31
  32 struct simp_way_ref {
  33   cnode n;
  34   struct simp_node *snode;
  35   struct symbol *sym;
  36   z_index_t zindex;
  37   struct osm_way *way;
  38   struct osm_node *node;
  39   struct simp_way_ref *prev_on_way;
  40   struct simp_way_ref *next_on_way;
  41   byte merge_done;
  42 };
  43
  44 struct simp_node {
  45   union {
  46     struct coords c;
  47     byte raw_coords[sizeof(struct coords)];
  48   };
  49   clist way_refs;
  50 };
  51
  52 static void simp_hash_init_data(struct simp_node *s)
  53 {
  54   clist_init(&s->way_refs);
  55 }
  56
  57 #define HASH_NODE struct simp_node
  58 #define HASH_PREFIX(x) simp_hash_##x
  59 #define HASH_KEY_MEMORY raw_coords
  60 #define HASH_KEY_SIZE sizeof(struct coords)
  61 #define HASH_WANT_LOOKUP
  62 #define HASH_GIVE_INIT_DATA
  63 #define HASH_USE_POOL simp_pool
  64 #define HASH_TABLE_ALLOC
  65 #include <ucw/hashtable.h>
  66
  67 static struct simp_node *simp_lookup_node(struct osm_node *n)
  68 {
  69   struct coords c = { .x = n->x, .y = n->y };
  70   return simp_hash_lookup((byte *) &c);
  71 }
  72
  73 static void simp_register_symbol(struct symbol *sym, z_index_t zindex)
  74 {
  75   struct osm_object *o = sym->o;
  76
  77   switch (o->type)
  78     {
  79     case OSM_TYPE_NODE:
  80       simp_lookup_node((struct osm_node *) o);
  81       break;
  82     case OSM_TYPE_WAY:
  83       {
  84         struct osm_way *w = (struct osm_way *) o;
  85         struct simp_way_ref *wr_last = NULL;
  86         struct osm_node *prev_n = NULL;
  87
  88 #if 0
  89         for (uint i=0; i<2; i++)
  90           {
  91             struct osm_node *n = (struct osm_node *) (i ? osm_ref_head(&w->nodes) : osm_ref_tail(&w->nodes));
  92             struct sym_point *sp = sym_point_new(&n->o);
  93             sp->shape = VALUE_CIRCLE;
  94             sp->size = 1;
  95             sp->fill_color = 0x0000ff;
  96             sp->fill_opacity = 1;
  97             sp->do_fill = 1;
  98             sym_plan(sp, 100);
  99           }
 100 #endif
 101
 102         if (clist_size(&w->nodes) < 2)
 103           break;
 104
 105         OSM_FOR_EACH_BEGIN(struct osm_node *, n, w->nodes)
 106           {
 107             if (n == prev_n)
 108               continue;
 109
 110             struct simp_node *s = simp_lookup_node(n);
 111             struct simp_way_ref *wref = mp_alloc(simp_pool, sizeof(*wref));
 112             wref->snode = s;
 113             wref->sym = sym;
 114             wref->zindex = zindex;
 115             wref->node = n;
 116             wref->way = w;
 117             wref->prev_on_way = wr_last;
 118             wref->next_on_way = NULL;
 119             if (wr_last)
 120               wr_last->next_on_way = wref;
 121             wr_last = wref;
 122             wref->merge_done = 0;
 123             clist_add_tail(&s->way_refs, &wref->n);
 124
 125             prev_n = n;
 126           }
 127         OSM_FOR_EACH_END;
 128         break;
 129       }
 130     default:
 131       die("Simplify: Unsupported symbol type %u", o->type);
 132     }
 133 }
 134
 135 static struct simp_way_ref *wref_other_end(struct simp_way_ref *wr)
 136 {
 137   if (wr->prev_on_way)
 138     {
 139       while (wr->prev_on_way)
 140         wr = wr->prev_on_way;
 141     }
 142   else
 143     {
 144       while (wr->next_on_way)
 145         wr = wr->next_on_way;
 146     }
 147   return wr;
 148 }
 149
 150 static struct simp_way_ref *wref_only_other(struct simp_node *sn, struct simp_way_ref *in_wr)
 151 {
 152   struct simp_way_ref *out_wr = NULL;
 153
 154   CLIST_FOR_EACH(struct simp_way_ref *, wr, sn->way_refs)
 155     {
 156       if (wr == in_wr)
 157         ;
 158       else if (!out_wr)
 159         out_wr = wr;
 160       else
 161         return NULL;
 162     }
 163
 164   return out_wr;
 165 }
 166
 167 /*** Merging of ways ***/
 168
 169 static struct simp_way_ref **merge_wrefs;
 170 static uint num_merged_ways, num_merged_segments;
 171
 172 static void simp_merge_way(struct simp_node *s)
 173 {
 174   // XXX: This is grossly over-simplified. We assume that every way generates
 175   // at most one symbol, which is definitely not the case for ways rendered
 176   // with casing. But it should be sufficient for now.
 177
 178   uint nrefs = clist_size(&s->way_refs);
 179   if (nrefs != 2)
 180     return;
 181
 182   struct simp_way_ref *wr1, *wr2, *wr;
 183   wr1 = clist_head(&s->way_refs);
 184   wr2 = clist_tail(&s->way_refs);
 185   if (!(!wr1->prev_on_way != !wr1->next_on_way && !wr2->prev_on_way != !wr2->next_on_way))
 186     return;
 187   if (wr1->merge_done || wr2->merge_done)
 188     return;
 189
 190   wr = wr1;
 191   DBG("Merge: Starting with wr %p", wr);
 192
 193   for (;;)
 194     {
 195       wr->merge_done = 1;
 196       struct simp_way_ref *or = wref_other_end(wr);
 197       struct simp_node *on = or->snode;
 198
 199       struct simp_way_ref *cr = wref_only_other(on, or);
 200       DBG("XXX: wr=%p or=%p cr=%p", wr, or, cr);
 201       if (!cr || !sym_same_attrs_p(or->sym, cr->sym))
 202         {
 203           DBG("Merge: Back stop at %p", cr);
 204           break;
 205         }
 206
 207       DBG("Merge: Back to %p", cr);
 208       wr = cr;
 209
 210       if (wr == wr1)
 211         {
 212           DBG("Merge: Loop detected");
 213           return;
 214         }
 215     }
 216
 217   // Now, we are at the beginning/end of a single way
 218
 219   DBG("Merge: Back to %p", wr);
 220   wr = wref_other_end(wr);
 221   DBG("Merge: Other end is %p", wr);
 222   GARY_RESIZE(merge_wrefs, 0);
 223   *GARY_PUSH(merge_wrefs) = wr;
 224
 225   for (;;)
 226     {
 227       wr->merge_done = 1;
 228       struct simp_way_ref *or = wref_other_end(wr);
 229       struct simp_node *on = or->snode;
 230
 231       struct simp_way_ref *cr = wref_only_other(on, or);
 232       if (!cr || !sym_same_attrs_p(or->sym, cr->sym))
 233         {
 234           DBG("Merge: Fwd stop at %p", cr);
 235           break;
 236         }
 237
 238       DBG("Merge: Fwd to %p", cr);
 239       *GARY_PUSH(merge_wrefs) = cr;
 240       wr = cr;
 241     }
 242
 243   if (GARY_SIZE(merge_wrefs) < 2)
 244     return;
 245
 246   DBG("Will merge");
 247   num_merged_ways++;
 248
 249   struct osm_way *nw = osm_way_new(++simp_last_id);
 250   struct symbol *main_sym = NULL;
 251
 252   for (uint i=0; i < GARY_SIZE(merge_wrefs); i++)
 253     {
 254       wr = merge_wrefs[i];
 255       clist_remove(&wr->n);
 256       if (!i)
 257         {
 258           osm_way_add_node(nw, wr->node);
 259           main_sym = wr->sym;
 260           main_sym->o = &nw->o;
 261         }
 262       else
 263         sym_disable(wr->sym);
 264
 265       if (wr->prev_on_way)
 266         {
 267           while (wr = wr->prev_on_way)
 268             {
 269               clist_remove(&wr->n);
 270               osm_way_add_node(nw, wr->node);
 271             }
 272         }
 273       else
 274         {
 275           // ASSERT(wr->next_on_way);
 276           while (wr = wr->next_on_way)
 277             {
 278               clist_remove(&wr->n);
 279               osm_way_add_node(nw, wr->node);
 280             }
 281         }
 282
 283       num_merged_segments++;
 284     }
 285
 286   // osm_obj_dump(&nw->o);
 287   simp_register_symbol(main_sym, wr1->zindex);
 288   // ((struct sym_line *) main_sym)->color = 0x0000ff;
 289 }
 290
 291 static void simp_merge_ways(void)
 292 {
 293   GARY_INIT_ALLOC(merge_wrefs, 0, &simp_pool->allocator);
 294
 295   HASH_FOR_ALL(simp_hash, s)
 296     {
 297       simp_merge_way(s);
 298     }
 299   HASH_END_FOR;
 300
 301   msg(L_INFO, "Simplify: Merged %u segments to %u new ways", num_merged_segments, num_merged_ways);
 302 }
 303
 304 /*** Splitting of ways ***/
 305
 306 static struct simp_way_ref **split_breakpoints;
 307 static uint num_split_ways, num_split_segments;
 308
 309 static void simp_split_way(struct simp_way_ref *wr)
 310 {
 311   GARY_RESIZE(split_breakpoints, 0);
 312   for (struct simp_way_ref *tr=wr; tr; tr=tr->next_on_way)
 313     if (tr->prev_on_way && tr->next_on_way)
 314       {
 315         struct simp_node *sn = tr->snode;
 316         struct simp_way_ref *x = clist_head(&sn->way_refs);
 317         if (x && clist_next(&sn->way_refs, &x->n))
 318           *GARY_PUSH(split_breakpoints) = tr;
 319       }
 320
 321   uint num_bp = GARY_SIZE(split_breakpoints);
 322   if (!num_bp)
 323     return;
 324
 325   DBG("Split: Want to split wr %p (%u times)", wr, num_bp);
 326   // ((struct sym_line *) wr->sym)->color = 0x0000ff;
 327   num_split_ways++;
 328
 329   uint bp = 0;
 330   struct symbol *orig_sym = wr->sym;
 331   struct symbol *sym = NULL;
 332   struct osm_way *w = NULL;
 333
 334   for (struct simp_way_ref *tr=wr; tr; tr=tr->next_on_way)
 335     {
 336       clist_remove(&tr->n);
 337       if (!sym)
 338         {
 339           w = osm_way_new(++simp_last_id);
 340           sym = sym_clone(orig_sym);
 341           sym->o = &w->o;
 342         }
 343       osm_way_add_node(w, tr->node);
 344       if (bp < num_bp && split_breakpoints[bp] == tr)
 345         {
 346           sym_plan(sym, wr->zindex);
 347           num_split_segments++;
 348           sym = NULL;
 349           w = NULL;
 350           bp++;
 351         }
 352     }
 353
 354   if (sym)
 355     {
 356       num_split_segments++;
 357       sym_plan(sym, wr->zindex);
 358       simp_register_symbol(sym, wr->zindex);
 359     }
 360
 361   sym_disable(orig_sym);
 362 }
 363
 364 static void simp_split_ways(void)
 365 {
 366   GARY_INIT_ALLOC(split_breakpoints, 0, &simp_pool->allocator);
 367
 368   HASH_FOR_ALL(simp_hash, s)
 369     {
 370       struct simp_way_ref *wr, *tmp;
 371       CLIST_WALK_DELSAFE(wr, s->way_refs, tmp)
 372         if (!wr->prev_on_way && wr->next_on_way)
 373           simp_split_way(wr);
 374     }
 375   HASH_END_FOR;
 376
 377   msg(L_INFO, "Simplify: Split %u ways to %u segments", num_split_ways, num_split_segments);
 378 }
 379
 380 /*** Generalization ***/
 381
 382 struct gen_context {
 383   struct osm_way *w;
 384   struct osm_ref **refs;
 385   uint in_nodes;
 386   uint out_nodes;
 387 };
 388
 389 static void generalize_recursively(struct gen_context *gc, int first, int last)
 390 {
 391   if (last - first <= 1)
 392     return;
 393
 394   double max_err = 0;
 395   struct osm_node *f = (struct osm_node *) gc->refs[first]->o, *l = (struct osm_node *) gc->refs[last]->o;
 396   double fx = f->x;
 397   double fy = f->y;
 398   double dx = l->x - fx;
 399   double dy = l->y - fy;
 400   double dd = dx*dx + dy*dy;
 401
 402   for (int i = first + 1; i < last; i++)
 403     {
 404       struct osm_node *n = (struct osm_node *) gc->refs[i]->o;
 405       double nx = n->x - f->x;
 406       double ny = n->y - f->y;
 407       double p = dx*nx + dy*ny;         // (px,py) = projection of (nx,ny) onto (dx,dy)
 408       double px = dx*p / dd;
 409       double py = dy*p / dd;
 410       double ex = px - nx;              // (ex,ey) is the error vector: (nx,ny) minus its projection
 411       double ey = py - ny;
 412       double e = ex*ex + ey*ey;
 413       max_err = MAX(max_err, e);
 414     }
 415
 416   double close = 1;
 417   if (max_err > close*close)
 418     {
 419       int mid = (first + last) / 2;
 420       ASSERT(first < mid && mid < last);
 421       generalize_recursively(gc, first, mid);
 422       clist_add_tail(&gc->w->nodes, &gc->refs[mid]->n);
 423       generalize_recursively(gc, mid, last);
 424     }
 425 }
 426
 427 static void simp_generalize_way(struct gen_context *gc, struct simp_way_ref *wr)
 428 {
 429   // XXX: This does not connect the way back to the simplification graph,
 430   // but it does not hurt since generalization is the last pass.
 431
 432   struct osm_way *w = wr->way;
 433   gc->w = w;
 434   GARY_RESIZE(gc->refs, 0);
 435
 436   CLIST_FOR_EACH(struct osm_ref *, r, w->nodes)
 437     *GARY_PUSH(gc->refs) = r;
 438
 439   int N = GARY_SIZE(gc->refs);
 440   if (N <= 2)
 441     return;
 442
 443   gc->in_nodes += N;
 444
 445 #if 0
 446   for (int i=0; i<N; i++)
 447     {
 448       struct osm_node *n = (struct osm_node *) gc->refs[i]->o;
 449       msg(L_DEBUG, "Generalize: @%d #%jd [%f,%f]", i, (intmax_t) n->o.id, n->x, n->y);
 450     }
 451 #endif
 452
 453   clist_init(&w->nodes);
 454   clist_add_tail(&w->nodes, &gc->refs[0]->n);
 455   generalize_recursively(gc, 0, N-1);
 456   clist_add_tail(&w->nodes, &gc->refs[N-1]->n);
 457
 458   CLIST_FOR_EACH(struct osm_ref *, r, w->nodes)
 459     gc->out_nodes++;
 460 }
 461
 462 static void simp_generalize_ways(void)
 463 {
 464   struct gen_context gc = { };
 465   GARY_INIT_ALLOC(gc.refs, 0, &simp_pool->allocator);
 466
 467   HASH_FOR_ALL(simp_hash, s)
 468     {
 469       struct simp_way_ref *wr, *tmp;
 470       CLIST_WALK_DELSAFE(wr, s->way_refs, tmp)
 471         if (!wr->prev_on_way && wr->next_on_way)
 472           simp_generalize_way(&gc, wr);
 473     }
 474   HASH_END_FOR;
 475
 476   msg(L_INFO, "Generalization: %u nodes in, %u nodes out", gc.in_nodes, gc.out_nodes);
 477 }
 478
 479 /*** Entry point ***/
 480
 481 void simplify(void)
 482 {
 483   msg(L_INFO, "Simplifying symbol topology");
 484   simp_pool = mp_new(65536);
 485   simp_osm = osm_init();
 486   simp_hash_init();
 487
 488   sym_for_all_planned(simp_register_symbol);
 489   simp_split_ways();
 490   simp_merge_ways();
 491   simp_generalize_ways();
 492
 493   mp_delete(simp_pool);
 494 }