[gtk/path-ops: 1/23] curve: Fix line-curve intersections

[Matthias Clasen <matthiasc src gnome org>]

commit be363abd506064d26cf4f4073e9623bb80c464a1
Author: Matthias Clasen <mclasen redhat com>
Date:   Sun Mar 20 21:27:44 2022 -0400

    curve: Fix line-curve intersections

 gsk/gskcurveintersect.c             | 33 +++++++++-------
 testsuite/gsk/curve-special-cases.c | 76 +++++++++++++++++++++++++++++++++++++
 testsuite/gsk/curve.c               | 26 +++++++++++++
 testsuite/gsk/meson.build           |  2 +-
 4 files changed, 122 insertions(+), 15 deletions(-)
---
diff --git a/gsk/gskcurveintersect.c b/gsk/gskcurveintersect.c
index 327827c718..486224b375 100644
--- a/gsk/gskcurveintersect.c
+++ b/gsk/gskcurveintersect.c
@@ -82,15 +82,18 @@ align_points (const graphene_point_t *p,
   graphene_vec2_t n1;
   float angle;
   float s, c;
+  float dist;
 
   get_tangent (a, b, &n1);
   angle = - atan2 (graphene_vec2_get_y (&n1), graphene_vec2_get_x (&n1));
   sincosf (angle, &s, &c);
 
+  dist = sqrtf ((a->x - b->x)*(a->x - b->x) + (a->y - b->y)*(a->y - b->y));
+
   for (int i = 0; i < n; i++)
     {
-      q[i].x = (p[i].x - a->x) * c - (p[i].y - a->y) * s;
-      q[i].y = (p[i].x - a->x) * s + (p[i].y - a->y) * c;
+      q[i].x = ((p[i].x - a->x) * c - (p[i].y - a->y) * s) / dist;
+      q[i].y = ((p[i].x - a->x) * s + (p[i].y - a->y) * c) / dist;
     }
 }
 
@@ -100,12 +103,10 @@ find_point_on_line (const graphene_point_t *p1,
                     const graphene_point_t *q,
                     float                  *t)
 {
-  float tx = p2->x - p1->x;
-  float ty = p2->y - p1->y;
-  float sx = q->x - p1->x;
-  float sy = q->y - p1->y;
-
-  *t = (tx*sx + ty*sy) / (tx*tx + ty*ty);
+  if (p2->x != p1->x)
+    *t = (q->x - p1->x) / (p2->x - p1->x);
+  else
+    *t = (q->y - p1->y) / (p2->y - p1->y);
 }
 
 static float
@@ -231,7 +232,7 @@ line_curve_intersect (const GskCurve   *curve1,
   const graphene_point_t *b = &curve1->line.points[1];
   graphene_point_t pts[4];
   float t[3];
-  int m, i;
+  int m, i, j;
 
   /* Rotate things to place curve1 on the x axis,
    * then solve curve2 for y == 0.
@@ -240,15 +241,19 @@ line_curve_intersect (const GskCurve   *curve1,
 
   m = get_cubic_roots (pts[0].y, pts[1].y, pts[2].y, pts[3].y, t);
 
-  m = MIN (m, n);
+  j = 0;
   for (i = 0; i < m; i++)
     {
-      t2[i] = t[i];
-      gsk_curve_get_point (curve2, t[i], &p[i]);
-      find_point_on_line (a, b, &p[i], &t1[i]);
+      t2[j] = t[i];
+      gsk_curve_get_point (curve2, t2[j], &p[j]);
+      find_point_on_line (a, b, &p[j], &t1[j]);
+      if (acceptable (t1[j]))
+        j++;
+      if (j == n)
+        break;
     }
 
-  return m;
+  return j;
 }
 
 static void
diff --git a/testsuite/gsk/curve-special-cases.c b/testsuite/gsk/curve-special-cases.c
index dae8adbd2a..1bb16c9a48 100644
--- a/testsuite/gsk/curve-special-cases.c
+++ b/testsuite/gsk/curve-special-cases.c
@@ -149,6 +149,80 @@ test_curve_degenerate_tangents (void)
   g_assert_true (graphene_vec2_near (&t, graphene_vec2_x_axis (), 0.0001));
 }
 
+static void
+test_errant_intersection (void)
+{
+  GskCurve c;
+  GskCurve l;
+  graphene_point_t p[4];
+  graphene_point_t q[2];
+  float t1[3], t2[3];
+  graphene_point_t s[3];
+  int n;
+
+  graphene_point_init (&p[0], 888, 482);
+  graphene_point_init (&p[1], 999.333313, 508.666687);
+  graphene_point_init (&p[2], 1080.83325, 544.333313);
+  graphene_point_init (&p[3], 1132.5, 589);
+  gsk_curve_init (&c, gsk_pathop_encode (GSK_PATH_CURVE, p));
+
+  graphene_point_init (&q[0], 886, 680);
+  graphene_point_init (&q[1], 642, 618);
+  gsk_curve_init (&l, gsk_pathop_encode (GSK_PATH_LINE, q));
+
+  n = gsk_curve_intersect (&l, &c, t1, t2, s, G_N_ELEMENTS (s));
+
+  g_assert_true (n == 0);
+}
+
+static void
+test_errant_intersection2 (void)
+{
+  GskCurve c;
+  GskCurve l;
+  graphene_point_t p[4];
+  graphene_point_t q[2];
+  float t1[3], t2[3];
+  graphene_point_t s[3];
+  int n;
+
+  graphene_point_init (&p[0], 1119.5, 772);
+  graphene_point_init (&p[1], 1039.16675, 850.666687);
+  graphene_point_init (&p[2], 925.333313, 890);
+  graphene_point_init (&p[3], 778, 890);
+  gsk_curve_init (&c, gsk_pathop_encode (GSK_PATH_CURVE, p));
+
+  graphene_point_init (&q[0], 1052, 1430);
+  graphene_point_init (&q[1], 734, 762);
+  gsk_curve_init (&l, gsk_pathop_encode (GSK_PATH_LINE, q));
+
+  n = gsk_curve_intersect (&l, &c, t1, t2, s, G_N_ELEMENTS (s));
+
+  g_assert_true (n == 1);
+
+  graphene_point_init (&q[0], 954, 762);
+  graphene_point_init (&q[1], 1292, 1430);
+  gsk_curve_init (&l, gsk_pathop_encode (GSK_PATH_LINE, q));
+
+  n = gsk_curve_intersect (&l, &c, t1, t2, s, G_N_ELEMENTS (s));
+
+  g_assert_true (n == 1);
+
+  graphene_point_init (&p[0], 248, 142);
+  graphene_point_init (&p[1], 283, 103);
+  graphene_point_init (&p[2], 333, 80);
+  graphene_point_init (&p[3], 384, 80);
+  gsk_curve_init (&c, gsk_pathop_encode (GSK_PATH_CURVE, p));
+
+  graphene_point_init (&q[0], 256, 719);
+  graphene_point_init (&q[1], 256, 76);
+  gsk_curve_init (&l, gsk_pathop_encode (GSK_PATH_LINE, q));
+
+  n = gsk_curve_intersect (&l, &c, t1, t2, s, G_N_ELEMENTS (s));
+
+  g_assert_true (n == 1);
+}
+
 int
 main (int   argc,
       char *argv[])
@@ -158,6 +232,8 @@ main (int   argc,
   g_test_add_func ("/curve/special/conic-segment", test_conic_segment);
   g_test_add_func ("/curve/special/tangents", test_curve_tangents);
   g_test_add_func ("/curve/special/degenerate-tangents", test_curve_degenerate_tangents);
+  g_test_add_func ("/curve/errant-intersection", test_errant_intersection);
+  g_test_add_func ("/curve/errant-intersection2", test_errant_intersection2);
 
   return g_test_run ();
 }
diff --git a/testsuite/gsk/curve.c b/testsuite/gsk/curve.c
index 1d6cb73f40..7bae660ac5 100644
--- a/testsuite/gsk/curve.c
+++ b/testsuite/gsk/curve.c
@@ -327,6 +327,31 @@ test_line_curve_intersection (void)
   graphene_rect_contains_point (&b, &p[0]);
 }
 
+static void
+test_line_curve_none_intersection (void)
+{
+  GskCurve c1, c2;
+  graphene_point_t p1[4], p2[2];
+  float t1[9], t2[9];
+  graphene_point_t p[9];
+  int n;
+
+  graphene_point_init (&p1[0], 333, 78);
+  graphene_point_init (&p1[1], 415, 78);
+  graphene_point_init (&p1[2], 463, 131);
+  graphene_point_init (&p1[3], 463, 223);
+
+  graphene_point_init (&p2[0], 520, 476);
+  graphene_point_init (&p2[1], 502, 418);
+
+  gsk_curve_init (&c1, gsk_pathop_encode (GSK_PATH_CURVE, p1));
+  gsk_curve_init (&c2, gsk_pathop_encode (GSK_PATH_LINE, p2));
+
+  n = gsk_curve_intersect (&c1, &c2, t1, t2, p, 1);
+
+  g_assert_cmpint (n, ==, 0);
+}
+
 static void
 test_curve_curve_intersection (void)
 {
@@ -662,6 +687,7 @@ main (int argc, char *argv[])
   g_test_add_func ("/curve/decompose-curve", test_curve_decompose_curve);
   g_test_add_func ("/curve/intersection/line-line", test_line_line_intersection);
   g_test_add_func ("/curve/intersection/line-curve", test_line_curve_intersection);
+  g_test_add_func ("/curve/intersection/line-curve-none", test_line_curve_none_intersection);
   g_test_add_func ("/curve/intersection/curve-curve", test_curve_curve_intersection);
   g_test_add_func ("/curve/intersection/curve-curve-max", test_curve_curve_max_intersection);
   g_test_add_func ("/curve/intersection/horizontal-line", test_curve_intersection_horizontal_line);
diff --git a/testsuite/gsk/meson.build b/testsuite/gsk/meson.build
index da2ce45c37..e8f4fe88b2 100644
--- a/testsuite/gsk/meson.build
+++ b/testsuite/gsk/meson.build
@@ -206,7 +206,7 @@ endforeach
 
 tests = [
   ['curve', ['../../gsk/gskcurve.c', '../../gsk/gskcurveintersect.c'], ['-DGTK_COMPILATION']],
-  ['curve-special-cases', ['../../gsk/gskcurve.c'], ['-DGTK_COMPILATION']],
+  ['curve-special-cases', ['../../gsk/gskcurve.c', '../../gsk/gskcurveintersect.c'], ['-DGTK_COMPILATION']],
   ['dash'],
   ['curve-performance', ['../../gsk/gskcurve.c', '../../gsk/gskcurveintersect.c'], ['-DGTK_COMPILATION']],
   ['path'],