[gtk/path-ops: 14/25] path: Fix gsk_path_measure_in_fill

[Matthias Clasen <matthiasc src gnome org>]

commit 8e38c913b04357fab68304d5a3050b4e4058e769
Author: Matthias Clasen <mclasen redhat com>
Date:   Sun Mar 27 11:26:45 2022 -0400

    path: Fix gsk_path_measure_in_fill
    
    This was getting some simple polygon cases wrong :(
    
    The problem here is a misunderstanding in line_get_crossing.
    It was returning 'on edge' when a point of the polygon is
    on the ray, which is not what 'on edge' is about.
    
    Add some test cases involving horizontal edges that coincide
    with the test point.

 gsk/gskcontour.c                   | 31 ++++++++++++++++++++++++-------
 testsuite/gsk/path-special-cases.c | 34 ++++++++++++++++++++++++++++++++++
 2 files changed, 58 insertions(+), 7 deletions(-)
---
diff --git a/gsk/gskcontour.c b/gsk/gskcontour.c
index bcbed9153a..330183af04 100644
--- a/gsk/gskcontour.c
+++ b/gsk/gskcontour.c
@@ -1583,6 +1583,9 @@ gsk_standard_contour_add_segment (const GskContour *contour,
     }
 }
 
+/* Returns twice the winding number, so we can record the
+ * 'point on ray' case by returning an odd number.
+ */
 static inline int
 line_get_crossing (const graphene_point_t *p,
                    const graphene_point_t *p1,
@@ -1590,6 +1593,7 @@ line_get_crossing (const graphene_point_t *p,
                    gboolean               *on_edge)
 {
   int dir = 1;
+  float r;
 
   if (p1->x >= p->x && p2->x >= p->x)
     return 0;
@@ -1603,21 +1607,32 @@ line_get_crossing (const graphene_point_t *p,
       dir = -1;
     }
 
-  if ((p1->x >= p->x && p1->y == p->y) ||
-      (p2->x >= p->x && p2->y == p->y))
+  if ((p1->x <= p->x && p1->y == p->y) ||
+      (p2->x <= p->x && p2->y == p->y))
     {
-        *on_edge = TRUE;
-        return 0;
+      if (p1->y == p2->y)
+        {
+          if (p1->x >= p->x || p2->x >= p->x)
+            *on_edge = TRUE;
+
+          return 0;
+        }
+
+      return dir;
     }
 
   if (p2->y <= p->y || p1->y > p->y)
     return 0;
 
   if (p1->x <= p->x && p2->x <= p->x)
-    return dir;
+    return 2 * dir;
 
-  if (p->x > p1->x + (p->y - p1->y) * (p2->x - p1->x) / (p2->y - p1->y))
-    return dir;
+  r = p1->x + (p->y - p1->y) * (p2->x - p1->x) / (p2->y - p1->y);
+  if (p->x > r)
+    return 2 * dir;
+
+  if (p->x == r)
+    *on_edge = TRUE;
 
   return 0;
 }
@@ -1653,6 +1668,8 @@ gsk_standard_contour_get_winding (const GskContour       *contour,
 
   winding += line_get_crossing (point, &last_point, &self->points[0], on_edge);
 
+  winding /= 2;
+
   return winding;
 }
 
diff --git a/testsuite/gsk/path-special-cases.c b/testsuite/gsk/path-special-cases.c
index 04a575ac1f..79389b5c1a 100644
--- a/testsuite/gsk/path-special-cases.c
+++ b/testsuite/gsk/path-special-cases.c
@@ -306,6 +306,39 @@ test_serialize_custom_contours (void)
   gsk_path_unref (path1);
 }
 
+static void
+test_path_winding (void)
+{
+  struct {
+    const char *path;
+    graphene_point_t point;
+    gboolean result;
+  } tests[] = {
+    { "M 150 103 L 250 100 L 300 103 L 250 180 Z", GRAPHENE_POINT_INIT (175, 100), FALSE },
+    { "M 100 100 L 300 200 L 300 0 Z", GRAPHENE_POINT_INIT (250, 100), TRUE },
+    { "M 100 100 L 300 200 L 300 0 Z", GRAPHENE_POINT_INIT (400, 100), FALSE},
+    { "M 100 100  L 200 100 L 300 200 L 300 0 Z", GRAPHENE_POINT_INIT (50, 100), FALSE },
+    { "M 100 100  L 200 100 L 300 200 L 300 0 Z", GRAPHENE_POINT_INIT (150, 100), TRUE },
+    { "M 100 100  L 200 100 L 300 200 L 300 0 Z", GRAPHENE_POINT_INIT (250, 100), TRUE },
+    { "M 100 100  L 200 100 L 300 200 L 300 0 Z", GRAPHENE_POINT_INIT (400, 100), FALSE },
+  };
+  GskPath *path;
+  GskPathMeasure *measure;
+  gboolean res;
+
+  for (int i = 0; i < G_N_ELEMENTS (tests); i++)
+    {
+      path = gsk_path_parse (tests[i].path);
+      measure = gsk_path_measure_new (path);
+
+      res = gsk_path_measure_in_fill (measure, &tests[i].point, GSK_FILL_RULE_WINDING);
+      g_assert_true (res == tests[i].result);
+
+      gsk_path_measure_unref (measure);
+      gsk_path_unref (path);
+    }
+}
+
 int
 main (int   argc,
       char *argv[])
@@ -314,6 +347,7 @@ main (int   argc,
 
   g_test_add_func ("/path/rsvg-parse", test_rsvg_parse);
   g_test_add_func ("/path/serialize-custom-contours", test_serialize_custom_contours);
+  g_test_add_func ("/path/winding", test_path_winding);
 
   return g_test_run ();
 }