Simplify: Generalization of line symbols

diff --git a/simplify.c b/simplify.c
index f5dc717edad92b0c4eecacd3e820428da2e62021..668d002e4fe9ee3954b36d9bb5f76d724d29e60a 100644 (file)
--- a/simplify.c
+++ b/simplify.c
@@ -290,6 +290,8 @@ static void simp_merge_way(struct simp_node *s)
 
 static void simp_merge_ways(void)
 {
+  GARY_INIT_ALLOC(merge_wrefs, 0, &simp_pool->allocator);
+
   HASH_FOR_ALL(simp_hash, s)
     {
       simp_merge_way(s);
@@ -361,6 +363,8 @@ static void simp_split_way(struct simp_way_ref *wr)
 
 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;
@@ -373,18 +377,118 @@ static void simp_split_ways(void)
   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 = 0.3;
+  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)
 {
   msg(L_INFO, "Simplifying symbol topology");
   simp_pool = mp_new(65536);
   simp_osm = osm_init();
-  GARY_INIT_ALLOC(merge_wrefs, 0, &simp_pool->allocator);
-  GARY_INIT_ALLOC(split_breakpoints, 0, &simp_pool->allocator);
   simp_hash_init();
 
   sym_for_all_planned(simp_register_symbol);
   simp_split_ways();
   simp_merge_ways();
+  simp_generalize_ways();
 
   mp_delete(simp_pool);
 }