[gtk/path-work-rebased] curve: Refine line-line intersection

[Matthias Clasen <matthiasc src gnome org>]

commit f7c0fa9593e8472adf4984e2964a59053668a82a
Author: Matthias Clasen <mclasen redhat com>
Date:   Mon Mar 28 00:18:58 2022 -0400

    curve: Refine line-line intersection
    
    For collinear line segments, return up to 2 intersections
    for the endpoints of the intersection (which is also a
    line segment in this case).
    
    Tests included.

 gsk/gskcurveintersect.c             | 107 +++++++++++++++++++++++++++++++++---
 testsuite/gsk/curve-special-cases.c |  68 +++++++++++++++++++++++
 2 files changed, 168 insertions(+), 7 deletions(-)
---
diff --git a/gsk/gskcurveintersect.c b/gsk/gskcurveintersect.c
index 79b05cfc02..d38788346e 100644
--- a/gsk/gskcurveintersect.c
+++ b/gsk/gskcurveintersect.c
@@ -33,7 +33,8 @@ line_intersect (const GskCurve   *curve1,
                 const GskCurve   *curve2,
                 float            *t1,
                 float            *t2,
-                graphene_point_t *p)
+                graphene_point_t *p,
+                int               n)
 {
   const graphene_point_t *pts1 = curve1->line.points;
   const graphene_point_t *pts2 = curve2->line.points;
@@ -43,22 +44,114 @@ line_intersect (const GskCurve   *curve1,
   float b2 = pts2[0].y - pts2[1].y;
   float det = a1 * b2 - b1 * a2;
 
-  if (det != 0)
+  if (fabs(det) > 0.01)
     {
       float tt =   ((pts1[0].x - pts2[0].x) * b2 - (pts1[0].y - pts2[0].y) * a2) / det;
       float ss = - ((pts1[0].y - pts2[0].y) * a1 - (pts1[0].x - pts2[0].x) * b1) / det;
 
       if (acceptable (tt) && acceptable (ss))
         {
-          p->x = pts1[0].x + tt * (pts1[1].x - pts1[0].x);
-          p->y = pts1[0].y + tt * (pts1[1].y - pts1[0].y);
+          p[0].x = pts1[0].x + tt * (pts1[1].x - pts1[0].x);
+          p[0].y = pts1[0].y + tt * (pts1[1].y - pts1[0].y);
 
-          *t1 = tt;
-          *t2 = ss;
+          t1[0] = tt;
+          t2[0] = ss;
 
           return 1;
         }
     }
+  else /* parallel lines */
+    {
+      float r = a1 * (pts1[1].y - pts2[0].y) - (pts1[1].x - pts2[0].x) * b1;
+      float dist = (r * r) / (a1 * a1 + b1 * b1);
+      float t, s, tt, ss;
+
+      if (dist > 0.01)
+        return 0;
+
+      if (pts1[1].x != pts1[0].x)
+        {
+          t = (pts2[0].x - pts1[0].x) / (pts1[1].x - pts1[0].x);
+          s = (pts2[1].x - pts1[0].x) / (pts1[1].x - pts1[0].x);
+        }
+      else
+        {
+          t = (pts2[0].y - pts1[0].y) / (pts1[1].y - pts1[0].y);
+          s = (pts2[1].y - pts1[0].y) / (pts1[1].y - pts1[0].y);
+        }
+
+      if ((t < 0 && s < 0) || (t > 1 && s > 1))
+        return 0;
+
+      if (acceptable (t))
+        {
+          t1[0] = t;
+          t2[0] = 0;
+          p[0] = pts2[0];
+        }
+      else if (t < 0)
+        {
+          if (pts2[1].x != pts2[0].x)
+            tt = (pts1[0].x - pts2[0].x) / (pts2[1].x - pts2[0].x);
+          else
+            tt = (pts1[0].y - pts2[0].y) / (pts2[1].y - pts2[0].y);
+
+          t1[0] = 0;
+          t2[0] = tt;
+          p[0] = pts1[0];
+        }
+      else
+        {
+          if (pts2[1].x != pts2[0].x)
+            tt = (pts1[1].x - pts2[0].x) / (pts2[1].x - pts2[0].x);
+          else
+            tt = (pts1[1].y - pts2[0].y) / (pts2[1].y - pts2[0].y);
+
+          t1[0] = 1;
+          t2[0] = tt;
+          p[0] = pts1[1];
+        }
+
+      if (acceptable (s))
+        {
+          if (t2[0] == 1)
+            return 1;
+
+          t1[1] = s;
+          t2[1] = 1;
+          p[1] = pts2[1];
+        }
+      else if (s < 0)
+        {
+          if (t1[0] == 0)
+            return 1;
+
+          if (pts2[1].x != pts2[0].x)
+            ss = (pts1[0].x - pts2[0].x) / (pts2[1].x - pts2[0].x);
+          else
+            ss = (pts1[0].y - pts2[0].y) / (pts2[1].y - pts2[0].y);
+
+          t1[1] = 0;
+          t2[1] = ss;
+          p[1] = pts1[0];
+        }
+      else
+        {
+          if (t1[0] == 1)
+            return 1;
+
+          if (pts2[1].x != pts2[0].x)
+            ss = (pts1[1].x - pts2[0].x) / (pts2[1].x - pts2[0].x);
+          else
+            ss = (pts1[1].y - pts2[0].y) / (pts2[1].y - pts2[0].y);
+
+          t1[1] = 1;
+          t2[1] = ss;
+          p[1] = pts1[1];
+        }
+
+      return 2;
+    }
 
   return 0;
 }
@@ -451,7 +544,7 @@ gsk_curve_intersect (const GskCurve   *curve1,
    * Everything else is done via bisection.
    */
   if (op1 == GSK_PATH_LINE && op2 == GSK_PATH_LINE)
-    return line_intersect (curve1, curve2, t1, t2, p);
+    return line_intersect (curve1, curve2, t1, t2, p, n);
   else if (op1 == GSK_PATH_LINE && op2 == GSK_PATH_CURVE)
     return line_curve_intersect (curve1, curve2, t1, t2, p, n);
   else if (op1 == GSK_PATH_CURVE && op2 == GSK_PATH_LINE)
diff --git a/testsuite/gsk/curve-special-cases.c b/testsuite/gsk/curve-special-cases.c
index 1bb16c9a48..14dd527878 100644
--- a/testsuite/gsk/curve-special-cases.c
+++ b/testsuite/gsk/curve-special-cases.c
@@ -223,6 +223,73 @@ test_errant_intersection2 (void)
   g_assert_true (n == 1);
 }
 
+static void
+test_line_intersection_parallel (void)
+{
+  GskCurve l1;
+  GskCurve l2;
+  graphene_point_t p1[1];
+  graphene_point_t p2[2];
+  float t1[3], t2[3];
+  graphene_point_t s[3];
+  int n;
+
+  graphene_point_init (&p1[0], 0, 100);
+  graphene_point_init (&p1[1], 100, 100);
+  gsk_curve_init (&l1, gsk_pathop_encode (GSK_PATH_LINE, p1));
+
+  graphene_point_init (&p2[0], 0, 110);
+  graphene_point_init (&p2[1], 100, 110);
+  gsk_curve_init (&l2, gsk_pathop_encode (GSK_PATH_LINE, p2));
+
+  n = gsk_curve_intersect (&l1, &l2, t1, t2, s, G_N_ELEMENTS (s));
+
+  g_assert_true (n == 0);
+
+  graphene_point_init (&p2[0], 110, 100);
+  graphene_point_init (&p2[1], 210, 100);
+  gsk_curve_init (&l2, gsk_pathop_encode (GSK_PATH_LINE, p2));
+
+  n = gsk_curve_intersect (&l1, &l2, t1, t2, s, G_N_ELEMENTS (s));
+
+  g_assert_true (n == 0);
+
+  graphene_point_init (&p2[0], 0, 100);
+  graphene_point_init (&p2[1], -100, 100);
+  gsk_curve_init (&l2, gsk_pathop_encode (GSK_PATH_LINE, p2));
+
+  n = gsk_curve_intersect (&l1, &l2, t1, t2, s, G_N_ELEMENTS (s));
+
+  g_assert_true (n == 1);
+  g_assert_cmpfloat_with_epsilon (t1[0], 0, 0.001);
+  g_assert_cmpfloat_with_epsilon (t2[0], 0, 0.001);
+
+  graphene_point_init (&p2[0], 20, 100);
+  graphene_point_init (&p2[1], 80, 100);
+  gsk_curve_init (&l2, gsk_pathop_encode (GSK_PATH_LINE, p2));
+
+  n = gsk_curve_intersect (&l1, &l2, t1, t2, s, G_N_ELEMENTS (s));
+
+  g_assert_true (n == 2);
+  g_assert_cmpfloat_with_epsilon (t1[0], 0.2, 0.001);
+  g_assert_cmpfloat_with_epsilon (t1[1], 0.8, 0.001);
+  g_assert_cmpfloat_with_epsilon (t2[0], 0, 0.001);
+  g_assert_cmpfloat_with_epsilon (t2[1], 1, 0.001);
+
+  graphene_point_init (&p2[0], 150, 100);
+  graphene_point_init (&p2[1], 50, 100);
+  gsk_curve_init (&l2, gsk_pathop_encode (GSK_PATH_LINE, p2));
+
+  n = gsk_curve_intersect (&l1, &l2, t1, t2, s, G_N_ELEMENTS (s));
+
+  g_assert_true (n == 2);
+  g_assert_cmpfloat_with_epsilon (t1[0], 1, 0.001);
+  g_assert_cmpfloat_with_epsilon (t1[1], 0.5, 0.001);
+  g_assert_cmpfloat_with_epsilon (t2[0], 0.5, 0.001);
+  g_assert_cmpfloat_with_epsilon (t2[1], 1, 0.001);
+
+}
+
 int
 main (int   argc,
       char *argv[])
@@ -234,6 +301,7 @@ main (int   argc,
   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);
+  g_test_add_func ("/curve/line-intersection-parallel", test_line_intersection_parallel);
 
   return g_test_run ();
 }