clutter/point: Add ClutterPoint quarilateral testing API

Add a function to check whether a point is inside a quadrilateral
by checking the cross product of vectors with the quadrilateral
points, and the point being checked.

If the passed quadrilateral is zero-sized, no point is ever reported
to be inside it.

This will be used by the next commit when comparing the transformed
actor vertices.

[feaneron: add a commit message and remove unecessary code]

https://gitlab.gnome.org/GNOME/mutter/merge_requests/189

4 files changed, 150 insertions, 0 deletions

diff --git a/clutter/clutter/clutter-base-types.c b/clutter/clutter/clutter-base-types.c
index aeb25c90e..c84f9aa64 100644
--- a/clutter/clutter/clutter-base-types.c
+++ b/clutter/clutter/clutter-base-types.c
@@ -570,6 +570,68 @@ G_DEFINE_BOXED_TYPE_WITH_CODE (ClutterPoint, clutter_point,
                                clutter_point_free,
                                CLUTTER_REGISTER_INTERVAL_PROGRESS (clutter_point_progress))
 
+static int
+clutter_point_compare_line (const ClutterPoint *p,
+                            const ClutterPoint *a,
+                            const ClutterPoint *b)
+{
+  float x1 = b->x - a->x;
+  float y1 = b->y - a->y;
+  float x2 = p->x - a->x;
+  float y2 = p->y - a->y;
+  float cross_z = x1 * y2 - y1 * x2;
+
+  if (cross_z > 0.f)
+    return 1;
+  else if (cross_z < 0.f)
+    return -1;
+  else
+    return 0;
+}
+
+/**
+ * clutter_point_inside_quadrilateral:
+ * @point: a #ClutterPoint to test
+ * @vertices: array of vertices of the quadrilateral, in clockwise order,
+ *            from top-left to bottom-left
+ *
+ * Determines whether a point is inside the convex quadrilateral provided,
+ * and not on any of its edges or vertices.
+ *
+ * Returns: %TRUE if @point is inside the quadrilateral
+ */
+gboolean
+clutter_point_inside_quadrilateral (const ClutterPoint *point,
+                                    const ClutterPoint *vertices)
+{
+  unsigned int i;
+  int first_side;
+
+  first_side = 0;
+
+  for (i = 0; i < 4; i++)
+    {
+      int side;
+
+      side = clutter_point_compare_line (point,
+                                         &vertices[i],
+                                         &vertices[(i + 1) % 4]);
+
+      if (side)
+        {
+          if (first_side == 0)
+            first_side = side;
+          else if (side != first_side)
+            return FALSE;
+        }
+    }
+
+  if (first_side == 0)
+    return FALSE;
+
+  return TRUE;
+}
+
 
 
 /*
diff --git a/clutter/clutter/clutter-types.h b/clutter/clutter/clutter-types.h
index 0f0fb1c2a..050802827 100644
--- a/clutter/clutter/clutter-types.h
+++ b/clutter/clutter/clutter-types.h
@@ -200,6 +200,9 @@ float                   clutter_point_distance  (const ClutterPoint *a,
                                                  const ClutterPoint *b,
                                                  float              *x_distance,
                                                  float              *y_distance);
+CLUTTER_EXPORT
+gboolean clutter_point_inside_quadrilateral     (const ClutterPoint *point,
+                                                 const ClutterPoint *vertices);
 
 /**
  * ClutterSize:
diff --git a/src/tests/clutter/conform/meson.build b/src/tests/clutter/conform/meson.build
index 6821e8963..cf91b374d 100644
--- a/src/tests/clutter/conform/meson.build
+++ b/src/tests/clutter/conform/meson.build
@@ -33,6 +33,7 @@ clutter_conform_tests_general_tests = [
   'interval',
   'script-parser',
   'units',
+  'point',
 ]
 
 clutter_conform_tests_deprecated_tests = [
diff --git a/src/tests/clutter/conform/point.c b/src/tests/clutter/conform/point.c
new file mode 100644
index 000000000..c8ecac709
--- /dev/null
+++ b/src/tests/clutter/conform/point.c
@@ -0,0 +1,84 @@
+#include "tests/clutter-test-utils.h"
+
+#include <clutter/clutter.h>
+
+static void
+point_on_nonempty_quadrilateral (void)
+{
+  int p;
+  static const ClutterPoint vertices[4] =
+    {
+      { 1.f, 2.f },
+      { 6.f, 3.f },
+      { 7.f, 6.f },
+      { 0.f, 5.f }
+    };
+  static const ClutterPoint points_inside[] =
+    {
+      { 2.f, 3.f },
+      { 1.f, 4.f },
+      { 5.f, 5.f },
+      { 4.f, 3.f },
+    };
+  static const ClutterPoint points_outside[] =
+    {
+      { 3.f, 1.f },
+      { 7.f, 4.f },
+      { 4.f, 6.f },
+      { 99.f, -77.f },
+      { -1.f, 3.f },
+      { -8.f, -8.f },
+      { 11.f, 4.f },
+      { -7.f, 4.f },
+    };
+
+  for (p = 0; p < G_N_ELEMENTS (points_inside); p++)
+    {
+      const ClutterPoint *point = &points_inside[p];
+
+      g_assert_true (clutter_point_inside_quadrilateral (point, vertices));
+    }
+
+  for (p = 0; p < G_N_ELEMENTS (points_outside); p++)
+    {
+      const ClutterPoint *point = &points_outside[p];
+
+      g_assert_false (clutter_point_inside_quadrilateral (point, vertices));
+    }
+}
+
+static void
+point_on_empty_quadrilateral (void)
+{
+  int p;
+  static const ClutterPoint vertices[4] =
+    {
+      { 5.f, 6.f },
+      { 5.f, 6.f },
+      { 5.f, 6.f },
+      { 5.f, 6.f },
+    };
+  static const ClutterPoint points_outside[] =
+    {
+      { 3.f, 1.f },
+      { 7.f, 4.f },
+      { 4.f, 6.f },
+      { 99.f, -77.f },
+      { -1.f, 3.f },
+      { -8.f, -8.f },
+    };
+
+  for (p = 0; p < G_N_ELEMENTS (points_outside); p++)
+    {
+      const ClutterPoint *point = &points_outside[p];
+
+      g_assert_false (clutter_point_inside_quadrilateral (point, vertices));
+    }
+
+  g_assert_false (clutter_point_inside_quadrilateral (&vertices[0], vertices));
+}
+
+CLUTTER_TEST_SUITE (
+  CLUTTER_TEST_UNIT ("/point/on_nonempty_quadrilateral", point_on_nonempty_quadrilateral)
+  CLUTTER_TEST_UNIT ("/point/on_empty_quadrilateral", point_on_empty_quadrilateral)
+)