[libshumate] vector: Smooth lines in symbol layer

[Marcus Lundblad <mlundblad src gnome org>]

commit 2986432e8fa474cd0788c0f3691f0e06d769c051
Author: James Westman <james jwestman net>
Date:   Sat May 14 21:48:56 2022 -0500

    vector: Smooth lines in symbol layer
    
    Smooth the lines used for glyph layout so that the labels are legible.

 demos/map-style.json                          | 14 +++++
 shumate/vector/shumate-vector-symbol-layer.c  | 25 ++++++++
 shumate/vector/shumate-vector-symbol.c        | 15 +++--
 shumate/vector/shumate-vector-utils-private.h |  1 +
 shumate/vector/shumate-vector-utils.c         | 87 ++++++++++++++++++++++++---
 5 files changed, 126 insertions(+), 16 deletions(-)
---
diff --git a/demos/map-style.json b/demos/map-style.json
index 2212534..3fed433 100644
--- a/demos/map-style.json
+++ b/demos/map-style.json
@@ -67,6 +67,20 @@
     },
     {
       "id": "waterway",
+      "type": "line",
+      "source-layer": "waterway",
+      "paint": {
+        "line-width": 0.5,
+        "line-color": {
+          "stops": [
+            [0, "#3584e4"],
+            [5, "#1a5fb4"]
+          ]
+        }
+      }
+    },
+    {
+      "id": "waterway_label",
       "type": "symbol",
       "source-layer": "waterway",
       "layout": {
diff --git a/shumate/vector/shumate-vector-symbol-layer.c b/shumate/vector/shumate-vector-symbol-layer.c
index 9ee597b..82a28d5 100644
--- a/shumate/vector/shumate-vector-symbol-layer.c
+++ b/shumate/vector/shumate-vector-symbol-layer.c
@@ -138,7 +138,32 @@ shumate_vector_symbol_layer_render (ShumateVectorLayer *layer, ShumateVectorRend
     {
       ShumateVectorLineString linestring;
       shumate_vector_render_scope_get_geometry (scope, &linestring);
+      shumate_vector_line_string_simplify (&linestring);
       shumate_vector_symbol_info_set_line_points (symbol_info, &linestring);
+
+#if 0
+      /* visualize line simplification */
+
+      line_points = shumate_vector_render_scope_get_geometry (scope, &num_points);
+      shumate_vector_line_simplify (line_points, &num_points);
+
+      if (num_points > 0)
+        {
+          float scale = scope->scale * scope->target_size;
+
+          cairo_set_source_rgb (scope->cr,
+                                rand () % 255 / 255.0,
+                                rand () % 255 / 255.0,
+                                rand () % 255 / 255.0);
+          cairo_set_line_width (scope->cr, scope->scale);
+
+          cairo_move_to (scope->cr, line_points[0].x * scale, line_points[0].y * scale);
+          for (gsize i = 1; i < num_points; i ++)
+            cairo_line_to (scope->cr, line_points[i].x * scale, line_points[i].y * scale);
+
+          cairo_stroke (scope->cr);
+        }
+#endif
     }
 
   g_ptr_array_add (scope->symbols, symbol_info);
diff --git a/shumate/vector/shumate-vector-symbol.c b/shumate/vector/shumate-vector-symbol.c
index 43c5251..3dccc6a 100644
--- a/shumate/vector/shumate-vector-symbol.c
+++ b/shumate/vector/shumate-vector-symbol.c
@@ -252,25 +252,28 @@ shumate_vector_symbol_snapshot (GtkWidget   *widget,
           Glyph *glyph = &((Glyph *)self->glyphs->data)[i];
           ShumateVectorPoint point;
 
-          shumate_vector_point_iter_get_current_point (&iter, &point);
-
           /* Whitespace has no glyph, but still has a width that needs to be
            * advanced in the point iter */
           if (glyph->node != NULL)
             {
+              float average_angle = shumate_vector_point_iter_get_average_angle (&iter, glyph->width / 
scale);
+              shumate_vector_point_iter_advance (&iter, glyph->width / scale / 2.0);
+              shumate_vector_point_iter_get_current_point (&iter, &point);
+              shumate_vector_point_iter_advance (&iter, glyph->width / scale / 2.0);
+
               gtk_snapshot_save (snapshot);
               gtk_snapshot_translate (snapshot,
                                       &GRAPHENE_POINT_INIT (
                                         (point.x - self->symbol_info->x) * scale,
                                         (point.y - self->symbol_info->y) * scale
                                       ));
-              gtk_snapshot_rotate (snapshot, shumate_vector_point_iter_get_current_angle (&iter) * 180 / 
G_PI);
-              gtk_snapshot_translate (snapshot, &GRAPHENE_POINT_INIT (0, self->symbol_info->text_size / 2));
+              gtk_snapshot_rotate (snapshot, average_angle * 180 / G_PI);
+              gtk_snapshot_translate (snapshot, &GRAPHENE_POINT_INIT (-glyph->width / 2.0, 
self->symbol_info->text_size / 2.0));
               gtk_snapshot_append_node (snapshot, glyph->node);
               gtk_snapshot_restore (snapshot);
             }
-
-          shumate_vector_point_iter_advance (&iter, glyph->width / scale);
+          else
+            shumate_vector_point_iter_advance (&iter, glyph->width / scale);
         }
 
       gtk_snapshot_restore (snapshot);
diff --git a/shumate/vector/shumate-vector-utils-private.h b/shumate/vector/shumate-vector-utils-private.h
index f424297..df26269 100644
--- a/shumate/vector/shumate-vector-utils-private.h
+++ b/shumate/vector/shumate-vector-utils-private.h
@@ -96,3 +96,4 @@ double shumate_vector_line_string_length              (ShumateVectorLineString *
 void   shumate_vector_line_string_bounds              (ShumateVectorLineString *linestring,
                                                        ShumateVectorPoint      *radius_out,
                                                        ShumateVectorPoint      *center_out);
+void   shumate_vector_line_string_simplify            (ShumateVectorLineString *linestring);
diff --git a/shumate/vector/shumate-vector-utils.c b/shumate/vector/shumate-vector-utils.c
index 976e5e7..f76e314 100644
--- a/shumate/vector/shumate-vector-utils.c
+++ b/shumate/vector/shumate-vector-utils.c
@@ -179,11 +179,19 @@ shumate_vector_point_iter_next_segment (ShumateVectorPointIter *iter)
 
 
 static double
-point_distance (ShumateVectorPoint *a, ShumateVectorPoint *b)
+point_distance_sq (ShumateVectorPoint *a,
+                   ShumateVectorPoint *b)
 {
   double x = a->x - b->x;
   double y = a->y - b->y;
-  return sqrt (x*x + y*y);
+  return x * x + y * y;
+}
+
+static double
+point_distance (ShumateVectorPoint *a,
+                ShumateVectorPoint *b)
+{
+  return sqrt (point_distance_sq (a, b));
 }
 
 static ShumateVectorPoint *
@@ -297,19 +305,16 @@ shumate_vector_point_iter_get_average_angle (ShumateVectorPointIter *iter,
                                              double                  remaining_distance)
 {
   ShumateVectorPointIter iter2 = *iter;
-  double orig = shumate_vector_point_iter_get_current_angle (iter);
-  double orig_distance = remaining_distance;
-  double sum = 0.0;
+  double sum_x = 0.0, sum_y = 0.0;
 
   while (remaining_distance > 0)
     {
-      float angle = shumate_vector_point_iter_get_current_angle (&iter2);
-      float d = MIN (remaining_distance, shumate_vector_point_iter_next_segment (&iter2));
-      sum += d * (angle - orig);
-      remaining_distance -= d;
+      sum_x += get_next_point (iter)->x - get_prev_point (iter)->x;
+      sum_y += get_next_point (iter)->y - get_prev_point (iter)->y;
+      remaining_distance -= shumate_vector_point_iter_next_segment (&iter2);
     }
 
-  return sum / orig_distance;
+  return atan2 (sum_y, sum_x);
 }
 
 
@@ -362,3 +367,65 @@ shumate_vector_line_string_bounds (ShumateVectorLineString *linestring,
   center_out->x = (max_x + min_x) / 2.0;
   center_out->y = (max_y + min_y) / 2.0;
 }
+
+
+void
+shumate_vector_line_string_simplify (ShumateVectorLineString *linestring)
+{
+  gint i;
+
+  if (linestring->n_points <= 2)
+    return;
+
+  /* The glyph layout algorithm for line symbols does not handle high detail
+   * very well. Lots of short segments with different angles cause it to place
+   * glyphs too close together and with "random" rotations, which makes text
+   * illegible.
+   *
+   * I tried several solutions. Simplification (such as the Visvalingam-Whyatt
+   * algorithm) creates too many sharp angles, which produces poor results.
+   * I also tried a smoothing algorithm which averages each point with its
+   * neighbors, and while that produced good results with natural lines like
+   * rivers, it deformed street labels that already looked fine, causing them
+   * not to line up with the street anymore.
+   *
+   * The following algorithm reduces detail only where it exists. It works by
+   * repeatedly merging the closest pair of neighboring points until no two
+   * points in the line are closer than a threshold.
+   * */
+
+  while (TRUE)
+    {
+      gint min_idx = -1;
+
+      /* Square the threshold because we compare it to the square of the
+       * distance (saving a sqrt() call). The unit is the size of a tile. */
+      float min_distance = 0.025 * 0.025;
+
+      /* Find the closest pair of points, excepting the first and last pair
+       * because we don't want to change the endpoints */
+      for (i = 1; i < linestring->n_points - 2; i ++)
+        {
+          float distance = point_distance_sq (&linestring->points[i], &linestring->points[i + 1]);
+          if (distance < min_distance)
+            {
+              min_idx = i;
+              min_distance = distance;
+            }
+        }
+
+      if (min_idx == -1 || linestring->n_points <= 2)
+        break;
+
+      /* Set the first point in the pair to the average of the two */
+      linestring->points[min_idx] = (ShumateVectorPoint) {
+        (linestring->points[min_idx].x + linestring->points[min_idx + 1].x) / 2.0,
+        (linestring->points[min_idx].y + linestring->points[min_idx + 1].y) / 2.0,
+      };
+
+      /* Remove the second point by shifting everything after it */
+      linestring->n_points --;
+      for (i = min_idx + 1; i < linestring->n_points; i ++)
+        linestring->points[i] = linestring->points[i + 1];
+    }
+}