[gtk/path-ops: 16/25] curve: Fix line-curve intersections

[Matthias Clasen <matthiasc src gnome org>]

commit 0222354a7391c56c4fb9e5afc8399c632ab77057
Author: Matthias Clasen <mclasen redhat com>
Date:   Sun Mar 27 22:32:26 2022 -0400

    curve: Fix line-curve intersections
    
    Tests included.

 gsk/gskcurveintersect.c             | 17 +++++----
 testsuite/gsk/curve-special-cases.c | 76 +++++++++++++++++++++++++++++++++++++
 testsuite/gsk/meson.build           |  2 +-
 3 files changed, 86 insertions(+), 9 deletions(-)
---
diff --git a/gsk/gskcurveintersect.c b/gsk/gskcurveintersect.c
index 8fed02ffbc..fe868594bc 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
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/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'],