]> mj.ucw.cz Git - leo.git/blob - simplify.c
Simplify: Splitting of ways to non-branching segments
[leo.git] / 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 }