From 47990015b7a740a6b4f0f6627d740de22844eeea Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sun, 27 Mar 2022 22:25:38 +0200 Subject: [PATCH] Simplify: Merging of ways --- leo.c | 2 +- simplify.c | 273 ++++++++++++++++++++++++++++++++++++++++++++--------- 2 files changed, 230 insertions(+), 45 deletions(-) diff --git a/leo.c b/leo.c index b62d21b..e957ec8 100644 --- a/leo.c +++ b/leo.c @@ -124,7 +124,6 @@ int main(int argc UNUSED, char **argv) styles_init(); map_load_styles(); map_load_sources(); - simplify(); graph_build(); map_set_scale(); map_generalize(); @@ -144,6 +143,7 @@ int main(int argc UNUSED, char **argv) sym_init(); map_apply_styles(svg); + simplify(); if (map_clip) { diff --git a/simplify.c b/simplify.c index a621027..7c69cf3 100644 --- a/simplify.c +++ b/simplify.c @@ -4,6 +4,8 @@ * (c) 2022 Martin Mares */ +// #pragma GCC optimize("-O0") + #include "leo.h" #include @@ -15,23 +17,26 @@ #include "osm.h" #include "map.h" +#include "sym.h" #include "simplify.h" static struct mempool *simp_pool; +static struct osm *simp_osm; +static osm_id_t simp_last_id; struct coords { double x, y; }; -struct simp_node_ref { - cnode n; - struct osm_node *to; -}; - struct simp_way_ref { cnode n; - struct osm_way *to; - bool is_end; + struct simp_node *snode; + struct symbol *sym; + struct osm_way *way; + struct osm_node *node; + struct simp_way_ref *prev_on_way; + struct simp_way_ref *next_on_way; + byte merge_done; }; struct simp_node { @@ -39,16 +44,12 @@ struct simp_node { struct coords c; byte raw_coords[sizeof(struct coords)]; }; - clist node_refs; clist way_refs; - byte can_be_merged; }; static void simp_hash_init_data(struct simp_node *s) { - clist_init(&s->node_refs); clist_init(&s->way_refs); - s->can_be_merged = false; } #define HASH_NODE struct simp_node @@ -61,64 +62,248 @@ static void simp_hash_init_data(struct simp_node *s) #define HASH_TABLE_ALLOC #include -static bool simp_can_be_merged(struct simp_node *s) +static struct simp_node *simp_lookup_node(struct osm_node *n) { - uint num_nodes = clist_size(&s->node_refs); - uint num_ways = clist_size(&s->way_refs); + struct coords c = { .x = n->x, .y = n->y }; + return simp_hash_lookup((byte *) &c); +} + +static void simp_register_symbol(struct symbol *sym) +{ + struct osm_object *o = sym->o; + + switch (o->type) + { + case OSM_TYPE_NODE: + simp_lookup_node((struct osm_node *) o); + break; + case OSM_TYPE_WAY: + { + struct osm_way *w = (struct osm_way *) o; + struct simp_way_ref *wr_last = NULL; + struct osm_node *prev_n = NULL; + +#if 0 + for (uint i=0; i<2; i++) + { + struct osm_node *n = (struct osm_node *) (i ? osm_ref_head(&w->nodes) : osm_ref_tail(&w->nodes)); + struct sym_point *sp = sym_point_new(&n->o); + sp->shape = VALUE_CIRCLE; + sp->size = 1; + sp->fill_color = 0x0000ff; + sp->fill_opacity = 1; + sp->do_fill = 1; + sym_plan(sp, 100); + } +#endif + + if (clist_size(&w->nodes) < 2) + break; + + OSM_FOR_EACH_BEGIN(struct osm_node *, n, w->nodes) + { + if (n == prev_n) + continue; + + struct simp_node *s = simp_lookup_node(n); + struct simp_way_ref *wref = mp_alloc(simp_pool, sizeof(*wref)); + wref->snode = s; + wref->sym = sym; + wref->node = n; + wref->way = w; + wref->prev_on_way = wr_last; + wref->next_on_way = NULL; + if (wr_last) + wr_last->next_on_way = wref; + wr_last = wref; + wref->merge_done = 0; + clist_add_tail(&s->way_refs, &wref->n); + + prev_n = n; + } + OSM_FOR_EACH_END; + break; + } + default: + die("Simplify: Unsupported symbol type %u", o->type); + } +} - ASSERT(num_nodes); - if (num_nodes > 1) +static struct simp_way_ref *wref_other_end(struct simp_way_ref *wr) +{ + if (wr->prev_on_way) + { + while (wr->prev_on_way) + wr = wr->prev_on_way; + } + else { - msg(L_WARN, "Simplify: Multiple (%u) nodes at [%f, %f]", num_nodes, s->c.x, s->c.y); - return false; + while (wr->next_on_way) + wr = wr->next_on_way; } + return wr; +} - if (num_ways > 2) - return false; +static struct simp_way_ref *wref_only_other(struct simp_node *sn, struct simp_way_ref *in_wr) +{ + struct simp_way_ref *out_wr = NULL; + + CLIST_FOR_EACH(struct simp_way_ref *, wr, sn->way_refs) + { + if (wr == in_wr) + ; + else if (!out_wr) + out_wr = wr; + else + return NULL; + } - return false; + return out_wr; } -static void simplify_source(struct data_source *ds) +static struct simp_way_ref **merge_wrefs; +static uint simp_merged_ways, simp_merged_segments; + +static void simp_merge_way(struct simp_node *s) { - msg(L_INFO, "Simplifying source %s", ds->file); - simp_pool = mp_new(65536); - simp_hash_init(); - osm_this = ds->osm; + // XXX: This is grossly over-simplified. We assume that every way generates + // at most one symbol, which is definitely not the case for ways rendered + // with casing. But it should be sufficient for now. + + uint nrefs = clist_size(&s->way_refs); + if (nrefs != 2) + return; + + struct simp_way_ref *wr1, *wr2, *wr; + wr1 = clist_head(&s->way_refs); + wr2 = clist_tail(&s->way_refs); + if (!(!wr1->prev_on_way != !wr1->next_on_way && !wr2->prev_on_way != !wr2->next_on_way)) + return; + if (wr1->merge_done || wr2->merge_done) + return; + + wr = wr1; + DBG("Merge: Starting with wr %p", wr); + + for (;;) + { + wr->merge_done = 1; + struct simp_way_ref *or = wref_other_end(wr); + struct simp_node *on = or->snode; - CLIST_FOR_EACH(struct osm_way *, w, osm_this->obj_list[OSM_TYPE_WAY]) + struct simp_way_ref *cr = wref_only_other(on, or); + DBG("XXX: wr=%p or=%p cr=%p", wr, or, cr); + if (!cr || !sym_same_attrs_p(or->sym, cr->sym)) + { + DBG("Merge: Back stop at %p", cr); + break; + } + + DBG("Merge: Back to %p", cr); + wr = cr; + + if (wr == wr1) + { + DBG("Merge: Loop detected"); + return; + } + } + + // Now, we are at the beginning/end of a single way + + DBG("Merge: Back to %p", wr); + wr = wref_other_end(wr); + DBG("Merge: Other end is %p", wr); + GARY_RESIZE(merge_wrefs, 0); + *GARY_PUSH(merge_wrefs) = wr; + + for (;;) { - struct osm_node *n_first = (struct osm_node *) osm_ref_head(&w->nodes); - struct osm_node *n_last = (struct osm_node *) osm_ref_tail(&w->nodes); + wr->merge_done = 1; + struct simp_way_ref *or = wref_other_end(wr); + struct simp_node *on = or->snode; - OSM_FOR_EACH_BEGIN(struct osm_node *, n, w->nodes) + struct simp_way_ref *cr = wref_only_other(on, or); + if (!cr || !sym_same_attrs_p(or->sym, cr->sym)) { - struct coords c = { .x = n->x, .y = n->y }; - struct simp_node *s = simp_hash_lookup((byte *) &c); + DBG("Merge: Fwd stop at %p", cr); + break; + } + + DBG("Merge: Fwd to %p", cr); + *GARY_PUSH(merge_wrefs) = cr; + wr = cr; + } + + if (GARY_SIZE(merge_wrefs) < 2) + return; + + DBG("Will merge"); + simp_merged_ways++; + + struct osm_way *nw = osm_way_new(++simp_last_id); + struct symbol *main_sym = NULL; - struct simp_node_ref *nref = mp_alloc(simp_pool, sizeof(*nref)); - nref->to = n; - clist_add_tail(&s->node_refs, &nref->n); + for (uint i=0; i < GARY_SIZE(merge_wrefs); i++) + { + wr = merge_wrefs[i]; + clist_remove(&wr->n); + if (!i) + { + osm_way_add_node(nw, wr->node); + main_sym = wr->sym; + main_sym->o = &nw->o; + } + else + sym_disable(wr->sym); - struct simp_way_ref *wref = mp_alloc(simp_pool, sizeof(*wref)); - wref->to = w; - wref->is_end = (n == n_first || n == n_last); - clist_add_tail(&s->way_refs, &wref->n); + if (wr->prev_on_way) + { + while (wr = wr->prev_on_way) + { + clist_remove(&wr->n); + osm_way_add_node(nw, wr->node); + } } - OSM_FOR_EACH_END; + else + { + // ASSERT(wr->next_on_way); + while (wr = wr->next_on_way) + { + clist_remove(&wr->n); + osm_way_add_node(nw, wr->node); + } + } + + simp_merged_segments++; } + // osm_obj_dump(&nw->o); + simp_register_symbol(main_sym); + // ((struct sym_line *) main_sym)->color = 0x0000ff; +} + +static void simp_merge_ways(void) +{ HASH_FOR_ALL(simp_hash, s) { - s->can_be_merged = simp_can_be_merged(s); + simp_merge_way(s); } HASH_END_FOR; - mp_delete(simp_pool); + msg(L_INFO, "Simplify: Merged %u segments to %u new ways", simp_merged_segments, simp_merged_ways); } void simplify(void) { - CLIST_FOR_EACH(struct data_source *, ds, map_sources) - simplify_source(ds); + msg(L_INFO, "Simplifying symbol topology"); + simp_pool = mp_new(65536); + simp_osm = osm_init(); + GARY_INIT_ALLOC(merge_wrefs, 0, &simp_pool->allocator); + simp_hash_init(); + + sym_for_all_planned(simp_register_symbol); + simp_merge_ways(); + + mp_delete(simp_pool); } -- 2.39.2