[gtk/path-work-rebased: 25/121] path: Add gsk_path_measure_get_closest_point()
- From: Matthias Clasen <matthiasc src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gtk/path-work-rebased: 25/121] path: Add gsk_path_measure_get_closest_point()
- Date: Sun, 5 Dec 2021 03:58:52 +0000 (UTC)
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]
