[gtk/path-ops: 4/8] path: Implement boolean ops




commit eccdf2146a8c3e3adb3ebe89acd19ee07b5689fc
Author: Matthias Clasen <mclasen redhat com>
Date:   Thu Mar 24 01:41:02 2022 -0400

    path: Implement boolean ops
    
    This adds apis for union, intersection, difference
    and symmetric difference of two paths.
    
    The implementation is not super-robust yet.

 gsk/gskpath.h         |  16 ++
 gsk/gskpathsimplify.c | 765 ++++++++++++++++++++++++++++++++++++++------------
 2 files changed, 605 insertions(+), 176 deletions(-)
---
diff --git a/gsk/gskpath.h b/gsk/gskpath.h
index 60188009aa..feb7a3e9a5 100644
--- a/gsk/gskpath.h
+++ b/gsk/gskpath.h
@@ -124,6 +124,22 @@ GskPath *               gsk_path_offset                         (GskPath
                                                                  GskLineJoin             line_join,
                                                                  float                   miter_limit);
 
+GDK_AVAILABLE_IN_ALL
+GskPath *               gsk_path_union                          (GskPath                *first,
+                                                                 GskPath                *second);
+
+GDK_AVAILABLE_IN_ALL
+GskPath *               gsk_path_intersection                   (GskPath                *first,
+                                                                 GskPath                *second);
+
+GDK_AVAILABLE_IN_ALL
+GskPath *               gsk_path_difference                     (GskPath                *first,
+                                                                 GskPath                *second);
+
+GDK_AVAILABLE_IN_ALL
+GskPath *               gsk_path_symmetric_difference           (GskPath                *first,
+                                                                 GskPath                *second);
+
 GDK_AVAILABLE_IN_ALL
 GskPath *               gsk_path_simplify                       (GskPath                *self);
 
diff --git a/gsk/gskpathsimplify.c b/gsk/gskpathsimplify.c
index 835eca5220..b79af4cca7 100644
--- a/gsk/gskpathsimplify.c
+++ b/gsk/gskpathsimplify.c
@@ -48,8 +48,13 @@ typedef struct
   GskCurve curve;
   Connection *start;
   Connection *end;
-  gboolean internal;
+  gboolean interior;
+  gboolean area_to_the_left;
+  gboolean area_to_the_right;
+  gboolean classified;
   gboolean collected;
+  float start_angle;
+  float end_angle;
   char *name;
 } Curve;
 
@@ -60,15 +65,6 @@ curve_free (Curve *c)
   g_free (c);
 }
 
-typedef struct
-{
-  GList *curves;
-  GList *connections;
-  Curve *start;
-} SimplifyData;
-
-static int collect_num = 0;
-
 static gboolean
 is_stationary_close (GskCurve *curve)
 {
@@ -76,12 +72,23 @@ is_stationary_close (GskCurve *curve)
           graphene_point_near (&curve->line.points[0], &curve->line.points[1], 0.01);
 }
 
+static gboolean
+is_tiny (GskCurve *curve)
+{
+  GskBoundingBox bounds;
+
+  gsk_curve_get_bounds (curve, &bounds);
+
+  return bounds.max.x - bounds.min.x < 0.01 &&
+         bounds.max.y - bounds.min.y < 0.01;
+}
+
 static void
 merge_connections (GList      **connections,
                    Connection  *c1,
                    Connection  *c2)
 {
-  g_assert (graphene_point_near (&c1->p, &c2->p, 0.1));
+  //g_assert (graphene_point_near (&c1->p, &c2->p, 0.1));
 
   if (c1 == c2)
     return;
@@ -101,17 +108,24 @@ merge_connections (GList      **connections,
   connection_free (c2);
 }
 
+typedef struct
+{
+  GList *curves;
+  GList *connections;
+  Curve *start;
+  int num;
+} CollectData;
+
 static gboolean
-simplify_collect_cb (GskPathOperation        op,
-                     const graphene_point_t *pts,
-                     gsize                   n_pts,
-                     float                   weight,
-                     gpointer                user_data)
+collect_cb (GskPathOperation        op,
+            const graphene_point_t *pts,
+            gsize                   n_pts,
+            float                   weight,
+            gpointer                user_data)
 {
-  SimplifyData *data = user_data;
+  CollectData *data = user_data;
   Curve *curve;
   Connection *connection;
-  const char *opname[] = { "Move", "Close", "Line", "Curve", "Conic" };
 
   g_assert (op != GSK_PATH_CONIC);
 
@@ -139,6 +153,7 @@ simplify_collect_cb (GskPathOperation        op,
       curve->curve.op = GSK_PATH_MOVE;
       curve->curve.line.points[0] = pts[0];
       curve->end = connection;
+      g_ptr_array_add (curve->end->edges, curve);
 
       data->curves = g_list_prepend (data->curves, curve);
       data->start = curve;
@@ -182,7 +197,10 @@ simplify_collect_cb (GskPathOperation        op,
     }
 
 #ifdef G_ENABLE_DEBUG
-  curve->name = g_strdup_printf ("%s %d", opname[op], collect_num++);
+  {
+    const char *opname[] = { "Move", "Close", "Line", "Curve", "Conic" };
+    curve->name = g_strdup_printf ("%s %d", opname[op], data->num++);
+  }
 #endif
 
   return TRUE;
@@ -192,61 +210,82 @@ static void
 gsk_path_builder_append_curve (GskPathBuilder *builder,
                                GskCurve       *curve)
 {
-  switch (curve->op)
-    {
-    case GSK_PATH_CLOSE:
-      gsk_path_builder_close (builder);
-      break;
-
-    case GSK_PATH_MOVE:
-      gsk_path_builder_move_to (builder, curve->line.points[0].x, curve->line.points[0].y);
-      break;
-
-    case GSK_PATH_LINE:
-      gsk_path_builder_line_to (builder, curve->line.points[1].x, curve->line.points[1].y);
-      break;
-
-    case GSK_PATH_CURVE:
-      gsk_path_builder_curve_to (builder,
-                                 curve->curve.points[1].x, curve->curve.points[1].y,
-                                 curve->curve.points[2].x, curve->curve.points[2].y,
-                                 curve->curve.points[3].x, curve->curve.points[3].y);
-      break;
-
-    case GSK_PATH_CONIC:
-      gsk_path_builder_conic_to (builder,
-                                 curve->conic.points[1].x, curve->conic.points[1].y,
-                                 curve->conic.points[2].x, curve->conic.points[2].y,
-                                 curve->conic.points[3].x);
-      break;
-
-    default:
-      g_assert_not_reached ();
-    }
+  if (curve->op == GSK_PATH_MOVE)
+    gsk_path_builder_move_to (builder, curve->line.points[0].x, curve->line.points[0].y);
+  else
+    gsk_curve_builder_to (curve, builder);
 }
 
-#define NEAR(f1, f2) (fabs ((f2) - (f1)) < 1e-3)
+typedef enum
+{
+  PATH_OP_SIMPLIFY,
+  PATH_OP_UNION,
+  PATH_OP_INTERSECTION,
+  PATH_OP_DIFFERENCE,
+  PATH_OP_XOR
+} PathOp;
+
+typedef struct
+{
+  PathOp operation;
+  GskPathMeasure *first;
+  GskPathMeasure *second;
+} PathOpData;
 
 static gboolean
-curve_is_external (GskCurve       *curve,
-                   GskPathMeasure *measure)
+point_is_inside (graphene_point_t *p,
+                 PathOpData       *opdata)
+{
+  gboolean in1, in2;
+
+  in1 = gsk_path_measure_in_fill (opdata->first, p, GSK_FILL_RULE_WINDING);
+  if (opdata->second)
+    in2 = gsk_path_measure_in_fill (opdata->second, p, GSK_FILL_RULE_WINDING);
+  else
+    in2 = FALSE;
+  switch (opdata->operation)
+    {
+    case PATH_OP_SIMPLIFY:     return in1;
+    case PATH_OP_UNION:        return in1 || in2;
+    case PATH_OP_INTERSECTION: return in1 && in2;
+    case PATH_OP_DIFFERENCE:   return in1 && !in2;
+    case PATH_OP_XOR:          return in1 != in2;
+    default: g_assert_not_reached ();
+    }
+}
+
+static void
+classify_boundary (Curve      *curve,
+                   PathOpData *opdata)
 {
   graphene_point_t pos, pos1, pos2;
   graphene_vec2_t normal;
 
-  if (curve->op == GSK_PATH_MOVE || is_stationary_close (curve))
-     return TRUE;
+  gsk_curve_get_point (&curve->curve, 0.5, &pos);
+  gsk_curve_get_normal (&curve->curve, 0.5, &normal);
 
-  gsk_curve_get_point (curve, 0.5, &pos);
-  gsk_curve_get_normal (curve, 0.5, &normal);
+  pos1.x = pos.x + 0.5 * graphene_vec2_get_x (&normal);
+  pos1.y = pos.y + 0.5 * graphene_vec2_get_y (&normal);
+  pos2.x = pos.x - 0.5 * graphene_vec2_get_x (&normal);
+  pos2.y = pos.y - 0.5 * graphene_vec2_get_y (&normal);
 
-  pos1.x = pos.x + 5 * graphene_vec2_get_x (&normal);
-  pos1.y = pos.y + 5 * graphene_vec2_get_y (&normal);
-  pos2.x = pos.x - 5 * graphene_vec2_get_x (&normal);
-  pos2.y = pos.y - 5 * graphene_vec2_get_y (&normal);
+  curve->area_to_the_left = point_is_inside (&pos1, opdata);
+  curve->area_to_the_right = point_is_inside (&pos2, opdata);
+  curve->interior = curve->area_to_the_left == curve->area_to_the_right;
+  curve->classified = TRUE;
+}
 
-  return gsk_path_measure_in_fill (measure, &pos1, GSK_FILL_RULE_WINDING) !=
-         gsk_path_measure_in_fill (measure, &pos2, GSK_FILL_RULE_WINDING);
+static void
+compute_angles (Curve *curve)
+{
+  graphene_vec2_t tangent;
+
+  gsk_curve_get_start_tangent (&curve->curve, &tangent);
+  curve->start_angle = atan2 (- graphene_vec2_get_y (&tangent),
+                              - graphene_vec2_get_x (&tangent));
+  gsk_curve_get_end_tangent (&curve->curve, &tangent);
+  curve->end_angle = atan2 (graphene_vec2_get_y (&tangent),
+                            graphene_vec2_get_x (&tangent));
 }
 
 static Curve *
@@ -254,33 +293,118 @@ find_next (Curve *curve)
 {
   Connection *c = curve->end;
   Curve *next = NULL;
+  guint idx;
+  int dir;
 
-  g_print ("at %s:\n", curve->name);
-  for (int i = 0; i < c->edges->len; i++)
+  g_assert (c != NULL);
+  g_assert (c->edges != NULL);
+
+  GSK_NOTE (PATHS,
+    g_print ("at %s:\n", curve->name);
+    for (int i = 0; i < c->edges->len; i++)
+      {
+        Curve *n = g_ptr_array_index (c->edges, i);
+        const char *ind = "  ";
+        float angle;
+
+        if (n->collected) ind = "()";
+        else if (n->interior) ind = "[]";
+
+        angle = n->start == c ? n->start_angle : n->end_angle;
+
+        g_print ("\t%c%s%c %g\n", ind[0], n->name, ind[1], angle);
+      }
+  );
+
+  if (curve->curve.op == GSK_PATH_MOVE)
     {
-      Curve *n = g_ptr_array_index (c->edges, i);
-      g_print ("\t%s\n", n->name);
-    }
+      /* If we start a new contour, we just need to pick an
+       * eligible outgoing curve.
+       */
+      for (int d = 0; d < c->edges->len; d++)
+        {
+          Curve *n = g_ptr_array_index (c->edges, d);
+
+          if (n->collected || n->interior)
+            continue;
+
+          if (n->curve.op == GSK_PATH_MOVE)
+            continue;
 
-  for (int i = 0; i < c->edges->len; i++)
+          if (n->end == c)
+            continue;
+
+          next = n;
+          break;
+        }
+    }
+  else
     {
-      Curve *n = g_ptr_array_index (c->edges, i);
+      /* Edges are sorted counterclockwise by their tangent.
+       * We pick the next eligible edge to the left
+       * or to the right of curve, depending on whether
+       * the left or right is inside.
+       */
+      g_ptr_array_find (c->edges, curve, &idx);
+      dir = curve->area_to_the_left ? -1 : 1;
+      for (int d = 0; d < c->edges->len; d++)
+        {
+          guint pos = (idx + dir * (d + 1)) % c->edges->len;
+          Curve *n = g_ptr_array_index (c->edges, pos);
+          float angle;
 
-      if (n->collected || n->internal)
-        continue;
+          if (n->collected || n->interior)
+            continue;
 
-       if (next != NULL && n->curve.op == GSK_PATH_CLOSE)
-         continue;
+          if (n->curve.op == GSK_PATH_MOVE)
+            continue;
 
-       if (next != NULL && next->start == c)
-         continue;
+          angle = n->end == c ? n->end_angle : n->start_angle;
+          if (fabs (angle - curve->end_angle) < 0.0001)
+            continue;
 
-       if (next != NULL)
-         g_print ("Two candidates. Do the sorting dance!\n");
+          next = n;
+          break;
+        }
+    }
 
-       next = n;
+  if (next && next->end == c)
+    {
+      GskCurve r;
+      Connection *s;
+      gboolean a;
+
+      GSK_NOTE (PATHS, g_print ("reversing %s\n", next->name));
+      gsk_curve_reverse (&next->curve, &r);
+      next->curve = r;
+      s = next->start;
+      next->start = next->end;
+      next->end = s;
+      a = next->area_to_the_left;
+      next->area_to_the_left = next->area_to_the_right;
+      next->area_to_the_right = a;
     }
 
+  GSK_NOTE (PATHS,
+    if (next == NULL)
+      {
+        g_print ("at %s: next is NULL\n", curve->name);
+        for (int i = 0; i < c->edges->len; i++)
+          {
+            Curve *n = g_ptr_array_index (c->edges, i);
+            const char *ind = "  ";
+            float angle;
+
+            if (n->collected) ind = "()";
+            else if (n->interior) ind = "[]";
+
+            angle = n->start == c ? n->start_angle : n->end_angle;
+
+            g_print ("\t%c%s%c %g\n", ind[0], n->name, ind[1], angle);
+          }
+      }
+    );
+
   return next;
 }
 
@@ -289,21 +413,22 @@ validate_curves (GList    *curves,
                  gboolean  split)
 {
 #ifdef G_ENABLE_DEBUG
-  Curve *start;
 
   for (GList *l = curves; l; l = l->next)
     {
       Curve *c = l->data;
 
       GSK_NOTE (PATHS,
-        g_print ("%s%s: ", c->internal ? "(" : "", c->name);
+        g_print ("%s%s: ", c->interior ? "(" : "", c->name);
         if (c->curve.op != GSK_PATH_MOVE)
           gsk_curve_print (&c->curve);
         else
           g_print ("%g %g", c->curve.line.points[0].x, c->curve.line.points[0].y);
-        g_print ("%s\n", c->internal ? ")" : "");
+        g_print ("%s\n", c->interior ? ")" : "");
       );
 
+#if 0
+  Curve *start;
       if (c->curve.op == GSK_PATH_MOVE)
         {
           start = NULL;
@@ -317,9 +442,11 @@ validate_curves (GList    *curves,
 
           g_assert (c->start != NULL);
           g_assert (c->end != NULL);
-          g_assert (graphene_point_near (&c->start->p, gsk_curve_get_start_point (&c->curve), 0.001));
-          g_assert (graphene_point_near (&c->end->p, gsk_curve_get_end_point (&c->curve), 0.001));
+          g_assert (graphene_point_near (&c->start->p, gsk_curve_get_start_point (&c->curve), 0.1));
+          g_assert (graphene_point_near (&c->end->p, gsk_curve_get_end_point (&c->curve), 0.1));
 
+#if 0
+  /* This isn't true with MOVE */
           if (split)
             {
               g_assert (c->start->edges->len % 2 == 0);
@@ -332,6 +459,7 @@ validate_curves (GList    *curves,
               g_assert (c->start->edges->len == 2);
               g_assert (c->end->edges->len == 2);
             }
+#endif
 
           g_assert (g_ptr_array_find (c->start->edges, c, &pos));
           g_assert (g_ptr_array_find (c->end->edges, c, &pos));
@@ -342,6 +470,7 @@ validate_curves (GList    *curves,
               g_assert (g_ptr_array_find (start->start->edges, c, &pos));
             }
         }
+#endif
     }
 #endif
 }
@@ -351,57 +480,122 @@ g_list_insert_after (GList    *l,
                      gpointer  data)
 {
   GList *res G_GNUC_UNUSED;
-
+  /* Silence warn-if-unused */
   res = g_list_insert_before (l, l->next, data);
 }
 
-/**
- * gsk_path_simplify:
- * @self: a `GskPath`
- *
- * Create a new path that describes the area as @self,
- * without overlapping contours.
- *
- * Returns: a new `GskPath`
- */
-GskPath *
-gsk_path_simplify (GskPath *self)
+static GskPath *
+gsk_path_remove_unclosed (GskPath *path)
 {
-  SimplifyData data;
+  GSList *contours;
+  GskPath *path2;
+
+  contours = NULL;
+  for (int i = 0; i < gsk_path_get_n_contours (path); i++)
+    {
+      const GskContour *contour = gsk_path_get_contour (path, i);
+      if (gsk_contour_get_flags (contour) & GSK_PATH_CLOSED)
+        contours = g_slist_prepend (contours, (gpointer)contour);
+    }
+
+  GSK_NOTE (PATHS, g_print ("%ld contours, %d closed\n", gsk_path_get_n_contours (path), g_slist_length 
(contours)));
+
+  contours = g_slist_reverse (contours);
+  path2 = gsk_path_new_from_contours (contours);
+  g_slist_free (contours);
+
+  gsk_path_unref (path);
+
+  return path2;
+}
+
+#define NEAR(f1, f2) (fabs ((f2) - (f1)) < 0.0001)
+
+typedef struct
+{
+  float t1;
+  float t2;
+  graphene_point_t p;
+  Connection *connection;
+} SplitPoint;
+
+static int
+compare_t1 (const void *p1,
+            const void *p2)
+{
+  const SplitPoint *sp1 = p1;
+  const SplitPoint *sp2 = p2;
+  return sp1->t1 < sp2->t1 ? -1 : (sp1->t1 > sp2->t1 ? 1 : 0);
+}
+
+static int
+compare_t2 (const void *p1,
+            const void *p2)
+{
+  const SplitPoint *sp1 = p1;
+  const SplitPoint *sp2 = p2;
+  return sp1->t2 < sp2->t2 ? -1 : (sp1->t2 > sp2->t2 ? 1 : 0);
+}
+
+static int
+compare_angle (gconstpointer p1,
+               gconstpointer p2,
+               gpointer      user_data)
+{
+  Connection *c = user_data;
+  Curve *c1 = *(Curve **)p1;
+  Curve *c2 = *(Curve **)p2;
+  float f1 = c1->start == c ? c1->start_angle : c1->end_angle;
+  float f2 = c2->start == c ? c2->start_angle : c2->end_angle;
+
+  return f1 < f2 ? -1 : (f1 > f2 ? 1 : 0);
+}
+
+static GskPath *
+gsk_path_op (PathOp   operation,
+             GskPath *self,
+             GskPath *other)
+{
+  GList *curves;
+  GList *connections;
+  CollectData data;
   GskPathBuilder *builder;
   GList *l, *ll;
-  GskPathMeasure *measure;
-  gboolean closed;
+  PathOpData opdata;
 
   /* Special-case convex paths */
-  if (gsk_path_compute_convexity (self) == GSK_CONVEXITY_CONVEX)
+  if (operation == PATH_OP_SIMPLIFY &&
+      gsk_path_compute_convexity (self) == GSK_CONVEXITY_CONVEX)
     return gsk_path_ref (self);
 
   GSK_NOTE (PATHS, g_print ("collecting\n"));
 
   data.curves = NULL;
   data.connections = NULL;
+  data.num = 0;
 
-  collect_num = 0;
-  gsk_path_foreach (self, GSK_PATH_FOREACH_ALLOW_CURVE, simplify_collect_cb, &data);
+  gsk_path_foreach (self, GSK_PATH_FOREACH_ALLOW_CURVE, collect_cb, &data);
+  if (other)
+    gsk_path_foreach (other, GSK_PATH_FOREACH_ALLOW_CURVE, collect_cb, &data);
 
-  data.curves = g_list_reverse (data.curves);
-  data.connections = g_list_reverse (data.connections);
+  curves = g_list_reverse (data.curves);
+  connections = g_list_reverse (data.connections);
 
-  validate_curves (data.curves, FALSE);
+  validate_curves (curves, FALSE);
 
-  GSK_NOTE (PATHS, g_print ("intersecting\n"));
-  l = data.curves;
+  GSK_NOTE (PATHS, g_print ("splitting\n"));
+  l = curves;
   while (l)
     {
       Curve *cd1 = l->data;
 
       while (l && (cd1->curve.op == GSK_PATH_MOVE ||
-                   is_stationary_close (&cd1->curve)))
+                   is_tiny (&cd1->curve)))
         {
           l = l->next;
-          if (l)
-            cd1 = l->data;
+          if (!l)
+            break;
+          cd1 = l->data;
         }
 
       if (!l)
@@ -410,44 +604,61 @@ gsk_path_simplify (GskPath *self)
       ll = l;
       while (ll)
         {
-          Curve *cd2 = ll->data;
+          Curve *cd2;
           float t1[9], t2[9];
-          graphene_point_t p [9];
+          graphene_point_t p[9];
+          SplitPoint sp[9];
           int n;
-          GList *next;
-          Connection *connection;
           GskCurve cs, ce;
           Curve *cd;
+          GList *before;
+          char *name;
+
+          cd1 = l->data;
+          cd2 = ll->data;
 
           while (ll && (cd2->curve.op == GSK_PATH_MOVE ||
-                        is_stationary_close (&cd2->curve)))
+                        is_tiny (&cd2->curve)))
             {
               ll = ll->next;
-              if (ll)
-                cd2 = ll->data;
+              if (!ll)
+                break;
+              cd2 = ll->data;
             }
 
           if (!ll)
             break;
 
-          next = ll->next;
-
           n = gsk_curve_intersect (&cd1->curve, &cd2->curve, t1, t2, p, sizeof (p));
+
+          GSK_NOTE (PATHS,
+            if (n > 1 || (n == 1 && (!NEAR (t1[0], 0) && !NEAR (t1[0], 1))))
+              g_print ("%d intersections between %s and %s\n",
+                       n, cd1->name, cd2->name);
+          );
+
+          for (int i = 0; i < n; i++)
+            sp[i] = (SplitPoint) { t1[i], t2[i], p[i], NULL};
+
+          qsort (sp, n, sizeof (SplitPoint), compare_t1);
+
+          name = g_strdup (cd1->name);
+          before = l;
           for (int i = 0; i < n; i++)
             {
-              if (NEAR (t1[i], 0))
-                connection = cd1->start;
-              else if (NEAR (t1[i], 1))
-                connection = cd1->end;
+              if (NEAR (sp[i].t1, 0))
+                sp[i].connection = cd1->start;
+              else if (NEAR (sp[i].t1, 1))
+                sp[i].connection = cd1->end;
               else
                 {
-                  connection = g_new0 (Connection, 1);
-                  connection->p = p[i];
-                  connection->edges = g_ptr_array_new ();
+                  sp[i].connection = g_new0 (Connection, 1);
+                  sp[i].connection->p = sp[i].p;
+                  sp[i].connection->edges = g_ptr_array_new ();
 
-                  data.connections = g_list_prepend (data.connections, connection);
+                  connections = g_list_prepend (connections, sp[i].connection);
 
-                  gsk_curve_split (&cd1->curve, t1[i], &cs, &ce);
+                  gsk_curve_split (&cd1->curve, sp[i].t1, &cs, &ce);
                   cd1->curve = cs;
 
                   cd = g_new0 (Curve, 1);
@@ -455,26 +666,61 @@ gsk_path_simplify (GskPath *self)
                   cd->end = cd1->end;
                   g_ptr_array_remove (cd->end->edges, cd1);
                   g_ptr_array_add (cd->end->edges, cd);
+
 #ifdef G_ENABLE_DEBUG
-                  cd->name = g_strdup_printf ("%s.%d", cd1->name, i);
+                  if (i == 0)
+                    {
+                      char *nn = g_strdup_printf ("%s.0", name);
+                      g_free (cd1->name);
+                      cd1->name = nn;
+                    }
+                  cd->name = g_strdup_printf ("%s.%d", name, i + 1);
 #endif
 
-                  cd1->end = connection;
-                  cd->start = connection;
-
-                  g_list_insert_after (l, cd);
-
-                  g_ptr_array_add (connection->edges, cd1);
-                  g_ptr_array_add (connection->edges, cd);
+                  GSK_NOTE (PATHS,
+                    if (i == 0)
+                      {
+                        g_print ("split %s from %s at %g\n", cd1->name, name, sp[i].t1);
+                        g_print ("%s%s: ", cd1->interior ? "(" : "", cd1->name);
+                        gsk_curve_print (&cd1->curve);
+                        g_print ("%s\n", cd1->interior ? ")" : "");
+                      }
+                  );
+                  GSK_NOTE (PATHS,
+                    g_print ("split %s from %s at %g\n", cd->name, name, sp[i].t1);
+                    g_print ("%s%s: ", cd->interior ? "(" : "", cd->name);
+                    gsk_curve_print (&cd->curve);
+                    g_print ("%s\n", cd->interior ? ")" : "");
+                  );
+
+                  cd1->end = sp[i].connection;
+                  cd->start = sp[i].connection;
+
+                  g_list_insert_after (before, cd);
+                  before = before->next;
+
+                  g_ptr_array_add (sp[i].connection->edges, cd1);
+                  g_ptr_array_add (sp[i].connection->edges, cd);
+
+                  cd1 = cd;
+                  for (int j = i + 1; j < n; j++)
+                    sp[j].t1 = (sp[j].t1 - sp[i].t1) / (1 - sp[i].t1);
                 }
+            }
+          g_free (name);
+
+          qsort (sp, n, sizeof (SplitPoint), compare_t2);
 
-              if (NEAR (t2[i], 0))
-                merge_connections (&data.connections, connection, cd2->start);
-              else if (NEAR (t2[i], 1))
-                merge_connections (&data.connections, connection, cd2->end);
+          name = g_strdup (cd2->name);
+          for (int i = 0; i < n; i++)
+            {
+              if (NEAR (sp[i].t2, 0))
+                merge_connections (&connections, sp[i].connection, cd2->start);
+              else if (NEAR (sp[i].t2, 1))
+                merge_connections (&connections, sp[i].connection, cd2->end);
               else
                 {
-                  gsk_curve_split (&cd2->curve, t2[i], &cs, &ce);
+                  gsk_curve_split (&cd2->curve, sp[i].t2, &cs, &ce);
                   cd2->curve = cs;
 
                   cd = g_new0 (Curve, 1);
@@ -482,21 +728,50 @@ gsk_path_simplify (GskPath *self)
                   cd->end = cd2->end;
                   g_ptr_array_remove (cd->end->edges, cd2);
                   g_ptr_array_add (cd->end->edges, cd);
+
 #ifdef G_ENABLE_DEBUG
-                  cd->name = g_strdup_printf ("%s.%d", cd2->name, i);
+                  if (i == 0)
+                    {
+                      char *nn = g_strdup_printf ("%s.0", name);
+                      g_free (cd2->name);
+                      cd2->name = nn;
+                    }
+                  cd->name = g_strdup_printf ("%s.%d", name, i + 1);
 #endif
 
-                  cd2->end = connection;
-                  cd->start = connection;
+                  GSK_NOTE (PATHS,
+                    if (i == 0)
+                      {
+                        g_print ("split %s from %s at %g\n", cd2->name, name, sp[i].t2);
+                        g_print ("%s%s: ", cd2->interior ? "(" : "", cd2->name);
+                        gsk_curve_print (&cd2->curve);
+                        g_print ("%s\n", cd2->interior ? ")" : "");
+                      }
+                  );
+                  GSK_NOTE (PATHS,
+                    g_print ("split %s from %s at %g\n", cd->name, name, sp[i].t2);
+                    g_print ("%s%s: ", cd->interior ? "(" : "", cd->name);
+                    gsk_curve_print (&cd->curve);
+                    g_print ("%s\n", cd->interior ? ")" : "");
+                  );
+
+                  cd2->end = sp[i].connection;
+                  cd->start = sp[i].connection;
 
                   g_list_insert_after (ll, cd);
+                  ll = ll->next;
+
+                  g_ptr_array_add (sp[i].connection->edges, cd2);
+                  g_ptr_array_add (sp[i].connection->edges, cd);
 
-                  g_ptr_array_add (connection->edges, cd2);
-                  g_ptr_array_add (connection->edges, cd);
+                  cd2 = cd;
+                  for (int j = i + 1; j < n; j++)
+                    sp[j].t2 = (sp[j].t2 - sp[i].t2) / (1 - sp[i].t2);
                 }
             }
+          g_free (name);
 
-          ll = next;
+          ll = ll->next;
         }
 
       l = l->next;
@@ -504,78 +779,216 @@ gsk_path_simplify (GskPath *self)
 
   GSK_NOTE (PATHS, g_print ("classifying\n"));
 
-  measure = gsk_path_measure_new (self);
+  opdata.operation = operation;
+  opdata.first = gsk_path_measure_new (self);
+  opdata.second = other ? gsk_path_measure_new (other) : NULL;
 
-  for (l = data.curves; l; l = l->next)
+  for (l = curves; l; l = l->next)
     {
        Curve *curve = l->data;
 
-       curve->internal = !curve_is_external (&curve->curve, measure);
+       if (curve->curve.op == GSK_PATH_MOVE || is_stationary_close (&curve->curve))
+         continue;
+
+       compute_angles (curve);
+
+#if 0
+       if (curve->start->edges->len == 2)
+         {
+           Curve *other_curve;
+
+           if (curve == g_ptr_array_index (curve->start->edges, 0))
+             other_curve = g_ptr_array_index (curve->start->edges, 1);
+           else
+             other_curve = g_ptr_array_index (curve->start->edges, 0);
+           if (other_curve->classified)
+             {
+               /* propagate classification */
+               curve->area_to_the_left = other_curve->area_to_the_left;
+               curve->area_to_the_right = other_curve->area_to_the_right;
+               curve->interior = other_curve->interior;
+               curve->classified = TRUE;
+               continue;
+             }
+         }
+#endif
+
+       classify_boundary (curve, &opdata);
     }
 
-  gsk_path_measure_unref (measure);
+  gsk_path_measure_unref (opdata.first);
+  if (opdata.second)
+    gsk_path_measure_unref (opdata.second);
+
+  validate_curves (curves, TRUE);
 
-  validate_curves (data.curves, TRUE);
+  GSK_NOTE (PATHS, g_print ("sorting\n"));
+
+  for (l = connections; l; l = l->next)
+    {
+      Connection *c = l->data;
+
+      g_ptr_array_sort_with_data (c->edges, compare_angle, c);
+    }
 
   GSK_NOTE (PATHS, g_print ("reassembling\n"));
 
   builder = gsk_path_builder_new ();
-  closed = TRUE;
 
-  for (l = data.curves; l; l = l->next)
+  for (l = curves; l; l = l->next)
     {
       Curve *curve = l->data;
-      const graphene_point_t *p;
+      Connection *start;
 
-      if (curve->collected || curve->internal)
+      if (curve->collected || curve->interior)
         continue;
 
-      /* start a new contour */
-      if (!closed)
-        {
-          gsk_path_builder_close (builder);
-          closed = TRUE;
-        }
-
       g_assert (curve->curve.op != GSK_PATH_CLOSE);
-      g_assert (!curve->internal);
 
       GSK_NOTE (PATHS, g_print ("start new contour %s\n", curve->name));
       if (curve->curve.op == GSK_PATH_MOVE)
-        p = &curve->curve.line.points[0];
+        start = curve->end;
       else
-        p = gsk_curve_get_start_point (&curve->curve);
-      gsk_path_builder_move_to (builder, p->x, p->y);
+        start = curve->start;
+
+      gsk_path_builder_move_to (builder, start->p.x, start->p.y);
 
       if (curve->curve.op != GSK_PATH_MOVE)
         gsk_path_builder_append_curve (builder, &curve->curve);
 
       curve->collected = TRUE;
-      closed = FALSE;
 
       /* collect segments, following through connections */
       for (curve = find_next (curve); curve; curve = find_next (curve))
         {
-          g_assert (!curve->internal);
+          g_assert (!curve->interior);
 
           if (curve->collected)
-            break;
+            {
+              g_warning ("find_next returned collected %s, falling off\n", curve->name);
+              break;
+            }
 
           GSK_NOTE (PATHS, g_print ("append %s\n", curve->name));
           gsk_path_builder_append_curve (builder, &curve->curve);
           curve->collected = TRUE;
 
-          if (curve->curve.op == GSK_PATH_CLOSE ||
-              curve->curve.op == GSK_PATH_MOVE)
+          if (curve->curve.op == GSK_PATH_CLOSE)
+            {
+              GSK_NOTE (PATHS, g_print ("explicitly closed\n"));
+              break;
+            }
+
+          if (curve->end == start)
             {
-              closed = TRUE;
+              GSK_NOTE (PATHS, g_print ("implicitly closed\n"));
+              gsk_path_builder_close (builder);
               break;
             }
         }
+
+      gsk_path_builder_close (builder);
+    }
+
+#ifdef G_ENABLE_DEBUG
+  /* Check that we've collected all */
+  for (l = curves; l; l = l->next)
+    {
+       Curve *curve = l->data;
+       g_assert (curve->interior == !curve->collected);
     }
+#endif
+
+  g_list_free_full (curves, (GDestroyNotify) curve_free);
+  g_list_free_full (connections, (GDestroyNotify) connection_free);
+
+  return gsk_path_remove_unclosed (gsk_path_builder_free_to_path (builder));
+}
+
+/**
+ * gsk_path_simplify:
+ * @self: a `GskPath`
+ *
+ * Create a new path that describes the same area as @self,
+ * without overlapping contours.
+ *
+ * Returns: a new `GskPath`
+ */
+GskPath *
+gsk_path_simplify (GskPath *self)
+{
+  GSK_NOTE (PATHS, g_print ("\n***simplify***\n"));
+  return gsk_path_op (PATH_OP_SIMPLIFY, self, NULL);
+}
+
+/**
+ * gsk_path_union:
+ * @first: a `GskPath`
+ * @second: a `GskPath`
+ *
+ * Create a new path that describes the union of the areas
+ * of the given paths.
+ *
+ * Returns: a new `GskPath`
+ */
+GskPath *
+gsk_path_union (GskPath *first,
+                GskPath *second)
+{
+  GSK_NOTE (PATHS, g_print ("\n***union***\n"));
+  return gsk_path_op (PATH_OP_UNION, first, second);
+}
 
-  g_list_free_full (data.curves, (GDestroyNotify) curve_free);
-  g_list_free_full (data.connections, (GDestroyNotify) connection_free);
+/**
+ * gsk_path_intersection:
+ * @first: a `GskPath`
+ * @second: a `GskPath`
+ *
+ * Create a new path that describes the intersection of the areas
+ * of the given paths.
+ *
+ * Returns: a new `GskPath`
+ */
+GskPath *
+gsk_path_intersection (GskPath *first,
+                       GskPath *second)
+{
+  GSK_NOTE (PATHS, g_print ("\n***intersection***\n"));
+  return gsk_path_op (PATH_OP_INTERSECTION, first, second);
+}
 
-  return gsk_path_builder_free_to_path (builder);
+/**
+ * gsk_path_difference:
+ * @first: a `GskPath`
+ * @second: a `GskPath`
+ *
+ * Create a new path that describes the difference of the areas
+ * of the given paths.
+ *
+ * Returns: a new `GskPath`
+ */
+GskPath *
+gsk_path_difference (GskPath *first,
+                     GskPath *second)
+{
+  GSK_NOTE (PATHS, g_print ("\n***difference***\n"));
+  return gsk_path_op (PATH_OP_DIFFERENCE, first, second);
+}
+
+/**
+ * gsk_path_symmetric_difference:
+ * @first: a `GskPath`
+ * @second: a `GskPath`
+ *
+ * Create a new path that describes the symmetric difference
+ * of the areas of the given paths.
+ *
+ * Returns: a new `GskPath`
+ */
+GskPath *
+gsk_path_symmetric_difference (GskPath *first,
+                               GskPath *second)
+{
+  GSK_NOTE (PATHS, g_print ("\n***symmetric difference***\n"));
+  return gsk_path_op (PATH_OP_XOR, first, second);
 }


[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]