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.

4 files changed, 434 insertions, 1 deletions

diff --git a/gsk/gskpath.c b/gsk/gskpath.c
index 4c3765e63a..22a85e1f33 100644
--- a/gsk/gskpath.c
+++ b/gsk/gskpath.c
@@ -76,6 +76,14 @@ struct _GskContourClass
                                                  float                   distance,
                                                  graphene_point_t       *pos,
                                                  graphene_vec2_t        *tangent);
+  gboolean              (* get_closest_point)   (const GskContour       *contour,
+                                                 gpointer                measure_data,
+                                                 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,
@@ -118,6 +126,40 @@ 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;
+    }
+}
+>>>>>>> 6bed13717b... path: Add gsk_path_measure_get_closest_point()
+
 /* RECT CONTOUR */
 
 typedef struct _GskRectContour GskRectContour;
@@ -246,6 +288,83 @@ 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,
+                                    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;
+
+  /* do unit square math */
+  t.x /= self->width;
+  t.y /= self->height;
+
+  /* move point onto the square */
+  t.x = CLAMP (t.x, 0.f, 1.f);
+  t.y = CLAMP (t.y, 0.f, 1.f);
+  if (t.x > 0 && t.x < 1 && t.y > 0 && t.y < 1)
+    {
+      float diff = MIN (t.x, 1.f - t.x) * self->width - MIN (t.y, 1.f - t.y) * 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.5 ? t.y : 2 - t.y) * ABS (self->height) + 
+                  (t.y > 0.5 ? 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)
@@ -333,6 +452,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
 };
@@ -356,6 +476,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
@@ -506,6 +627,77 @@ gsk_circle_contour_get_point (const GskContour *contour,
     }
 }
 
+static gboolean
+gsk_circle_contour_get_closest_point (const GskContour       *contour,
+                                      gpointer                measure_data,
+                                      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;
+  graphene_vec2_t dir;
+  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;
+
+  graphene_vec2_init (&dir,
+                      point->x - self->center.x,
+                      point->y - self->center.y);
+  graphene_vec2_normalize (&dir, &dir);
+  angle = acos (graphene_vec2_dot (&dir, graphene_vec2_x_axis ()));
+  if (point->y - self->center.y < 0)
+    angle = 2*M_PI - angle;
+
+  angle = RAD_TO_DEG (angle);
+
+  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)
@@ -555,6 +747,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
 };
@@ -908,6 +1101,91 @@ 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,
+                                        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 */
+      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 */ 
+          if (dist < threshold || (!result && dist == threshold))
+            {
+              threshold = dist;
+              if (out_distance)
+                *out_distance = dist;
+              if (out_pos)
+                *out_pos = p;
+              if (out_offset)
+                *out_offset = measure->start + (measure->end - measure->start) * found_progress;
+              if (out_tangent)
+                *out_tangent = t;
+              result = TRUE;
+            }
+        }
+    }
+
+  return result;
+}
+
 static void
 gsk_standard_contour_init (GskContour *contour,
                            GskPathFlags flags,
@@ -1091,6 +1369,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
 };
@@ -1187,6 +1466,29 @@ 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,
+                               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,
+                                         point,
+                                         threshold,
+                                         out_distance,
+                                         out_pos,
+                                         out_offset,
+                                         out_tangent);
+}
+
 /* PATH */
 
 static GskPath *
diff --git a/gsk/gskpathmeasure.c b/gsk/gskpathmeasure.c
index 4b698b9a87..c6cba14cbf 100644
--- a/gsk/gskpathmeasure.c
+++ b/gsk/gskpathmeasure.c
@@ -244,6 +244,114 @@ gsk_path_measure_get_point (GskPathMeasure   *self,
 }
 
 /**
+ * gsk_path_measure_get_closest_point:
+ * @self: a #GskPathMeasure
+ * @point: the point to fond the closest point to
+ * @out_pos: (out) (optional) (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
+ * gsk_path_measure_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,
+                                               &result,
+                                               out_pos,
+                                               NULL,
+                                               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 fond the closest point to
+ * @threshold: The maximum allowed distance between the path and @point.
+ *     Use INFINITY to look for any point.
+ * @out_distance: (out) (optional) (caller-allocates): The 
+ *     distance between the found closest point on the path and the given
+ *     @point.
+ * @out_pos: (out) (optional) (caller-allocates): return location
+ *     for the closest point
+ * @out_offset: (out) (optional) (caller-allocates): The offset into
+ *     the path of the found point
+ * @out_tangent: (out) (optional) (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 pointwas 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;
+
+  g_return_val_if_fail (self != NULL, FALSE);
+  g_return_val_if_fail (point != NULL, FALSE);
+
+  result = FALSE;
+
+  for (i = self->n_contours; i-- > 0; )
+    {
+      if (gsk_contour_get_closest_point (self->path,
+                                         i,
+                                         self->measures[i].contour_data,
+                                         point,
+                                         threshold,
+                                         &threshold,
+                                         out_pos,
+                                         out_offset,
+                                         out_tangent))
+        {
+          result = TRUE;
+        }
+      else if (result)
+        {
+          if (out_offset)
+            *out_offset += self->measures[i].length;
+        }
+    }
+
+  if (result && out_distance)
+    *out_distance = threshold;
+
+  return result;
+}
+
+/**
  * gsk_path_measure_add_segment:
  * @self: a #GskPathMeasure
  * @builder: the builder to add the segment to
@@ -291,8 +399,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 7af9dbcaff..f7a0d2b194 100644
--- a/gsk/gskpathprivate.h
+++ b/gsk/gskpathprivate.h
@@ -47,6 +47,15 @@ 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,
+                                                                 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,