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   HASH_FOR_ALL(simp_hash, s)
 294     {
 295       simp_merge_way(s);
 296     }
 297   HASH_END_FOR;
 298
 299   msg(L_INFO, "Simplify: Merged %u segments to %u new ways", num_merged_segments, num_merged_ways);
 300 }
 301
 302 /*** Splitting of ways ***/
 303
 304 static struct simp_way_ref **split_breakpoints;
 305 static uint num_split_ways, num_split_segments;
 306
 307 static void simp_split_way(struct simp_way_ref *wr)
 308 {
 309   GARY_RESIZE(split_breakpoints, 0);
 310   for (struct simp_way_ref *tr=wr; tr; tr=tr->next_on_way)
 311     if (tr->prev_on_way && tr->next_on_way)
 312       {
 313         struct simp_node *sn = tr->snode;
 314         struct simp_way_ref *x = clist_head(&sn->way_refs);
 315         if (x && clist_next(&sn->way_refs, &x->n))
 316           *GARY_PUSH(split_breakpoints) = tr;
 317       }
 318
 319   uint num_bp = GARY_SIZE(split_breakpoints);
 320   if (!num_bp)
 321     return;
 322
 323   DBG("Split: Want to split wr %p (%u times)", wr, num_bp);
 324   // ((struct sym_line *) wr->sym)->color = 0x0000ff;
 325   num_split_ways++;
 326
 327   uint bp = 0;
 328   struct symbol *orig_sym = wr->sym;
 329   struct symbol *sym = NULL;
 330   struct osm_way *w = NULL;
 331
 332   for (struct simp_way_ref *tr=wr; tr; tr=tr->next_on_way)
 333     {
 334       clist_remove(&tr->n);
 335       if (!sym)
 336         {
 337           w = osm_way_new(++simp_last_id);
 338           sym = sym_clone(orig_sym);
 339           sym->o = &w->o;
 340         }
 341       osm_way_add_node(w, tr->node);
 342       if (bp < num_bp && split_breakpoints[bp] == tr)
 343         {
 344           sym_plan(sym, wr->zindex);
 345           num_split_segments++;
 346           sym = NULL;
 347           w = NULL;
 348           bp++;
 349         }
 350     }
 351
 352   if (sym)
 353     {
 354       num_split_segments++;
 355       sym_plan(sym, wr->zindex);
 356       simp_register_symbol(sym, wr->zindex);
 357     }
 358
 359   sym_disable(orig_sym);
 360 }
 361
 362 static void simp_split_ways(void)
 363 {
 364   HASH_FOR_ALL(simp_hash, s)
 365     {
 366       struct simp_way_ref *wr, *tmp;
 367       CLIST_WALK_DELSAFE(wr, s->way_refs, tmp)
 368         if (!wr->prev_on_way && wr->next_on_way)
 369           simp_split_way(wr);
 370     }
 371   HASH_END_FOR;
 372
 373   msg(L_INFO, "Simplify: Split %u ways to %u segments", num_split_ways, num_split_segments);
 374 }
 375
 376 void simplify(void)
 377 {
 378   msg(L_INFO, "Simplifying symbol topology");
 379   simp_pool = mp_new(65536);
 380   simp_osm = osm_init();
 381   GARY_INIT_ALLOC(merge_wrefs, 0, &simp_pool->allocator);
 382   GARY_INIT_ALLOC(split_breakpoints, 0, &simp_pool->allocator);
 383   simp_hash_init();
 384
 385   sym_for_all_planned(simp_register_symbol);
 386   simp_split_ways();
 387   simp_merge_ways();
 388
 389   mp_delete(simp_pool);
 390 }