[gtk/path-work-rebased: 25/121] path: Add gsk_path_measure_get_closest_point()




commit 614e043c94d1b8a8805e8084235cdc8001d9687a
Author: Benjamin Otte <otte redhat com>
Date:   Wed Nov 25 02:21:41 2020 +0100

    path: Add gsk_path_measure_get_closest_point()
    
    ... and gsk_path_measure_get_closest_point_full().
    
    Those 2 functions allow finding the closest point on a path to a given
    point.

 gsk/gskpath.c        | 316 +++++++++++++++++++++++++++++++++++++++++++++++++++
 gsk/gskpathmeasure.c | 118 ++++++++++++++++++-
 gsk/gskpathmeasure.h |  12 ++
 gsk/gskpathprivate.h |  10 ++
 4 files changed, 455 insertions(+), 1 deletion(-)
---
diff --git a/gsk/gskpath.c b/gsk/gskpath.c
index 900b414bef..d87e967af6 100644
--- a/gsk/gskpath.c
+++ b/gsk/gskpath.c
@@ -63,6 +63,15 @@ struct _GskContourClass
                                                  float                   distance,
                                                  graphene_point_t       *pos,
                                                  graphene_vec2_t        *tangent);
+  gboolean              (* get_closest_point)   (const GskContour       *contour,
+                                                 gpointer                measure_data,
+                                                 float                   tolerance,
+                                                 const graphene_point_t *point,
+                                                 float                   threshold,
+                                                 float                  *out_offset,
+                                                 graphene_point_t       *out_pos,
+                                                 float                  *out_distance,
+                                                 graphene_vec2_t        *out_tangent);
   void                  (* copy)                (const GskContour       *contour,
                                                  GskContour             *dest);
   void                  (* add_segment)         (const GskContour       *contour,
@@ -112,6 +121,39 @@ static GskContour *
 gsk_path_builder_add_contour_by_klass (GskPathBuilder        *builder,
                                        const GskContourClass *klass);
 
+static void
+gsk_find_point_on_line (const graphene_point_t *a,
+                        const graphene_point_t *b,
+                        const graphene_point_t *p,
+                        float                  *offset,
+                        graphene_point_t       *pos)
+{
+  graphene_vec2_t n;
+  graphene_vec2_t ap;
+  float t;
+
+  graphene_vec2_init (&n, b->x - a->x, b->y - a->y);
+  graphene_vec2_init (&ap, p->x - a->x, p->y - a->y);
+
+  t = graphene_vec2_dot (&ap, &n) / graphene_vec2_dot (&n, &n);
+
+  if (t <= 0)
+    {
+      *pos = *a;
+      *offset = 0;
+    }
+  else if (t >= 1)
+    {
+      *pos = *b;
+      *offset = 1;
+    }
+  else
+    {
+      graphene_point_interpolate (a, b, t, pos);
+      *offset = t;
+    }
+}
+
 /* RECT CONTOUR */
 
 typedef struct _GskRectContour GskRectContour;
@@ -264,6 +306,95 @@ gsk_rect_contour_get_point (const GskContour *contour,
     graphene_vec2_init (tangent, 0.0f, - copysignf (self->height, 1.0f));
 }
 
+static gboolean
+gsk_rect_contour_get_closest_point (const GskContour       *contour,
+                                    gpointer                measure_data,
+                                    float                   tolerance,
+                                    const graphene_point_t *point,
+                                    float                   threshold,
+                                    float                  *out_distance,
+                                    graphene_point_t       *out_pos,
+                                    float                  *out_offset,
+                                    graphene_vec2_t        *out_tangent)
+{
+  const GskRectContour *self = (const GskRectContour *) contour;
+  graphene_point_t t, p;
+  float distance;
+ 
+  /* offset coords to be relative to rectangle */
+  t.x = point->x - self->x;
+  t.y = point->y - self->y;
+
+  if (self->width)
+    {
+      /* do unit square math */
+      t.x /= self->width;
+      /* move point onto the square */
+      t.x = CLAMP (t.x, 0.f, 1.f);
+    }
+  else
+    t.x = 0.f;
+
+  if (self->height)
+    {
+      t.y /= self->height;
+      t.y = CLAMP (t.y, 0.f, 1.f);
+    }
+  else
+    t.y = 0.f;
+
+  if (t.x > 0 && t.x < 1 && t.y > 0 && t.y < 1)
+    {
+      float diff = MIN (t.x, 1.f - t.x) * ABS (self->width) - MIN (t.y, 1.f - t.y) * ABS (self->height);
+
+      if (diff < 0.f)
+        t.x = ceilf (t.x - 0.5f); /* round 0.5 down */
+      else if (diff > 0.f)
+        t.y = roundf (t.y); /* round 0.5 up */
+      else
+        {
+          /* at least 2 points match, return the first one in the stroke */
+          if (t.y <= 1.f - t.y)
+            t.y = 0.f;
+          else if (1.f - t.x <= t.x)
+            t.x = 1.f;
+          else
+            t.y = 1.f;
+        }
+    }
+
+  p = GRAPHENE_POINT_INIT (self->x + t.x * self->width,
+                           self->y + t.y * self->height);
+
+  distance = graphene_point_distance (point, &p, NULL, NULL);
+  if (distance > threshold)
+    return FALSE;
+
+  if (out_distance)
+    *out_distance = distance;
+
+  if (out_pos)
+    *out_pos = p;
+
+  if (out_offset)
+    *out_offset = (t.x == 0.0 && self->width > 0 ? 2 - t.y : t.y) * ABS (self->height) + 
+                  (t.y == 1.0 ? 2 - t.x : t.x) * ABS (self->width);
+
+  if (out_tangent)
+    {
+      if (t.y == 0 && t.x < 1)
+        graphene_vec2_init (out_tangent, copysignf(1.0, self->width), 0);
+      else if (t.x == 0)
+        graphene_vec2_init (out_tangent, 0, - copysignf(1.0, self->height));
+      else if (t.y == 1)
+        graphene_vec2_init (out_tangent, - copysignf(1.0, self->width), 0);
+      else if (t.x == 1)
+        graphene_vec2_init (out_tangent, 0, copysignf(1.0, self->height));
+    }
+
+  return TRUE;
+}
+
 static void
 gsk_rect_contour_copy (const GskContour *contour,
                        GskContour       *dest)
@@ -351,6 +482,7 @@ static const GskContourClass GSK_RECT_CONTOUR_CLASS =
   gsk_rect_contour_init_measure,
   gsk_rect_contour_free_measure,
   gsk_rect_contour_get_point,
+  gsk_rect_contour_get_closest_point,
   gsk_rect_contour_copy,
   gsk_rect_contour_add_segment
 };
@@ -374,6 +506,7 @@ gsk_rect_contour_init (GskContour *contour,
 /* CIRCLE CONTOUR */
 
 #define DEG_TO_RAD(x)          ((x) * (G_PI / 180.f))
+#define RAD_TO_DEG(x)          ((x) / (G_PI / 180.f))
 
 typedef struct _GskCircleContour GskCircleContour;
 struct _GskCircleContour
@@ -528,6 +661,72 @@ gsk_circle_contour_get_point (const GskContour *contour,
     }
 }
 
+static gboolean
+gsk_circle_contour_get_closest_point (const GskContour       *contour,
+                                      gpointer                measure_data,
+                                      float                   tolerance,
+                                      const graphene_point_t *point,
+                                      float                   threshold,
+                                      float                  *out_distance,
+                                      graphene_point_t       *out_pos,
+                                      float                  *out_offset,
+                                      graphene_vec2_t        *out_tangent)
+{
+  const GskCircleContour *self = (const GskCircleContour *) contour;
+  float angle;
+  float closest_angle;
+  float offset;
+  graphene_point_t pos;
+  graphene_vec2_t tangent;
+  float distance;
+
+  if (graphene_point_distance (point, &self->center, NULL, NULL) > threshold + self->radius)
+    return FALSE;
+
+  angle = atan2f (point->y - self->center.y, point->x - self->center.x);
+  angle = RAD_TO_DEG (angle);
+  if (angle < 0)
+    angle += 360;
+
+  if ((self->start_angle <= angle && angle <= self->end_angle) ||
+      (self->end_angle <= angle && angle <= self->start_angle))
+    {
+      closest_angle = angle;
+    }
+  else
+    {
+      float d1, d2;
+
+      d1 = fabs (self->start_angle - angle);
+      d1 = MIN (d1, 360 - d1);
+      d2 = fabs (self->end_angle - angle);
+      d2 = MIN (d2, 360 - d2);
+      if (d1 < d2)
+        closest_angle = self->start_angle;
+      else
+        closest_angle = self->end_angle;
+    }
+
+  offset = self->radius * 2 * M_PI * (closest_angle - self->start_angle) / (self->end_angle - 
self->start_angle);
+
+  gsk_circle_contour_get_point (contour, NULL, offset, &pos, out_tangent ? &tangent : NULL);
+
+  distance = graphene_point_distance (&pos, point, NULL, NULL);
+  if (threshold < distance)
+    return FALSE;
+
+  if (out_offset)
+    *out_offset = offset;
+  if (out_pos)
+    *out_pos = pos;
+  if (out_distance)
+    *out_distance = distance;
+  if (out_tangent)
+    *out_tangent = tangent;
+
+  return TRUE;
+}
+
 static void
 gsk_circle_contour_copy (const GskContour *contour,
                          GskContour       *dest)
@@ -577,6 +776,7 @@ static const GskContourClass GSK_CIRCLE_CONTOUR_CLASS =
   gsk_circle_contour_init_measure,
   gsk_circle_contour_free_measure,
   gsk_circle_contour_get_point,
+  gsk_circle_contour_get_closest_point,
   gsk_circle_contour_copy,
   gsk_circle_contour_add_segment
 };
@@ -945,6 +1145,96 @@ gsk_standard_contour_get_point (const GskContour *contour,
   gsk_standard_contour_measure_get_point (self, measure->op, progress, pos, tangent);
 }
 
+static gboolean
+gsk_standard_contour_get_closest_point (const GskContour       *contour,
+                                        gpointer                measure_data,
+                                        float                   tolerance,
+                                        const graphene_point_t *point,
+                                        float                   threshold,
+                                        float                  *out_distance,
+                                        graphene_point_t       *out_pos,
+                                        float                  *out_offset,
+                                        graphene_vec2_t        *out_tangent)
+{
+  GskStandardContour *self = (GskStandardContour *) contour;
+  GskStandardContourMeasure *measure;
+  float progress, dist;
+  GArray *array = measure_data;
+  graphene_point_t p, last_point;
+  gsize i;
+  gboolean result = FALSE;
+
+  g_assert (self->ops[0].op == GSK_PATH_MOVE);
+  last_point = self->points[0];
+
+  if (array->len == 0)
+    {
+      /* This is the special case for point-only */
+      dist = graphene_point_distance (&last_point, point, NULL, NULL);
+
+      if (dist > threshold)
+        return FALSE;
+
+      if (out_offset)
+        *out_offset = 0;
+
+      if (out_distance)
+        *out_distance = dist;
+
+      if (out_pos)
+        *out_pos = last_point;
+
+      if (out_tangent)
+        *out_tangent = *graphene_vec2_x_axis ();
+
+      return TRUE;
+    }
+
+  for (i = 0; i < array->len; i++)
+    {
+      measure = &g_array_index (array, GskStandardContourMeasure, i);
+
+      gsk_find_point_on_line (&last_point,
+                              &measure->end_point,
+                              point,
+                              &progress,
+                              &p);
+      last_point = measure->end_point;
+      dist = graphene_point_distance (point, &p, NULL, NULL);
+      /* add some wiggleroom for the accurate check below */
+      //g_print ("%zu: (%g-%g) dist %g\n", i, measure->start, measure->end, dist);
+      if (dist <= threshold + 1.0f)
+        {
+          graphene_vec2_t t;
+          float found_progress;
+
+          found_progress = measure->start_progress + (measure->end_progress - measure->start_progress) * 
progress;
+
+          gsk_standard_contour_measure_get_point (self, measure->op, found_progress, &p, out_tangent ? &t : 
NULL);
+          dist = graphene_point_distance (point, &p, NULL, NULL);
+          /* double check that the point actually is closer */ 
+          //g_print ("!!! %zu: (%g-%g) dist %g\n", i, measure->start, measure->end, dist);
+          if (dist <= threshold)
+            {
+              if (out_distance)
+                *out_distance = dist;
+              if (out_pos)
+                *out_pos = p;
+              if (out_offset)
+                *out_offset = measure->start + (measure->end - measure->start) * progress;
+              if (out_tangent)
+                *out_tangent = t;
+              result = TRUE;
+              if (tolerance >= dist)
+                  return TRUE;
+              threshold = dist - tolerance;
+            }
+        }
+    }
+
+  return result;
+}
+
 static void
 gsk_standard_contour_init (GskContour *contour,
                            GskPathFlags flags,
@@ -1128,6 +1418,7 @@ static const GskContourClass GSK_STANDARD_CONTOUR_CLASS =
   gsk_standard_contour_init_measure,
   gsk_standard_contour_free_measure,
   gsk_standard_contour_get_point,
+  gsk_standard_contour_get_closest_point,
   gsk_standard_contour_copy,
   gsk_standard_contour_add_segment
 };
@@ -1224,6 +1515,31 @@ gsk_contour_get_point (GskPath          *path,
   self->klass->get_point (self, measure_data, distance, pos, tangent);
 }
 
+gboolean
+gsk_contour_get_closest_point (GskPath                *path,
+                               gsize                   i,
+                               gpointer                measure_data,
+                               float                   tolerance,
+                               const graphene_point_t *point,
+                               float                   threshold,
+                               float                  *out_distance,
+                               graphene_point_t       *out_pos,
+                               float                  *out_offset,
+                               graphene_vec2_t        *out_tangent)
+{
+  GskContour *self = path->contours[i];
+
+  return self->klass->get_closest_point (self,
+                                         measure_data,
+                                         tolerance,
+                                         point,
+                                         threshold,
+                                         out_distance,
+                                         out_pos,
+                                         out_offset,
+                                         out_tangent);
+}
+
 /* PATH */
 
 static GskPath *
diff --git a/gsk/gskpathmeasure.c b/gsk/gskpathmeasure.c
index ba16dfdbcc..a86838a78e 100644
--- a/gsk/gskpathmeasure.c
+++ b/gsk/gskpathmeasure.c
@@ -255,6 +255,120 @@ gsk_path_measure_get_point (GskPathMeasure   *self,
                          tangent);
 }
 
+/**
+ * gsk_path_measure_get_closest_point:
+ * @self: a `GskPathMeasure`
+ * @point: the point to find the closest point to
+ * @out_pos: (optional) (out caller-allocates): return location
+ *   for the closest point
+ *
+ * Gets the point on the path that is closest to @point.
+ *
+ * If the path being measured is empty, return 0 and set
+ * @out_pos to (0, 0).
+ *
+ * This is a simpler and slower version of
+ * [method@Gsk.PathMeasure.get_closest_point_full].
+ * Use that one if you need more control.
+ *
+ * Returns: The offset into the path of the closest point
+ **/
+float
+gsk_path_measure_get_closest_point (GskPathMeasure         *self,
+                                    const graphene_point_t *point,
+                                    graphene_point_t       *out_pos)
+{
+  float result;
+
+  g_return_val_if_fail (self != NULL, 0.0f);
+
+  if (gsk_path_measure_get_closest_point_full (self,
+                                               point,
+                                               INFINITY,
+                                               NULL,
+                                               out_pos,
+                                               &result,
+                                               NULL))
+    return result;
+
+  if (out_pos)
+    *out_pos = GRAPHENE_POINT_INIT (0, 0);
+
+  return 0;
+
+}
+
+/**
+ * gsk_path_measure_get_closest_point_full:
+ * @self: a `GskPathMeasure`
+ * @point: the point to find the closest point to
+ * @threshold: The maximum allowed distance between the path and @point.
+ *   Use INFINITY to look for any point.
+ * @out_distance: (optional) (out caller-allocates): The
+ *   distance between the found closest point on the path and the given
+ *   @point.
+ * @out_pos: (optional) (out caller-allocates): return location
+ *   for the closest point
+ * @out_offset: (optional) (out caller-allocates): The offset into
+ *   the path of the found point
+ * @out_tangent: (optional) (out caller-allocates): return location for
+ *   the tangent at the closest point
+ *
+ * Gets the point on the path that is closest to @point. If no point on
+ * path is closer to @point than @threshold, return %FALSE.
+ *
+ * Returns: %TRUE if a point was found, %FALSE otherwise.
+ **/
+gboolean
+gsk_path_measure_get_closest_point_full (GskPathMeasure         *self,
+                                         const graphene_point_t *point,
+                                         float                   threshold,
+                                         float                  *out_distance,
+                                         graphene_point_t       *out_pos,
+                                         float                  *out_offset,
+                                         graphene_vec2_t        *out_tangent)
+{
+  gboolean result;
+  gsize i;
+  float distance, length;
+
+  g_return_val_if_fail (self != NULL, FALSE);
+  g_return_val_if_fail (point != NULL, FALSE);
+
+  result = FALSE;
+  length = 0;
+
+  for (i = 0; i < self->n_contours; i++)
+    {
+      if (gsk_contour_get_closest_point (self->path,
+                                         i,
+                                         self->measures[i].contour_data,
+                                         self->tolerance,
+                                         point,
+                                         threshold,
+                                         &distance,
+                                         out_pos,
+                                         out_offset,
+                                         out_tangent))
+        {
+          result = TRUE;
+          if (out_offset)
+            *out_offset += length;
+
+          if (distance < self->tolerance)
+            break;
+          threshold = distance - self->tolerance;
+        }
+
+      length += self->measures[i].length;
+    }
+
+  if (result && out_distance)
+    *out_distance = distance;
+
+  return result;
+}
+
 /**
  * gsk_path_measure_add_segment:
  * @self: a `GskPathMeasure`
@@ -302,8 +416,10 @@ gsk_path_measure_add_segment (GskPathMeasure *self,
                                                 self->measures[i].contour_data,
                                                 start,
                                                 len);
-          start = 0;
           end -= len;
+          start = 0;
+          if (end <= 0)
+            break;
         }
       else
         {
diff --git a/gsk/gskpathmeasure.h b/gsk/gskpathmeasure.h
index 72db10690c..64b04753da 100644
--- a/gsk/gskpathmeasure.h
+++ b/gsk/gskpathmeasure.h
@@ -51,6 +51,18 @@ void                    gsk_path_measure_get_point              (GskPathMeasure
                                                                  float                   distance,
                                                                  graphene_point_t       *pos,
                                                                  graphene_vec2_t        *tangent);
+GDK_AVAILABLE_IN_ALL
+float                   gsk_path_measure_get_closest_point      (GskPathMeasure         *self,
+                                                                 const graphene_point_t *point,
+                                                                 graphene_point_t       *out_pos);
+GDK_AVAILABLE_IN_ALL
+gboolean                gsk_path_measure_get_closest_point_full (GskPathMeasure         *self,
+                                                                 const graphene_point_t *point,
+                                                                 float                   threshold,
+                                                                 float                  *out_distance,
+                                                                 graphene_point_t       *out_pos,
+                                                                 float                  *out_offset,
+                                                                 graphene_vec2_t        *out_tangent);
 
 GDK_AVAILABLE_IN_ALL
 void                    gsk_path_measure_add_segment            (GskPathMeasure         *self,
diff --git a/gsk/gskpathprivate.h b/gsk/gskpathprivate.h
index 34ec4a549a..ed8db4a49d 100644
--- a/gsk/gskpathprivate.h
+++ b/gsk/gskpathprivate.h
@@ -47,6 +47,16 @@ void                    gsk_contour_get_point                   (GskPath
                                                                  float                 distance,
                                                                  graphene_point_t     *pos,
                                                                  graphene_vec2_t      *tangent);
+gboolean                gsk_contour_get_closest_point           (GskPath                *path,
+                                                                 gsize                   i,
+                                                                 gpointer                measure_data,
+                                                                 float                   tolerance,
+                                                                 const graphene_point_t *point,
+                                                                 float                   threshold,
+                                                                 float                  *out_distance,
+                                                                 graphene_point_t       *out_pos,
+                                                                 float                  *out_offset,
+                                                                 graphene_vec2_t        *out_tangent);
 
 void                    gsk_path_builder_add_contour            (GskPathBuilder       *builder,
                                                                  GskPath              *path,


[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]