Perform 2D rectangle intersection test and return topology classes

intersection.patch

commit ac3c81578e760af11732da8f925b87ba7b1f70be
Author: Michael Clark <[email protected]>
Date:   Tue Feb 25 10:45:10 2020 +1300

    Perform 2D rectangle intersection test and return topology classes

diff --git a/src/geometry.h b/src/geometry.h
new file mode 100644
index 000000000000..1b5d890c2f58
--- /dev/null
+++ b/src/geometry.h
@@ -0,0 +1,244 @@
+/*
+ * Rectangle Intersection (2D)
+ *
+ * Copyright (c) 2020 Michael Clark <[email protected]>
+ *
+ * License: GPLv3
+ *
+ * Perform 2D rectangle intersection test and returns intersection
+ * topology classes including which axes overlap and the proximal
+ * direction of the rectangles relative to each other when they are
+ * not overlapping. The interface for the intersect function is:
+ *
+ *   - intersect_2d intersect(rect_2d r1, rect_2d r2);
+ *
+ * The rectangle structure contains two points {x, y} relative to
+ * origin with 'x' increasing from left to right and 'y' increasing
+ * fromn top to bottom.
+ *
+ *   - struct rect_2d { vec2 p0, p1; };
+ *
+ * The intersect_2d topology classes are coded using 5 bits:
+ *
+ *   - { inner, north, south, east, west }
+ *
+ * The intersect function returns combinations of these bits forming
+ * 24 distinct classes, with coding efficiency of 91.7%
+ *
+ *   D = log₂(|classes|)/bits
+ *     = log₂(24)/5
+ *     = 4.585/5
+ *     = 0.917
+ *
+ * The algorithm performs 8 less than comparisons {r1,r2}·{p0,p1}·{x,y}
+ * from which it decides the class. Insideness is tested with not less
+ * than p0 and less than p1, so coordinates may need to be biased with
+ * an appropriate epsilon value. 𝛆 = {0.5, 0.5}.
+ */
+
+#pragma once
+
+//* Rectangle (2D) *//
+struct rect_2d
+{
+    glm::vec2 p0, p1;
+};
+
+//* Intersection topology classes *//
+enum intersect_2d
+{
+    /*
+     * Outside cases (0-axis crossing)
+     *
+     *  ░░░░░ ░░░░░ ░░░░░ █░░░░ ░░█░░ ░░░░█ ░░░░░ ░░░░░
+     *  ░┏━┓░ ░┏━┓░ ░┏━┓░ ░┏━┓░ ░┏━┓░ ░┏━┓░ ░┏━┓░ ░┏━┓░
+     *  ░┃░┃░ ░┃░┃░ █┃░┃░ ░┃░┃░ ░┃░┃░ ░┃░┃░ ░┃░┃█ ░┃░┃░
+     *  ░┗━┛░ ░┗━┛░ ░┗━┛░ ░┗━┛░ ░┗━┛░ ░┗━┛░ ░┗━┛░ ░┗━┛░
+     *  ░░█░░ █░░░░ ░░░░░ ░░░░░ ░░░░░ ░░░░░ ░░░░░ ░░░░█
+     *
+     * Fully inside case (0-axis crossing):
+     *
+     *  ░░░░░
+     *  ░┏━┓░
+     *  ░┃█┃░
+     *  ░┗━┛░
+     *  ░░░░░
+     *
+     * Overlap cases (1-axis crossing):
+     *
+     *  ░░░░░ ░░░░░ ░░█░░ ░░░░░
+     *  ░┏━┓░ ░┏━┓░ ░┏█┓░ ░┏━┓░
+     *  ░┃░┃░ ██░┃░ ░┃░┃░ ░┃░██
+     *  ░┗█┛░ ░┗━┛░ ░┗━┛░ ░┗━┛░
+     *  ░░█░░ ░░░░░ ░░░░░ ░░░░░
+     *
+     * Overlap cases (2-axis crossing):
+     *
+     *  ░░░░░ ██░░░ ░░░██ ░░░░░ ░░█░░ ░░░░░
+     *  ░┏━┓░ ██━┓░ ░┏━██ ░┏━┓░ ░┏█┓░ ░┏━┓░
+     *  ░┃░┃░ ░┃░┃░ ░┃░┃░ ░┃░┃░ ░┃█┃░ █████
+     *  ██━┛░ ░┗━┛░ ░┗━┛░ ░┗━██ ░┗█┛░ ░┗━┛░
+     *  ██░░░ ░░░░░ ░░░░░ ░░░██ ░░█░░ ░░░░░
+     *
+     * Overlap cases (3-axis crossing):
+     *
+     *  ██░░░ █████ ░░░██ ░░░░░
+     *  ██━┓░ █████ ░┏━██ ░┏━┓░
+     *  ██░┃░ ░┃░┃░ ░┃░██ ░┃░┃░
+     *  ██━┛░ ░┗━┛░ ░┗━██ █████
+     *  ██░░░ ░░░░░ ░░░██ █████
+     *
+     * Fully surrounded case (4-axis crossing):
+     *
+     *  █████
+     *  █┏━┓█
+     *  █┃█┃█
+     *  █┗━┛█
+     *  █████
+     */
+
+    none               = 0,
+
+    inner              = (1 << 1),
+    north              = (1 << 2),
+    east               = (1 << 3),
+    south              = (1 << 4),
+    west               = (1 << 5),
+
+    north_east         = north | east,
+    north_west         = north | west,
+    south_east         = south | east,
+    south_west         = south | west,
+
+    north_south        = north | south,
+    east_west          = east  | west,
+
+    left               = south | west  | north,
+    top                = west  | north | east,
+    right              = north | east  | south,
+    bottom             = east  | south | west,
+    surrounded         = north | east  | south | west,
+
+    inner_north        = inner | north,
+    inner_north_east   = inner | north | east,
+    inner_east         = inner | east,
+    inner_south_east   = inner | south | east,
+    inner_south        = inner | south,
+    inner_south_west   = inner | south | west,
+    inner_west         = inner | west,
+    inner_north_west   = inner | north | west,
+
+    inner_north_south  = inner | north | south,
+    inner_east_west    = inner | east  | west,
+
+    inner_left         = inner | south | west  | north,
+    inner_top          = inner | west  | north | east,
+    inner_right        = inner | north | east  | south,
+    inner_bottom       = inner | east  | south | west,
+    inner_surrounded   = inner | north | east  | south | west,
+};
+
+intersect_2d intersect(rect_2d r1, rect_2d r2)
+{
+    int r1_p0_x_lt_r2_p0_x = r1.p0.x < r2.p0.x;
+    int r1_p0_x_lt_r2_p1_x = r1.p0.x < r2.p1.x;
+    int r1_p1_x_lt_r2_p0_x = r1.p1.x < r2.p0.x;
+    int r1_p1_x_lt_r2_p1_x = r1.p1.x < r2.p1.x;
+    int r1_p0_y_lt_r2_p0_y = r1.p0.y < r2.p0.y;
+    int r1_p0_y_lt_r2_p1_y = r1.p0.y < r2.p1.y;
+    int r1_p1_y_lt_r2_p0_y = r1.p1.y < r2.p0.y;
+    int r1_p1_y_lt_r2_p1_y = r1.p1.y < r2.p1.y;
+
+    int p0_x_lt = r1_p0_x_lt_r2_p0_x && r1_p0_x_lt_r2_p1_x;
+    int p0_x_in = !r1_p0_x_lt_r2_p0_x && r1_p0_x_lt_r2_p1_x;
+    int p0_x_ge = !r1_p0_x_lt_r2_p0_x && !r1_p0_x_lt_r2_p1_x;
+
+    int p1_x_lt = r1_p1_x_lt_r2_p0_x && r1_p1_x_lt_r2_p1_x;
+    int p1_x_in = !r1_p1_x_lt_r2_p0_x && r1_p1_x_lt_r2_p1_x;
+    int p1_x_ge = !r1_p1_x_lt_r2_p0_x && !r1_p1_x_lt_r2_p1_x;
+
+    int p0_y_lt = r1_p0_y_lt_r2_p0_y && r1_p0_y_lt_r2_p1_y;
+    int p0_y_in = !r1_p0_y_lt_r2_p0_y && r1_p0_y_lt_r2_p1_y;
+    int p0_y_ge = !r1_p0_y_lt_r2_p0_y && !r1_p0_y_lt_r2_p1_y;
+
+    int p1_y_lt = r1_p1_y_lt_r2_p0_y && r1_p1_y_lt_r2_p1_y;
+    int p1_y_in = !r1_p1_y_lt_r2_p0_y && r1_p1_y_lt_r2_p1_y;
+    int p1_y_ge = !r1_p1_y_lt_r2_p0_y && !r1_p1_y_lt_r2_p1_y;
+
+    /* Outside cases:
+     *
+     *  ░░░░░ ░░░░░ ░░░░░ █░░░░ ░░█░░ ░░░░█ ░░░░░ ░░░░░
+     *  ░┏━┓░ ░┏━┓░ ░┏━┓░ ░┏━┓░ ░┏━┓░ ░┏━┓░ ░┏━┓░ ░┏━┓░
+     *  ░┃░┃░ ░┃░┃░ █┃░┃░ ░┃░┃░ ░┃░┃░ ░┃░┃░ ░┃░┃█ ░┃░┃░
+     *  ░┗━┛░ ░┗━┛░ ░┗━┛░ ░┗━┛░ ░┗━┛░ ░┗━┛░ ░┗━┛░ ░┗━┛░
+     *  ░░█░░ █░░░░ ░░░░░ ░░░░░ ░░░░░ ░░░░░ ░░░░░ ░░░░█
+     */
+    unsigned out = 0;
+    out |= (p0_y_lt && p1_y_lt) ? intersect_2d::north : 0;
+    out |= (p0_x_ge && p1_x_ge) ? intersect_2d::east  : 0;
+    out |= (p0_y_ge && p1_y_ge) ? intersect_2d::south : 0;
+    out |= (p0_x_lt && p1_x_lt) ? intersect_2d::west  : 0;
+    if (out) return (intersect_2d)out;
+
+    /* Fully inside case (0-axis crossing):
+     *
+     *  ░░░░░
+     *  ░┏━┓░
+     *  ░┃█┃░
+     *  ░┗━┛░
+     *  ░░░░░
+     */
+    if (p0_x_in && p1_x_in && p0_y_in && p1_y_in) return intersect_2d::inner;
+
+    /* Overlap cases (1-axis crossing):
+     *
+     *  ░░░░░ ░░░░░ ░░█░░ ░░░░░
+     *  ░┏━┓░ ░┏━┓░ ░┏█┓░ ░┏━┓░
+     *  ░┃░┃░ ██░┃░ ░┃░┃░ ░┃░██
+     *  ░┗█┛░ ░┗━┛░ ░┗━┛░ ░┗━┛░
+     *  ░░█░░ ░░░░░ ░░░░░ ░░░░░
+     */
+    else if (p0_x_in && p1_x_in && p0_y_in && p1_y_ge) return intersect_2d::inner_south;
+    else if (p0_x_lt && p1_x_in && p0_y_in && p1_y_in) return intersect_2d::inner_west;
+    else if (p0_x_in && p1_x_in && p0_y_lt && p1_y_in) return intersect_2d::inner_north;
+    else if (p0_x_in && p1_x_ge && p0_y_in && p1_y_in) return intersect_2d::inner_east;
+
+    /* Overlap cases (2-axis crossing):
+     *
+     *  ░░░░░ ██░░░ ░░░██ ░░░░░ ░░█░░ ░░░░░
+     *  ░┏━┓░ ██━┓░ ░┏━██ ░┏━┓░ ░┏█┓░ ░┏━┓░
+     *  ░┃░┃░ ░┃░┃░ ░┃░┃░ ░┃░┃░ ░┃█┃░ █████
+     *  ██━┛░ ░┗━┛░ ░┗━┛░ ░┗━██ ░┗█┛░ ░┗━┛░
+     *  ██░░░ ░░░░░ ░░░░░ ░░░██ ░░█░░ ░░░░░
+     */
+    else if (p0_x_lt && p1_x_in && p0_y_in && p1_y_ge) return intersect_2d::inner_south_west;
+    else if (p0_x_lt && p1_x_in && p0_y_lt && p1_y_in) return intersect_2d::inner_north_west;
+    else if (p0_x_in && p1_x_ge && p0_y_lt && p1_y_in) return intersect_2d::inner_north_east;
+    else if (p0_x_in && p1_x_ge && p0_y_in && p1_y_ge) return intersect_2d::inner_south_east;
+    else if (p0_x_in && p1_x_in && p0_y_lt && p1_y_ge) return intersect_2d::inner_north_south;
+    else if (p0_x_lt && p1_x_ge && p0_y_in && p1_y_in) return intersect_2d::inner_east_west;
+
+    /* Overlap cases (3-axis crossing):
+     *
+     *  ██░░░ █████ ░░░██ ░░░░░
+     *  ██━┓░ █████ ░┏━██ ░┏━┓░
+     *  ██░┃░ ░┃░┃░ ░┃░██ ░┃░┃░
+     *  ██━┛░ ░┗━┛░ ░┗━██ █████
+     *  ██░░░ ░░░░░ ░░░██ █████
+     */
+    else if (p0_x_lt && p1_x_in && p0_y_lt && p1_y_ge) return intersect_2d::inner_left;
+    else if (p0_x_lt && p1_x_ge && p0_y_lt && p1_y_in) return intersect_2d::inner_top;
+    else if (p0_x_in && p1_x_ge && p0_y_lt && p1_y_ge) return intersect_2d::inner_right;
+    else if (p0_x_lt && p1_x_ge && p0_y_in && p1_y_ge) return intersect_2d::inner_bottom;
+
+    /* Fully surrounded case (4-axis crossing):
+     *
+     *   █████
+     *   █┏━┓█
+     *   █┃█┃█
+     *   █┗━┛█
+     *   █████
+     */
+    else if (p0_x_lt && p1_x_ge && p0_y_lt && p1_y_ge) return intersect_2d::inner_surrounded;
+    else return intersect_2d::none;
+}
diff --git a/tests/test0010.cc b/tests/test0010.cc
new file mode 100644
index 000000000000..9dd55bf9bec8
--- /dev/null
+++ b/tests/test0010.cc
@@ -0,0 +1,107 @@
+#undef NDEBUG
+#include <cassert>
+#include <cstdio>
+#include <string>
+
+#include "glm/glm.hpp"
+#include "geometry.h"
+
+const struct { intersect_2d key; const char *name; } map[] = {
+
+    { intersect_2d::none,              "none" },
+
+    { intersect_2d::inner,             "inner" },
+    { intersect_2d::north,             "north" },
+    { intersect_2d::east,              "east" },
+    { intersect_2d::south,             "south" },
+    { intersect_2d::west,              "west" },
+
+    { intersect_2d::north_east,        "north_east" },
+    { intersect_2d::south_east,        "south_east" },
+    { intersect_2d::south_west,        "south_west" },
+    { intersect_2d::north_west,        "north_west" },
+
+    { intersect_2d::north_south,       "north_south" },
+    { intersect_2d::east_west,         "east_west" },
+
+    { intersect_2d::left,              "left" },
+    { intersect_2d::top,               "top" },
+    { intersect_2d::bottom,            "bottom" },
+    { intersect_2d::right,             "right" },
+    { intersect_2d::surrounded,        "surrounded" },
+
+    { intersect_2d::inner_north,       "inner_north" },
+    { intersect_2d::inner_north_east,  "inner_north_east" },
+    { intersect_2d::inner_east,        "inner_east" },
+    { intersect_2d::inner_south_east,  "inner_south_east" },
+    { intersect_2d::inner_south,       "inner_south" },
+    { intersect_2d::inner_south_west,  "inner_south_west" },
+    { intersect_2d::inner_west,        "inner_west" },
+    { intersect_2d::inner_north_west,  "inner_north_west" },
+    { intersect_2d::inner_north_south, "inner_north_south" },
+    { intersect_2d::inner_east_west,   "inner_east_west" },
+    { intersect_2d::inner_left,        "inner_left" },
+    { intersect_2d::inner_top,         "inner_top" },
+    { intersect_2d::inner_bottom,      "inner_bottom" },
+    { intersect_2d::inner_right,       "inner_right" },
+    { intersect_2d::inner_surrounded,  "inner_surrounded" },
+
+    { intersect_2d::none, nullptr },
+};
+
+std::string to_string(intersect_2d n)
+{
+    for (auto *p = map; p->name; p++) {
+        if (p->key == n) return p->name;
+    }
+    return "unknown";
+}
+
+std::string to_string(rect_2d r)
+{
+    char buf[64];
+    snprintf(buf, sizeof(buf),
+        "{{%4.1f,%4.1f },{%4.1f,%4.1f }}",
+        r.p0.x, r.p0.y, r.p1.x, r.p1.y);
+    return std::string(buf);
+}
+
+void test(rect_2d a, rect_2d b, intersect_2d m)
+{
+    intersect_2d n = intersect(a, b);
+    printf("intersect(a: %s, b: %s) -> %-20s # %4s\n",
+        to_string(a).c_str(), to_string(b).c_str(),
+        to_string(m).c_str(), ((n&m) == m) ? "PASS" : "FAIL"
+    );
+    assert((n&m) == m);
+}
+
+int main(int argc, char **argv)
+{
+    test({{3,3},{6,6}}, {{2,2},{7,7}}, intersect_2d::inner);
+    test({{4,1},{5,2}}, {{2,2},{7,7}}, intersect_2d::inner_north);
+    test({{6,4},{8,5}}, {{2,2},{7,7}}, intersect_2d::inner_east);
+    test({{4,6},{5,8}}, {{2,2},{7,7}}, intersect_2d::inner_south);
+    test({{1,4},{3,5}}, {{2,2},{7,7}}, intersect_2d::inner_west);
+    test({{6,1},{8,3}}, {{2,2},{7,7}}, intersect_2d::inner_north_east);
+    test({{1,1},{3,3}}, {{2,2},{7,7}}, intersect_2d::inner_north_west);
+    test({{6,6},{8,8}}, {{2,2},{7,7}}, intersect_2d::inner_south_east);
+    test({{1,6},{3,8}}, {{2,2},{7,7}}, intersect_2d::inner_south_west);
+    test({{4,1},{5,8}}, {{2,2},{7,7}}, intersect_2d::inner_north_south);
+    test({{1,4},{8,5}}, {{2,2},{7,7}}, intersect_2d::inner_east_west);
+    test({{1,1},{4,8}}, {{2,2},{7,7}}, intersect_2d::inner_left);
+    test({{1,1},{8,3}}, {{2,2},{7,7}}, intersect_2d::inner_top);
+    test({{6,1},{8,8}}, {{2,2},{7,7}}, intersect_2d::inner_right);
+    test({{1,6},{8,8}}, {{2,2},{7,7}}, intersect_2d::inner_bottom);
+    test({{1,1},{8,8}}, {{2,2},{7,7}}, intersect_2d::inner_surrounded);
+    test({{4,0},{5,1}}, {{2,2},{7,7}}, intersect_2d::north);
+    test({{8,4},{9,5}}, {{2,2},{7,7}}, intersect_2d::east);
+    test({{4,8},{5,9}}, {{2,2},{7,7}}, intersect_2d::south);
+    test({{0,4},{1,5}}, {{2,2},{7,7}}, intersect_2d::west);
+    test({{8,0},{9,1}}, {{2,2},{7,7}}, intersect_2d::north_east);
+    test({{0,0},{1,1}}, {{2,2},{7,7}}, intersect_2d::north_west);
+    test({{8,8},{9,9}}, {{2,2},{7,7}}, intersect_2d::south_east);
+    test({{0,8},{1,9}}, {{2,2},{7,7}}, intersect_2d::south_west);
+
+    return 0;
+}