* (c) 2022 Martin Mares <mj@ucw.cz>
*/
+// #define LOCAL_DEBUG
+// #pragma GCC optimize("-O0")
+
#include "leo.h"
#include <ucw/lib.h>
#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;
+ z_index_t zindex;
+ 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 {
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
#define HASH_TABLE_ALLOC
#include <ucw/hashtable.h>
-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);
+}
- ASSERT(num_nodes);
- if (num_nodes > 1)
+static void simp_register_symbol(struct symbol *sym, z_index_t zindex)
+{
+ struct osm_object *o = sym->o;
+
+ switch (o->type)
{
- msg(L_WARN, "Simplify: Multiple (%u) nodes at [%f, %f]", num_nodes, s->c.x, s->c.y);
- return false;
+ 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->zindex = zindex;
+ 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);
}
+}
- if (num_ways > 2)
- return false;
+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
+ {
+ while (wr->next_on_way)
+ wr = wr->next_on_way;
+ }
+ return wr;
+}
+
+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;
- return false;
+ 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 out_wr;
}
-static void simplify_source(struct data_source *ds)
+/*** Merging of ways ***/
+
+static struct simp_way_ref **merge_wrefs;
+static uint num_merged_ways, num_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;
- CLIST_FOR_EACH(struct osm_way *, w, osm_this->obj_list[OSM_TYPE_WAY])
+ 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 (;;)
{
- 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);
+ DBG("XXX: wr=%p or=%p cr=%p", wr, or, cr);
+ 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: Back stop at %p", cr);
+ break;
+ }
- struct simp_node_ref *nref = mp_alloc(simp_pool, sizeof(*nref));
- nref->to = n;
- clist_add_tail(&s->node_refs, &nref->n);
+ DBG("Merge: Back to %p", cr);
+ wr = cr;
- 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 == wr1)
+ {
+ DBG("Merge: Loop detected");
+ return;
}
- OSM_FOR_EACH_END;
}
+ // 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 (;;)
+ {
+ wr->merge_done = 1;
+ struct simp_way_ref *or = wref_other_end(wr);
+ struct simp_node *on = or->snode;
+
+ struct simp_way_ref *cr = wref_only_other(on, or);
+ if (!cr || !sym_same_attrs_p(or->sym, cr->sym))
+ {
+ 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");
+ num_merged_ways++;
+
+ struct osm_way *nw = osm_way_new(++simp_last_id);
+ struct symbol *main_sym = NULL;
+
+ 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);
+
+ if (wr->prev_on_way)
+ {
+ while (wr = wr->prev_on_way)
+ {
+ clist_remove(&wr->n);
+ osm_way_add_node(nw, wr->node);
+ }
+ }
+ else
+ {
+ // ASSERT(wr->next_on_way);
+ while (wr = wr->next_on_way)
+ {
+ clist_remove(&wr->n);
+ osm_way_add_node(nw, wr->node);
+ }
+ }
+
+ num_merged_segments++;
+ }
+
+ // osm_obj_dump(&nw->o);
+ simp_register_symbol(main_sym, wr1->zindex);
+ // ((struct sym_line *) main_sym)->color = 0x0000ff;
+}
+
+static void simp_merge_ways(void)
+{
+ GARY_INIT_ALLOC(merge_wrefs, 0, &simp_pool->allocator);
+
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", num_merged_segments, num_merged_ways);
}
+/*** Splitting of ways ***/
+
+static struct simp_way_ref **split_breakpoints;
+static uint num_split_ways, num_split_segments;
+
+static void simp_split_way(struct simp_way_ref *wr)
+{
+ GARY_RESIZE(split_breakpoints, 0);
+ for (struct simp_way_ref *tr=wr; tr; tr=tr->next_on_way)
+ if (tr->prev_on_way && tr->next_on_way)
+ {
+ struct simp_node *sn = tr->snode;
+ struct simp_way_ref *x = clist_head(&sn->way_refs);
+ if (x && clist_next(&sn->way_refs, &x->n))
+ *GARY_PUSH(split_breakpoints) = tr;
+ }
+
+ uint num_bp = GARY_SIZE(split_breakpoints);
+ if (!num_bp)
+ return;
+
+ DBG("Split: Want to split wr %p (%u times)", wr, num_bp);
+ // ((struct sym_line *) wr->sym)->color = 0x0000ff;
+ num_split_ways++;
+
+ uint bp = 0;
+ struct symbol *orig_sym = wr->sym;
+ struct symbol *sym = NULL;
+ struct osm_way *w = NULL;
+
+ for (struct simp_way_ref *tr=wr; tr; tr=tr->next_on_way)
+ {
+ clist_remove(&tr->n);
+ if (!sym)
+ {
+ w = osm_way_new(++simp_last_id);
+ sym = sym_clone(orig_sym);
+ sym->o = &w->o;
+ }
+ osm_way_add_node(w, tr->node);
+ if (bp < num_bp && split_breakpoints[bp] == tr)
+ {
+ sym_plan(sym, wr->zindex);
+ num_split_segments++;
+ sym = NULL;
+ w = NULL;
+ bp++;
+ }
+ }
+
+ if (sym)
+ {
+ num_split_segments++;
+ sym_plan(sym, wr->zindex);
+ simp_register_symbol(sym, wr->zindex);
+ }
+
+ sym_disable(orig_sym);
+}
+
+static void simp_split_ways(void)
+{
+ GARY_INIT_ALLOC(split_breakpoints, 0, &simp_pool->allocator);
+
+ HASH_FOR_ALL(simp_hash, s)
+ {
+ struct simp_way_ref *wr, *tmp;
+ CLIST_WALK_DELSAFE(wr, s->way_refs, tmp)
+ if (!wr->prev_on_way && wr->next_on_way)
+ simp_split_way(wr);
+ }
+ HASH_END_FOR;
+
+ msg(L_INFO, "Simplify: Split %u ways to %u segments", num_split_ways, num_split_segments);
+}
+
+/*** Generalization ***/
+
+struct gen_context {
+ struct osm_way *w;
+ struct osm_ref **refs;
+ uint in_nodes;
+ uint out_nodes;
+};
+
+static void generalize_recursively(struct gen_context *gc, int first, int last)
+{
+ if (last - first <= 1)
+ return;
+
+ double max_err = 0;
+ struct osm_node *f = (struct osm_node *) gc->refs[first]->o, *l = (struct osm_node *) gc->refs[last]->o;
+ double fx = f->x;
+ double fy = f->y;
+ double dx = l->x - fx;
+ double dy = l->y - fy;
+ double dd = dx*dx + dy*dy;
+
+ for (int i = first + 1; i < last; i++)
+ {
+ struct osm_node *n = (struct osm_node *) gc->refs[i]->o;
+ double nx = n->x - f->x;
+ double ny = n->y - f->y;
+ double p = dx*nx + dy*ny; // (px,py) = projection of (nx,ny) onto (dx,dy)
+ double px = dx*p / dd;
+ double py = dy*p / dd;
+ double ex = px - nx; // (ex,ey) is the error vector: (nx,ny) minus its projection
+ double ey = py - ny;
+ double e = ex*ex + ey*ey;
+ max_err = MAX(max_err, e);
+ }
+
+ double close = 1;
+ if (max_err > close*close)
+ {
+ int mid = (first + last) / 2;
+ ASSERT(first < mid && mid < last);
+ generalize_recursively(gc, first, mid);
+ clist_add_tail(&gc->w->nodes, &gc->refs[mid]->n);
+ generalize_recursively(gc, mid, last);
+ }
+}
+
+static void simp_generalize_way(struct gen_context *gc, struct simp_way_ref *wr)
+{
+ // XXX: This does not connect the way back to the simplification graph,
+ // but it does not hurt since generalization is the last pass.
+
+ struct osm_way *w = wr->way;
+ gc->w = w;
+ GARY_RESIZE(gc->refs, 0);
+
+ CLIST_FOR_EACH(struct osm_ref *, r, w->nodes)
+ *GARY_PUSH(gc->refs) = r;
+
+ int N = GARY_SIZE(gc->refs);
+ if (N <= 2)
+ return;
+
+ gc->in_nodes += N;
+
+#if 0
+ for (int i=0; i<N; i++)
+ {
+ struct osm_node *n = (struct osm_node *) gc->refs[i]->o;
+ msg(L_DEBUG, "Generalize: @%d #%jd [%f,%f]", i, (intmax_t) n->o.id, n->x, n->y);
+ }
+#endif
+
+ clist_init(&w->nodes);
+ clist_add_tail(&w->nodes, &gc->refs[0]->n);
+ generalize_recursively(gc, 0, N-1);
+ clist_add_tail(&w->nodes, &gc->refs[N-1]->n);
+
+ CLIST_FOR_EACH(struct osm_ref *, r, w->nodes)
+ gc->out_nodes++;
+}
+
+static void simp_generalize_ways(void)
+{
+ struct gen_context gc = { };
+ GARY_INIT_ALLOC(gc.refs, 0, &simp_pool->allocator);
+
+ HASH_FOR_ALL(simp_hash, s)
+ {
+ struct simp_way_ref *wr, *tmp;
+ CLIST_WALK_DELSAFE(wr, s->way_refs, tmp)
+ if (!wr->prev_on_way && wr->next_on_way)
+ simp_generalize_way(&gc, wr);
+ }
+ HASH_END_FOR;
+
+ msg(L_INFO, "Generalization: %u nodes in, %u nodes out", gc.in_nodes, gc.out_nodes);
+}
+
+/*** Entry point ***/
+
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();
+ simp_hash_init();
+
+ sym_for_all_planned(simp_register_symbol);
+ simp_split_ways();
+ simp_merge_ways();
+ simp_generalize_ways();
+
+ mp_delete(simp_pool);
}
projects / leo.git / blobdiff