simplify.c

   1 /*
   2  *      Hic Est Leo -- Map Simplification
   3  *
   4  *      (c) 2022 Martin Mares <mj@ucw.cz>
   5  */
   6
   7 // #pragma GCC optimize("-O0")
   8
   9 #include "leo.h"
  10
  11 #include <ucw/lib.h>
  12 #include <ucw/clists.h>
  13 #include <ucw/mempool.h>
  14
  15 #include <stdio.h>
  16 #include <math.h>
  17
  18 #include "osm.h"
  19 #include "map.h"
  20 #include "sym.h"
  21 #include "simplify.h"
  22
  23 static struct mempool *simp_pool;
  24 static struct osm *simp_osm;
  25 static osm_id_t simp_last_id;
  26
  27 struct coords {
  28   double x, y;
  29 };
  30
  31 struct simp_way_ref {
  32   cnode n;
  33   struct simp_node *snode;
  34   struct symbol *sym;
  35   struct osm_way *way;
  36   struct osm_node *node;
  37   struct simp_way_ref *prev_on_way;
  38   struct simp_way_ref *next_on_way;
  39   byte merge_done;
  40 };
  41
  42 struct simp_node {
  43   union {
  44     struct coords c;
  45     byte raw_coords[sizeof(struct coords)];
  46   };
  47   clist way_refs;
  48 };
  49
  50 static void simp_hash_init_data(struct simp_node *s)
  51 {
  52   clist_init(&s->way_refs);
  53 }
  54
  55 #define HASH_NODE struct simp_node
  56 #define HASH_PREFIX(x) simp_hash_##x
  57 #define HASH_KEY_MEMORY raw_coords
  58 #define HASH_KEY_SIZE sizeof(struct coords)
  59 #define HASH_WANT_LOOKUP
  60 #define HASH_GIVE_INIT_DATA
  61 #define HASH_USE_POOL simp_pool
  62 #define HASH_TABLE_ALLOC
  63 #include <ucw/hashtable.h>
  64
  65 static struct simp_node *simp_lookup_node(struct osm_node *n)
  66 {
  67   struct coords c = { .x = n->x, .y = n->y };
  68   return simp_hash_lookup((byte *) &c);
  69 }
  70
  71 static void simp_register_symbol(struct symbol *sym)
  72 {
  73   struct osm_object *o = sym->o;
  74
  75   switch (o->type)
  76     {
  77     case OSM_TYPE_NODE:
  78       simp_lookup_node((struct osm_node *) o);
  79       break;
  80     case OSM_TYPE_WAY:
  81       {
  82         struct osm_way *w = (struct osm_way *) o;
  83         struct simp_way_ref *wr_last = NULL;
  84         struct osm_node *prev_n = NULL;
  85
  86 #if 0
  87         for (uint i=0; i<2; i++)
  88           {
  89             struct osm_node *n = (struct osm_node *) (i ? osm_ref_head(&w->nodes) : osm_ref_tail(&w->nodes));
  90             struct sym_point *sp = sym_point_new(&n->o);
  91             sp->shape = VALUE_CIRCLE;
  92             sp->size = 1;
  93             sp->fill_color = 0x0000ff;
  94             sp->fill_opacity = 1;
  95             sp->do_fill = 1;
  96             sym_plan(sp, 100);
  97           }
  98 #endif
  99
 100         if (clist_size(&w->nodes) < 2)
 101           break;
 102
 103         OSM_FOR_EACH_BEGIN(struct osm_node *, n, w->nodes)
 104           {
 105             if (n == prev_n)
 106               continue;
 107
 108             struct simp_node *s = simp_lookup_node(n);
 109             struct simp_way_ref *wref = mp_alloc(simp_pool, sizeof(*wref));
 110             wref->snode = s;
 111             wref->sym = sym;
 112             wref->node = n;
 113             wref->way = w;
 114             wref->prev_on_way = wr_last;
 115             wref->next_on_way = NULL;
 116             if (wr_last)
 117               wr_last->next_on_way = wref;
 118             wr_last = wref;
 119             wref->merge_done = 0;
 120             clist_add_tail(&s->way_refs, &wref->n);
 121
 122             prev_n = n;
 123           }
 124         OSM_FOR_EACH_END;
 125         break;
 126       }
 127     default:
 128       die("Simplify: Unsupported symbol type %u", o->type);
 129     }
 130 }
 131
 132 static struct simp_way_ref *wref_other_end(struct simp_way_ref *wr)
 133 {
 134   if (wr->prev_on_way)
 135     {
 136       while (wr->prev_on_way)
 137         wr = wr->prev_on_way;
 138     }
 139   else
 140     {
 141       while (wr->next_on_way)
 142         wr = wr->next_on_way;
 143     }
 144   return wr;
 145 }
 146
 147 static struct simp_way_ref *wref_only_other(struct simp_node *sn, struct simp_way_ref *in_wr)
 148 {
 149   struct simp_way_ref *out_wr = NULL;
 150
 151   CLIST_FOR_EACH(struct simp_way_ref *, wr, sn->way_refs)
 152     {
 153       if (wr == in_wr)
 154         ;
 155       else if (!out_wr)
 156         out_wr = wr;
 157       else
 158         return NULL;
 159     }
 160
 161   return out_wr;
 162 }
 163
 164 static struct simp_way_ref **merge_wrefs;
 165 static uint simp_merged_ways, simp_merged_segments;
 166
 167 static void simp_merge_way(struct simp_node *s)
 168 {
 169   // XXX: This is grossly over-simplified. We assume that every way generates
 170   // at most one symbol, which is definitely not the case for ways rendered
 171   // with casing. But it should be sufficient for now.
 172
 173   uint nrefs = clist_size(&s->way_refs);
 174   if (nrefs != 2)
 175     return;
 176
 177   struct simp_way_ref *wr1, *wr2, *wr;
 178   wr1 = clist_head(&s->way_refs);
 179   wr2 = clist_tail(&s->way_refs);
 180   if (!(!wr1->prev_on_way != !wr1->next_on_way && !wr2->prev_on_way != !wr2->next_on_way))
 181     return;
 182   if (wr1->merge_done || wr2->merge_done)
 183     return;
 184
 185   wr = wr1;
 186   DBG("Merge: Starting with wr %p", wr);
 187
 188   for (;;)
 189     {
 190       wr->merge_done = 1;
 191       struct simp_way_ref *or = wref_other_end(wr);
 192       struct simp_node *on = or->snode;
 193
 194       struct simp_way_ref *cr = wref_only_other(on, or);
 195       DBG("XXX: wr=%p or=%p cr=%p", wr, or, cr);
 196       if (!cr || !sym_same_attrs_p(or->sym, cr->sym))
 197         {
 198           DBG("Merge: Back stop at %p", cr);
 199           break;
 200         }
 201
 202       DBG("Merge: Back to %p", cr);
 203       wr = cr;
 204
 205       if (wr == wr1)
 206         {
 207           DBG("Merge: Loop detected");
 208           return;
 209         }
 210     }
 211
 212   // Now, we are at the beginning/end of a single way
 213
 214   DBG("Merge: Back to %p", wr);
 215   wr = wref_other_end(wr);
 216   DBG("Merge: Other end is %p", wr);
 217   GARY_RESIZE(merge_wrefs, 0);
 218   *GARY_PUSH(merge_wrefs) = wr;
 219
 220   for (;;)
 221     {
 222       wr->merge_done = 1;
 223       struct simp_way_ref *or = wref_other_end(wr);
 224       struct simp_node *on = or->snode;
 225
 226       struct simp_way_ref *cr = wref_only_other(on, or);
 227       if (!cr || !sym_same_attrs_p(or->sym, cr->sym))
 228         {
 229           DBG("Merge: Fwd stop at %p", cr);
 230           break;
 231         }
 232
 233       DBG("Merge: Fwd to %p", cr);
 234       *GARY_PUSH(merge_wrefs) = cr;
 235       wr = cr;
 236     }
 237
 238   if (GARY_SIZE(merge_wrefs) < 2)
 239     return;
 240
 241   DBG("Will merge");
 242   simp_merged_ways++;
 243
 244   struct osm_way *nw = osm_way_new(++simp_last_id);
 245   struct symbol *main_sym = NULL;
 246
 247   for (uint i=0; i < GARY_SIZE(merge_wrefs); i++)
 248     {
 249       wr = merge_wrefs[i];
 250       clist_remove(&wr->n);
 251       if (!i)
 252         {
 253           osm_way_add_node(nw, wr->node);
 254           main_sym = wr->sym;
 255           main_sym->o = &nw->o;
 256         }
 257       else
 258         sym_disable(wr->sym);
 259
 260       if (wr->prev_on_way)
 261         {
 262           while (wr = wr->prev_on_way)
 263             {
 264               clist_remove(&wr->n);
 265               osm_way_add_node(nw, wr->node);
 266             }
 267         }
 268       else
 269         {
 270           // ASSERT(wr->next_on_way);
 271           while (wr = wr->next_on_way)
 272             {
 273               clist_remove(&wr->n);
 274               osm_way_add_node(nw, wr->node);
 275             }
 276         }
 277
 278       simp_merged_segments++;
 279     }
 280
 281   // osm_obj_dump(&nw->o);
 282   simp_register_symbol(main_sym);
 283   // ((struct sym_line *) main_sym)->color = 0x0000ff;
 284 }
 285
 286 static void simp_merge_ways(void)
 287 {
 288   HASH_FOR_ALL(simp_hash, s)
 289     {
 290       simp_merge_way(s);
 291     }
 292   HASH_END_FOR;
 293
 294   msg(L_INFO, "Simplify: Merged %u segments to %u new ways", simp_merged_segments, simp_merged_ways);
 295 }
 296
 297 void simplify(void)
 298 {
 299   msg(L_INFO, "Simplifying symbol topology");
 300   simp_pool = mp_new(65536);
 301   simp_osm = osm_init();
 302   GARY_INIT_ALLOC(merge_wrefs, 0, &simp_pool->allocator);
 303   simp_hash_init();
 304
 305   sym_for_all_planned(simp_register_symbol);
 306   simp_merge_ways();
 307
 308   mp_delete(simp_pool);
 309 }