[gtk/path-ops: 6/19] curve: Handle self-intersection

[Matthias Clasen <matthiasc src gnome org>]

commit 5991bec13ba99413faa4000a9efa999311d2076e
Author: Matthias Clasen <mclasen redhat com>
Date:   Mon Mar 21 00:14:52 2022 -0400

    curve: Handle self-intersection

 gsk/gskcurveintersect.c | 73 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 73 insertions(+)
---
diff --git a/gsk/gskcurveintersect.c b/gsk/gskcurveintersect.c
index 1b0d820dfa..83085f08de 100644
--- a/gsk/gskcurveintersect.c
+++ b/gsk/gskcurveintersect.c
@@ -423,6 +423,76 @@ general_intersect (const GskCurve   *curve1,
   return pos;
 }
 
+static int
+curve_self_intersect (const GskCurve   *curve,
+                      float            *t1,
+                      float            *t2,
+                      graphene_point_t *p,
+                      int               n)
+{
+  float tt[3], ss[3], s;
+  graphene_point_t pp[3];
+  int m;
+  GskCurve cs, ce;
+
+  if (curve->op != GSK_PATH_CURVE)
+    return 0;
+
+  s = 0.5;
+  m = gsk_curve_get_curvature_points (curve, tt);
+  for (int i = 0; i < m; i++)
+    {
+      if (gsk_curve_get_curvature (curve, tt[i], NULL) == 0)
+        {
+          s = tt[i];
+          break;
+        }
+    }
+
+  gsk_curve_split (curve, s, &cs, &ce);
+
+  m = gsk_curve_intersect (&cs, &ce, tt, ss, pp, 3);
+
+  if (m > 1)
+    {
+      if (tt[0] != 1)
+        {
+          t1[0] = t2[0] = tt[0] * s;
+          p[0] = pp[0];
+        }
+      else if (tt[1] != 1)
+        {
+          t1[0] = t2[0] = tt[1] * s;
+          p[0] = pp[1];
+        }
+      if (ss[0] != 0)
+        {
+          t1[1] = t2[1] = s + ss[0] * (1 - s);
+          p[1] = pp[0];
+        }
+      else if (ss[1] != 0)
+        {
+          t1[1] = t2[1] = s + ss[1] * (1 - s);
+          p[1] = pp[1];
+        }
+
+      return 2;
+    }
+  else if (m == 1)
+    {
+      if (tt[0] != 1 && ss[0] != 0)
+        {
+          t1[0] = t2[0] = tt[0] * s;
+          t1[1] = t2[1] = s + ss[0] * (1 - s);
+          p[0] = p[1] = pp[0];
+
+          return 2;
+        }
+    }
+
+  return 0;
+}
+
 /* Place intersections between the curves in p, and their Bezier positions
  * in t1 and t2, up to n. Return the number of intersections found.
  *
@@ -445,6 +515,9 @@ gsk_curve_intersect (const GskCurve   *curve1,
   if (op2 == GSK_PATH_CLOSE)
     op2 = GSK_PATH_LINE;
 
+  if (curve1 == curve2)
+    return curve_self_intersect (curve1, t1, t2, p, n);
+
   /* We special-case line-line and line-curve intersections,
    * since we can solve them directly.
    * Everything else is done via bisection.