path: root/src/geometry.rs

/// Represents a line segment
#[derive(Debug, Clone, Copy)]
pub struct Line {
    pub start: (f64, f64),
    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 {
    pub x: f64,
    pub y: f64,
    pub width: f64,
    pub height: f64,
}

impl Rect {
    pub fn new(x: f64, y: f64, width: f64, height: f64) -> Self {
        Self {
            x,
            y,
            width,
            height,
        }
    }
}

/// Checks if a point is inside a rectangle
pub fn point_in_rect(point: (f64, f64), rect: &Rect) -> bool {
    point.0 >= rect.x
        && point.0 <= rect.x + rect.width
        && point.1 >= rect.y
        && point.1 <= rect.y + rect.height
}

/// Checks if two rectangles intersect (AABB collision)
pub fn rect_intersects_rect(r1: &Rect, r2: &Rect) -> bool {
    !(r1.x + r1.width < r2.x
        || r2.x + r2.width < r1.x
        || r1.y + r1.height < r2.y
        || r2.y + r2.height < r1.y)
}

/// Checks if two line segments intersect using parametric equations
pub fn line_intersects_line(l1: &Line, l2: &Line) -> bool {
    let x1 = l1.start.0;
    let y1 = l1.start.1;
    let x2 = l1.end.0;
    let y2 = l1.end.1;
    let x3 = l2.start.0;
    let y3 = l2.start.1;
    let x4 = l2.end.0;
    let y4 = l2.end.1;

    let denom = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
    if denom.abs() < 1e-10 {
        return false; // Parallel or coincident
    }

    let t = ((x1 - x3) * (y3 - y4) - (y1 - y3) * (x3 - x4)) / denom;
    let u = -((x1 - x2) * (y1 - y3) - (y1 - y2) * (x1 - x3)) / denom;

    (0.0..=1.0).contains(&t) && (0.0..=1.0).contains(&u)
}

/// Checks if a line segment intersects a rectangle
pub fn line_intersects_rect(line: &Line, rect: &Rect) -> bool {
    if point_in_rect(line.start, rect) || point_in_rect(line.end, rect) {
        return true;
    }

    let edges = [
        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),
        ),
        Line::new(
            (rect.x + rect.width, rect.y + rect.height),
            (rect.x, rect.y + rect.height),
        ),
        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 {
        // Safe cast: width and height are positive map dimensions, divided by cell_size and clamped to at least 1.0
        // The resulting grid size will be reasonable (< millions of cells) for typical map sizes
        #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
        let columns = (width / cell_size).ceil().max(1.0) as usize;
        #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
        let rows = (height / cell_size).ceil().max(1.0) as usize;
        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);

        // Safe cast: coordinates are clamped to [0.0, max] before casting, ensuring valid grid indices
        // The .max(0.0) ensures non-negative, and .min(columns/rows - 1) ensures within bounds
        #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
        let start_column =
            ((min_x / self.cell_size).floor().max(0.0) as usize).min(self.columns - 1);
        #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
        let end_column = ((max_x / self.cell_size).floor().max(0.0) as usize).min(self.columns - 1);
        #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
        let start_row = ((min_y / self.cell_size).floor().max(0.0) as usize).min(self.rows - 1);
        #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
        let end_row = ((max_y / self.cell_size).floor().max(0.0) 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 max_column_idx = if self.columns > 0 {
            self.columns - 1
        } else {
            0
        };
        let max_row_idx = if self.rows > 0 { self.rows - 1 } else { 0 };

        // Safe cast: grid indices are small (< thousands) for typical map sizes, well within f64 precision
        // The coordinates are clamped to valid grid bounds before casting to usize
        #[allow(clippy::cast_precision_loss)]
        let max_column_f64 = max_column_idx as f64;
        #[allow(clippy::cast_precision_loss)]
        let max_row_f64 = max_row_idx as f64;

        #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
        let start_column = ((min_x / self.cell_size)
            .floor()
            .max(0.0)
            .min(max_column_f64)) as usize;
        #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
        let end_column = ((max_x / self.cell_size)
            .floor()
            .max(0.0)
            .min(max_column_f64)) as usize;
        #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
        let start_row = ((min_y / self.cell_size).floor().max(0.0).min(max_row_f64)) as usize;
        #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
        let end_row = ((max_y / self.cell_size).floor().max(0.0).min(max_row_f64)) 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::*;

    #[test]
    fn test_point_in_rect() {
        let rect = Rect::new(10.0, 10.0, 20.0, 20.0);
        assert!(point_in_rect((15.0, 15.0), &rect));
        assert!(point_in_rect((10.0, 10.0), &rect));
        assert!(point_in_rect((30.0, 30.0), &rect));
        assert!(!point_in_rect((5.0, 15.0), &rect));
        assert!(!point_in_rect((35.0, 15.0), &rect));
    }

    #[test]
    fn test_rect_intersects_rect() {
        let r1 = Rect::new(0.0, 0.0, 10.0, 10.0);
        let r2 = Rect::new(5.0, 5.0, 10.0, 10.0);
        let r3 = Rect::new(20.0, 20.0, 10.0, 10.0);

        assert!(rect_intersects_rect(&r1, &r2));
        assert!(rect_intersects_rect(&r2, &r1));
        assert!(!rect_intersects_rect(&r1, &r3));
    }

    #[test]
    fn test_line_intersects_line() {
        let l1 = Line::new((0.0, 0.0), (10.0, 10.0));
        let l2 = Line::new((0.0, 10.0), (10.0, 0.0));
        let l3 = Line::new((20.0, 20.0), (30.0, 30.0));

        assert!(line_intersects_line(&l1, &l2));
        assert!(!line_intersects_line(&l1, &l3));
    }

    #[test]
    fn test_line_intersects_rect() {
        let rect = Rect::new(10.0, 10.0, 20.0, 20.0);
        let l1 = Line::new((0.0, 15.0), (40.0, 15.0)); // Horizontal through
        let l2 = Line::new((15.0, 0.0), (15.0, 40.0)); // Vertical through
        let l3 = Line::new((0.0, 0.0), (5.0, 5.0)); // Outside

        assert!(line_intersects_rect(&l1, &rect));
        assert!(line_intersects_rect(&l2, &rect));
        assert!(!line_intersects_rect(&l3, &rect));
    }
}