From 0850473d2dc324e35bcaabf246a865cf70b10da1 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Sun, 27 Mar 2022 23:03:03 +0200
Subject: [PATCH] Simplify: Splitting of ways to non-branching segments

This is to make the segments mergeable.
---
 leo.c      |  2 +-
 simplify.c | 93 ++++++++++++++++++++++++++++++++++++++++++++++++++----
 2 files changed, 88 insertions(+), 7 deletions(-)

diff --git a/leo.c b/leo.c
index e957ec8..d7a39bd 100644
--- a/leo.c
+++ b/leo.c
@@ -126,7 +126,7 @@ int main(int argc UNUSED, char **argv)
   map_load_sources();
   graph_build();
   map_set_scale();
-  map_generalize();
+  // map_generalize();
 
   struct svg *svg = svg_open(map_svg_output);
   if (!map_rotate)
diff --git a/simplify.c b/simplify.c
index 7c69cf3..f5dc717 100644
--- a/simplify.c
+++ b/simplify.c
@@ -4,6 +4,7 @@
  *	(c) 2022 Martin Mares <mj@ucw.cz>
  */
 
+// #define LOCAL_DEBUG
 // #pragma GCC optimize("-O0")
 
 #include "leo.h"
@@ -32,6 +33,7 @@ struct simp_way_ref {
   cnode n;
   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;
@@ -68,7 +70,7 @@ static struct simp_node *simp_lookup_node(struct osm_node *n)
   return simp_hash_lookup((byte *) &c);
 }
 
-static void simp_register_symbol(struct symbol *sym)
+static void simp_register_symbol(struct symbol *sym, z_index_t zindex)
 {
   struct osm_object *o = sym->o;
 
@@ -109,6 +111,7 @@ static void simp_register_symbol(struct symbol *sym)
 	    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;
@@ -161,8 +164,10 @@ static struct simp_way_ref *wref_only_other(struct simp_node *sn, struct simp_wa
   return out_wr;
 }
 
+/*** Merging of ways ***/
+
 static struct simp_way_ref **merge_wrefs;
-static uint simp_merged_ways, simp_merged_segments;
+static uint num_merged_ways, num_merged_segments;
 
 static void simp_merge_way(struct simp_node *s)
 {
@@ -239,7 +244,7 @@ static void simp_merge_way(struct simp_node *s)
     return;
 
   DBG("Will merge");
-  simp_merged_ways++;
+  num_merged_ways++;
 
   struct osm_way *nw = osm_way_new(++simp_last_id);
   struct symbol *main_sym = NULL;
@@ -275,11 +280,11 @@ static void simp_merge_way(struct simp_node *s)
 	    }
 	}
 
-      simp_merged_segments++;
+      num_merged_segments++;
     }
 
   // osm_obj_dump(&nw->o);
-  simp_register_symbol(main_sym);
+  simp_register_symbol(main_sym, wr1->zindex);
   // ((struct sym_line *) main_sym)->color = 0x0000ff;
 }
 
@@ -291,7 +296,81 @@ static void simp_merge_ways(void)
     }
   HASH_END_FOR;
 
-  msg(L_INFO, "Simplify: Merged %u segments to %u new ways", simp_merged_segments, simp_merged_ways);
+  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)
+{
+  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);
 }
 
 void simplify(void)
@@ -300,9 +379,11 @@ void simplify(void)
   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();
 
   mp_delete(simp_pool);
-- 
2.39.2