[gegl] gegl-path: add ability to compute y coordinate for a given x

[Øyvind Kolås <ok src gnome org>]

commit f41f3d4614b585e5b0df4d3220f3145c1307934f
Author: Øyvind Kolås <pippin gimp org>
Date:   Tue Apr 5 11:41:10 2016 +0200

    gegl-path: add ability to compute y coordinate for a given x

 gegl/property-types/gegl-path.c |   45 +++++++++++++++++++++++++++++++++++++++
 gegl/property-types/gegl-path.h |   37 ++++++++++++++++++++++---------
 tests/simple/test-path.c        |   38 ++++++++++++++++++++++++++++++++-
 3 files changed, 108 insertions(+), 12 deletions(-)
---
diff --git a/gegl/property-types/gegl-path.c b/gegl/property-types/gegl-path.c
index efd6745..622a0c7 100644
--- a/gegl/property-types/gegl-path.c
+++ b/gegl/property-types/gegl-path.c
@@ -1620,6 +1620,51 @@ gegl_path_point_dist (GeglPathPoint *a,
                (a->y-b->y)*(a->y-b->y));
 }
 
+#define Y_FOR_X_RES 1024
+
+gint gegl_path_calc_y_for_x (GeglPath *path,
+                             gdouble   x,
+                             gdouble  *y)
+{
+  gdouble xs[Y_FOR_X_RES];
+  gdouble ys[Y_FOR_X_RES];
+  gdouble best_xd = 4096.0;
+  gdouble second_best_xd = 4096.0;
+  double sum_xd;
+  gint best = 0;
+  gint second_best = 0;
+
+  int i;
+  if (!y)
+    return -1;
+  gegl_path_calc_values (path, Y_FOR_X_RES, xs, ys);
+  for (i = 0; i < Y_FOR_X_RES; i++)
+  {
+    if (fabs (xs[i] - x) < best_xd)
+    {
+      second_best_xd = best_xd;
+      best_xd = fabs (xs[i] - x);
+      second_best = best;
+      best = i;
+    }
+
+  }
+
+   sum_xd  = best_xd + second_best_xd;
+
+   if (best_xd < 0.0001)
+   {
+     *y = ys[best];
+   }
+   else
+   {
+      *y = ys[best] * (1.0 - (best_xd-sum_xd)/sum_xd) +
+           ys[second_best] * ((best_xd-sum_xd)/sum_xd);
+   }
+
+  return 0;
+}
+
 /* --------------------------------------------------------------------------
  * A GParamSpec class to describe behavior of GeglPath as an object property
  * follows.
diff --git a/gegl/property-types/gegl-path.h b/gegl/property-types/gegl-path.h
index c22bb96..0f1ce8b 100644
--- a/gegl/property-types/gegl-path.h
+++ b/gegl/property-types/gegl-path.h
@@ -214,6 +214,21 @@ gdouble              gegl_path_closest_point  (GeglPath     *path,
                                                gdouble      *on_path_y,
                                                gint         *node_pos_before);
 
+
+/**
+ * gegl_path_calc_y_for_x:
+ * @path: a #GeglPath
+ * @x: x coordinate to compute for
+ * @y: (out): return location for y coordinate
+ *
+ * Compute a corresponding y coordinate for a given x input coordinate,
+ * returns 0 if computed correctly and -1 if the path doesn't exist for the
+ * specified x coordinate.
+ */
+gint gegl_path_calc_y_for_x (GeglPath *path,
+                             gdouble   x,
+                             gdouble  *y);
+
 /**
  * gegl_path_calc:
  * @path: a #GeglPath
@@ -434,7 +449,7 @@ typedef struct GeglPathList
  *
  * Appends to path list, if head is NULL a new list is created
  */ 
-GeglPathList *        gegl_path_list_append   (GeglPathList *head, ...);
+GeglPathList *     gegl_path_list_append   (GeglPathList *head, ...);
 
 /**
  * gegl_path_list_destroy: (skip)
@@ -442,7 +457,7 @@ GeglPathList *        gegl_path_list_append   (GeglPathList *head, ...);
  *
  * Frees up a path list
  */
-GeglPathList *        gegl_path_list_destroy  (GeglPathList *path);
+GeglPathList *     gegl_path_list_destroy  (GeglPathList *path);
 
 
 /***
@@ -461,7 +476,7 @@ typedef GeglPathList *(*GeglFlattenerFunc) (GeglPathList *original);
  * the incoming path (doesn't understand the instructions), the original
  * path should be returned.
  */
-void                  gegl_path_add_flattener (GeglFlattenerFunc func);
+void           gegl_path_add_flattener (GeglFlattenerFunc func);
 
 
 /**
@@ -470,7 +485,7 @@ void                  gegl_path_add_flattener (GeglFlattenerFunc func);
  *
  * Return the internal untouched #GeglPathList
  */
-GeglPathList *        gegl_path_get_path (GeglPath *path);
+GeglPathList * gegl_path_get_path (GeglPath *path);
 
 /**
  * gegl_path_get_flat_path: (skip)
@@ -478,7 +493,7 @@ GeglPathList *        gegl_path_get_path (GeglPath *path);
  *
  * Return a polyline version of @path
  */
-GeglPathList *        gegl_path_get_flat_path (GeglPath *path);
+GeglPathList * gegl_path_get_flat_path (GeglPath *path);
 
 /***
  * GeglPathPoint: (skip)
@@ -493,10 +508,10 @@ GeglPathList *        gegl_path_get_flat_path (GeglPath *path);
  *
  * linear interpolation between two #GeglPathPoint
  */
-void                  gegl_path_point_lerp    (GeglPathPoint    *dest,
-                                               GeglPathPoint    *a,
-                                               GeglPathPoint    *b,
-                                               gfloat            t);
+void           gegl_path_point_lerp    (GeglPathPoint *dest,
+                                        GeglPathPoint *a,
+                                        GeglPathPoint *b,
+                                        gfloat         t);
 
 /**
  * gegl_path_point_dist: (skip)
@@ -505,8 +520,8 @@ void                  gegl_path_point_lerp    (GeglPathPoint    *dest,
  *
  * Compute the distance between #GeglPathPoint @a and @b
  */
-gdouble               gegl_path_point_dist    (GeglPathPoint       *a,
-                                               GeglPathPoint       *b);
+gdouble        gegl_path_point_dist    (GeglPathPoint *a,
+                                        GeglPathPoint *b);
 
 G_END_DECLS
 
diff --git a/tests/simple/test-path.c b/tests/simple/test-path.c
index 7b217ea..c107a62 100644
--- a/tests/simple/test-path.c
+++ b/tests/simple/test-path.c
@@ -8,7 +8,7 @@
 #define SUCCESS  0
 #define FAILURE -1
 
-#define EPSILON 0.00001
+#define EPSILON 0.0005 // XXX < ideally we'd use a 1.5 orders of magnitude smaller epsilon
 
 #define NSMP 3
 static gboolean 
@@ -94,6 +94,20 @@ test_path_calc (GeglPath *path, gdouble pos,
     }
   return TRUE;
 }
+
+static int
+test_path_calc_y_for_x (GeglPath *path, gdouble x, gdouble exp_y)
+{
+  gdouble y = -1.0;
+  gegl_path_calc_y_for_x (path, x, &y);
+  if (! equals (y, exp_y))
+  {
+    fprintf (stderr, "got %f expected %f\n", y, exp_y);
+    return FALSE;
+  }
+  return TRUE;
+}
+
 int main(int argc, char *argv[])
 {
   gdouble exp_x[NSMP],exp_y[NSMP];
@@ -176,6 +190,28 @@ int main(int argc, char *argv[])
    * 4sampl  :    ^     ^     ^     ^
    */
 
+
+  path = gegl_path_new ();
+  gegl_path_append (path, 'M', 0.0, 0.0);
+  gegl_path_append (path, 'L', 0.5, 0.23);
+  gegl_path_append (path, 'L', 1.0, 0.42);
+  if (! test_path_calc_y_for_x (path, 0.5, 0.23))
+  {
+    g_printerr("The gegl_path_calc_y_for_x() 0.5 failed\n");
+    result += FAILURE;
+  }
+  if (! test_path_calc_y_for_x (path, 1.0, 0.42))
+  {
+    g_printerr("The gegl_path_calc_y_for_x() 1.0 failed\n");
+    result += FAILURE;
+  }
+  if (! test_path_calc_y_for_x (path, 0.25, 0.115))
+  {
+    g_printerr("The gegl_path_calc_y_for_x() 0.25 failed\n");
+    result += FAILURE;
+  }
+
+
   gegl_exit ();
 
   return result;