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