gridaco · softmarshmallow · Jun 18, 2025 · Jun 18, 2025
diff --git a/crates/grida-math2/src/lib.rs b/crates/grida-math2/src/lib.rs
@@ -10,6 +10,7 @@ pub mod packing;
 pub mod range;
 pub mod raster;
 pub mod rect;
+pub mod region;
 pub mod snap;
 pub mod transform;
 pub mod ui;
@@ -55,6 +56,10 @@ pub use rect::{
     pad as rect_pad, positive as rect_positive, quantize as rect_quantize, rotate as rect_rotate,
     to_9points, to_9points_chunk, transform as rect_transform, union,
 };
+pub use region::{
+    Region, contains as region_contains, difference as region_difference,
+    intersects as region_intersects, subtract as region_subtract,
+};
 pub use snap::axis::{
     AxisAlignedPoint, Movement, Snap1DResult, Snap2DAxisAlignedResult, Snap2DAxisConfig,
     axis_locked_by_dominance, normalize as movement_normalize, snap1d, snap2d_axis_aligned,

diff --git a/crates/grida-math2/src/region.rs b/crates/grida-math2/src/region.rs
@@ -0,0 +1,89 @@
+//! Region utilities built on rectangles.
+//!
+//! This module provides simple boolean operations for working with rectangular
+//! regions. Regions are represented as collections of [`Rectangle`], allowing
+//! composition of multiple rectangles.
+//!
+//! These helpers are useful for computing complex spatial queries such as
+//! subtracting holes from a base region or checking spatial relationships.
+
+use crate::rect::{self, Rectangle};
+
+/// A collection of non-overlapping rectangles treated as a single region.
+#[derive(Debug, Clone, PartialEq)]
+pub struct Region {
+    /// Rectangles composing the region.
+    pub rectangles: Vec<Rectangle>,
+}
+
+impl Region {
+    /// Creates a region from potentially overlapping rectangles.
+    ///
+    /// The resulting region will contain non-overlapping rectangles.
+    pub fn from_rectangles(rectangles: Vec<Rectangle>) -> Self {
+        let mut region = Region {
+            rectangles: Vec::new(),
+        };
+        for rect in rectangles {
+            region.add_rectangle(rect);
+        }
+        region
+    }
+
+    /// Adds a rectangle to the region while maintaining non-overlap.
+    fn add_rectangle(&mut self, rect: Rectangle) {
+        // Remove parts already covered by the existing region.
+        let mut parts = vec![rect];
+        for exist in &self.rectangles {
+            let mut next = Vec::new();
+            for p in parts {
+                next.extend(rect::boolean::subtract(p, *exist));
+            }
+            parts = next;
+            if parts.is_empty() {
+                break;
+            }
+        }
+
+        // Any remaining parts are guaranteed to not overlap with existing
+        // rectangles. Append them to the region.
+        self.rectangles.extend(parts);
+    }
+}
+
+/// Returns `true` if two rectangles intersect or touch at the edges.
+pub fn intersects(a: &Rectangle, b: &Rectangle) -> bool {
+    rect::intersects(a, b)
+}
+
+/// Returns `true` if rectangle `a` fully contains rectangle `b`.
+pub fn contains(a: &Rectangle, b: &Rectangle) -> bool {
+    rect::contains(a, b)
+}
+
+/// Subtracts region `b` from region `a`, returning the remaining region.
+pub fn subtract(a: Region, b: Region) -> Region {
+    let mut current = a.rectangles;
+    for hole in b.rectangles {
+        let mut next = Vec::new();
+        for rect in current.into_iter() {
+            next.extend(rect::boolean::subtract(rect, hole));
+        }
+        current = next;
+        if current.is_empty() {
+            break;
+        }
+    }
+    Region::from_rectangles(current)
+}
+
+/// Computes the difference of `base` with one or more hole rectangles.
+///
+/// Each hole is subtracted sequentially from the remaining regions.
+pub fn difference(base: Rectangle, holes: &[Rectangle]) -> Vec<Rectangle> {
+    subtract(
+        Region::from_rectangles(vec![base]),
+        Region::from_rectangles(holes.to_vec()),
+    )
+    .rectangles
+}
diff --git a/crates/grida-math2/tests/region.rs b/crates/grida-math2/tests/region.rs
@@ -0,0 +1,50 @@
+use math2::{
+    Rectangle, Region, region_contains, region_difference, region_intersects, region_subtract,
+};
+
+fn rect(x: f32, y: f32, w: f32, h: f32) -> Rectangle {
+    Rectangle {
+        x,
+        y,
+        width: w,
+        height: h,
+    }
+}
+
+#[test]
+fn difference_multiple_holes() {
+    let base = rect(0.0, 0.0, 30.0, 30.0);
+    let holes = [rect(10.0, 10.0, 10.0, 10.0), rect(0.0, 0.0, 5.0, 30.0)];
+    let result = region_difference(base, &holes);
+    let expected = vec![
+        rect(5.0, 0.0, 25.0, 10.0),
+        rect(5.0, 20.0, 25.0, 10.0),
+        rect(5.0, 10.0, 5.0, 10.0),
+        rect(20.0, 10.0, 10.0, 10.0),
+    ];
+    assert_eq!(result, expected);
+}
+
+#[test]
+fn contains_and_intersects() {
+    let a = rect(0.0, 0.0, 20.0, 20.0);
+    let b = rect(5.0, 5.0, 5.0, 5.0);
+    let c = rect(15.0, 15.0, 10.0, 10.0);
+    assert!(region_contains(&a, &b));
+    assert!(region_intersects(&a, &c));
+    assert!(!region_contains(&a, &c));
+}
+
+#[test]
+fn region_subtract_multiple() {
+    let r1 = rect(0.0, 0.0, 10.0, 10.0);
+    let r2 = rect(15.0, 0.0, 10.0, 10.0);
+    let hole = rect(5.0, 0.0, 10.0, 10.0);
+
+    let a = Region::from_rectangles(vec![r1, r2]);
+    let b = Region::from_rectangles(vec![hole]);
+
+    let result = region_subtract(a, b);
+
+    assert_eq!(result.rectangles, vec![rect(0.0, 0.0, 5.0, 10.0), r2]);
+}