1 files changed, 90 insertions, 12 deletions

diff --git a/src/geometry.rs b/src/geometry.rs
index 5099ada..0841183 100644
--- a/src/geometry.rs
+++ b/src/geometry.rs
@@ -5,6 +5,12 @@ pub struct Line {
     pub end: (f64, f64),
 }
 
+impl Line {
+    pub fn new(start: (f64, f64), end: (f64, f64)) -> Self {
+        Self { start, end }
+    }
+}
+
 /// Represents a rectangle
 #[derive(Debug, Clone, Copy)]
 pub struct Rect {
@@ -14,12 +20,6 @@ pub struct Rect {
     pub height: f64,
 }
 
-impl Line {
-    pub fn new(start: (f64, f64), end: (f64, f64)) -> Self {
-        Self { start, end }
-    }
-}
-
 impl Rect {
     pub fn new(x: f64, y: f64, width: f64, height: f64) -> Self {
         Self {
@@ -71,28 +71,106 @@ pub fn line_intersects_line(l1: &Line, l2: &Line) -> bool {
 
 /// Checks if a line segment intersects a rectangle
 pub fn line_intersects_rect(line: &Line, rect: &Rect) -> bool {
-    // Check if either endpoint is inside the rectangle
     if point_in_rect(line.start, rect) || point_in_rect(line.end, rect) {
         return true;
     }
 
-    // Check intersection with all four edges
     let edges = [
-        Line::new((rect.x, rect.y), (rect.x + rect.width, rect.y)), // Top
+        Line::new((rect.x, rect.y), (rect.x + rect.width, rect.y)),
         Line::new(
             (rect.x + rect.width, rect.y),
             (rect.x + rect.width, rect.y + rect.height),
-        ), // Right
+        ),
         Line::new(
             (rect.x + rect.width, rect.y + rect.height),
             (rect.x, rect.y + rect.height),
-        ), // Bottom
-        Line::new((rect.x, rect.y + rect.height), (rect.x, rect.y)), // Left
+        ),
+        Line::new((rect.x, rect.y + rect.height), (rect.x, rect.y)),
     ];
 
     edges.iter().any(|edge| line_intersects_line(line, edge))
 }
 
+/// Spatial hash grid for fast collision detection
+/// that stores cells as indices of lines.
+pub struct SpatialGrid {
+    cell_size: f64,
+    cells: Vec<Vec<usize>>,
+    columns: usize,
+    rows: usize,
+}
+
+impl SpatialGrid {
+    /// Creates a new spatial grid for the given dimensions
+    pub fn new(width: f64, height: f64, cell_size: f64) -> Self {
+        let columns = ((width / cell_size).ceil() as usize).max(1);
+        let rows = ((height / cell_size).ceil() as usize).max(1);
+        let cells = vec![Vec::new(); columns * rows];
+
+        Self {
+            cell_size,
+            cells,
+            columns,
+            rows,
+        }
+    }
+
+    /// Inserts a line into the spatial grid
+    pub fn insert_line(&mut self, line_idx: usize, line: &Line) {
+        let min_x = line.start.0.min(line.end.0);
+        let max_x = line.start.0.max(line.end.0);
+        let min_y = line.start.1.min(line.end.1);
+        let max_y = line.start.1.max(line.end.1);
+
+        let start_column = ((min_x / self.cell_size).floor() as usize).min(self.columns - 1);
+        let end_column = ((max_x / self.cell_size).floor() as usize).min(self.columns - 1);
+        let start_row = ((min_y / self.cell_size).floor() as usize).min(self.rows - 1);
+        let end_row = ((max_y / self.cell_size).floor() as usize).min(self.rows - 1);
+
+        for row in start_row..=end_row {
+            for col in start_column..=end_column {
+                let cell_idx = row * self.columns + col;
+                self.cells[cell_idx].push(line_idx);
+            }
+        }
+    }
+
+    /// Queries the spatial grid for lines that might intersect with the given rectangle
+    /// Returns line indices without duplicates
+    pub fn query_rect(&self, rect: &Rect) -> impl Iterator<Item = usize> + '_ {
+        let min_x = rect.x;
+        let max_x = rect.x + rect.width;
+        let min_y = rect.y;
+        let max_y = rect.y + rect.height;
+
+        let start_column = ((min_x / self.cell_size).floor() as isize)
+            .max(0)
+            .min(self.columns as isize - 1) as usize;
+        let end_column = ((max_x / self.cell_size).floor() as isize)
+            .max(0)
+            .min(self.columns as isize - 1) as usize;
+        let start_row = ((min_y / self.cell_size).floor() as isize)
+            .max(0)
+            .min(self.rows as isize - 1) as usize;
+        let end_row = ((max_y / self.cell_size).floor() as isize)
+            .max(0)
+            .min(self.rows as isize - 1) as usize;
+
+        let mut line_indices = Vec::new();
+        for row in start_row..=end_row {
+            for column in start_column..=end_column {
+                let cell_idx = row * self.columns + column;
+                line_indices.extend_from_slice(&self.cells[cell_idx]);
+            }
+        }
+
+        line_indices.sort_unstable();
+        line_indices.dedup();
+
+        line_indices.into_iter()
+    }
+}
+
 #[cfg(test)]
 mod tests {
     use super::*;