voronoi-go 1.0.1

//! Exact-arithmetic predicates over points and polygons.
//!
//! Nothing here rounds or tolerates. [`ccw`] and [`segments_intersect`] decide
//! by sign alone, and [`point_in_polygon`] by parity of crossings.

use crate::Point;

use super::LineSegment;

/// Signed twice-area of the triangle `(p1, p2, p3)`.
///
/// Positive when `p3` lies to the left of the directed line `p1 → p2`, negative
/// to the right, zero when the three are collinear.
#[must_use]
pub fn ccw(p1: Point, p2: Point, p3: Point) -> f64 {
    (p3.y - p1.y) * (p2.x - p1.x) - (p2.y - p1.y) * (p3.x - p1.x)
}

/// Whether two segments *properly* cross.
///
/// **Strict**: a shared endpoint, a touch, and a collinear overlap are all
/// `false`. Only a crossing where each segment has one endpoint strictly either
/// side of the other counts. Callers depend on this — a chain of segments that
/// meet end to end must not read as self-intersecting.
#[must_use]
pub fn segments_intersect(first: LineSegment, second: LineSegment) -> bool {
    let ccw1 = ccw(first.a, second.a, second.b);
    let ccw2 = ccw(first.b, second.a, second.b);
    let ccw3 = ccw(first.a, first.b, second.a);
    let ccw4 = ccw(first.a, first.b, second.b);

    ccw1 * ccw2 < 0.0 && ccw3 * ccw4 < 0.0
}

/// Signed area of a closed ring, by the shoelace formula.
///
/// The **sign is the ring's winding direction**, which is the only way to tell
/// an enclosed region from the region around it once a graph's faces are being
/// walked: every bounded face winds one way and the unbounded one the other.
/// Board coordinates are y-down, so the sign is the opposite of the y-up
/// convention — compare signs against each other, never against a remembered
/// rule.
///
/// The ring may be given closed (last point repeating the first) or open; the
/// wrap is handled either way and a repeated point contributes nothing. Fewer
/// than three points enclose nothing and give `0.0`.
#[must_use]
pub fn signed_ring_area(ring: &[Point]) -> f64 {
    if ring.len() < 3 {
        return 0.0;
    }

    let mut area = 0.0;
    for (current, next) in ring
        .iter()
        .zip(ring.iter().cycle().skip(1))
        .take(ring.len())
    {
        area += current.x * next.y;
        area -= next.x * current.y;
    }
    area / 2.0
}

/// Whether `point` lies inside `polygon`, by casting a ray and counting
/// crossings.
///
/// A polygon of fewer than three vertices contains nothing. Points exactly on
/// an edge are not classified either way — the ray test is a parity count, not
/// a boundary test.
#[must_use]
pub fn point_in_polygon(point: Point, polygon: &[Point]) -> bool {
    if polygon.len() < 3 {
        return false;
    }

    let mut inside = false;
    // Pairs each vertex with its predecessor, wrapping the first onto the last.
    let previous = polygon.iter().cycle().skip(polygon.len() - 1);
    for (current, previous) in polygon.iter().zip(previous).take(polygon.len()) {
        let crosses = (current.y > point.y) != (previous.y > point.y)
            && point.x
                < (previous.x - current.x) * (point.y - current.y) / (previous.y - current.y)
                    + current.x;
        if crosses {
            inside = !inside;
        }
    }

    inside
}

/// Whether `point` lies inside a set of rings: inside the outer ring and
/// outside every hole.
///
/// Ring 0 is the outer loop and every later ring is a hole, which is the
/// convention a merged group's hull follows — an enclosed enemy group is a hole
/// in the territory around it, and is not part of it. An empty ring set contains
/// nothing.
#[must_use]
pub fn point_in_rings(point: Point, rings: &[Vec<Point>]) -> bool {
    let mut rings = rings.iter();
    let Some(hull) = rings.next() else {
        return false;
    };
    point_in_polygon(point, hull) && !rings.any(|hole| point_in_polygon(point, hole))
}

#[cfg(test)]
mod tests {
    #![allow(clippy::unwrap_used, clippy::expect_used)]

    use super::{ccw, point_in_polygon, point_in_rings, segments_intersect, signed_ring_area};
    use crate::Point;
    use crate::geometry::LineSegment;

    fn p(x: f64, y: f64) -> Point {
        Point::new(x, y)
    }

    fn seg(ax: f64, ay: f64, bx: f64, by: f64) -> LineSegment {
        LineSegment::new(p(ax, ay), p(bx, by))
    }

    #[test]
    fn ccw_signs_the_turn() {
        assert!(ccw(p(0.0, 0.0), p(1.0, 0.0), p(0.0, 1.0)) > 0.0);
        assert!(ccw(p(0.0, 0.0), p(1.0, 0.0), p(0.0, -1.0)) < 0.0);
        assert!(ccw(p(0.0, 0.0), p(1.0, 0.0), p(2.0, 0.0)).abs() < f64::MIN_POSITIVE);
    }

    #[test]
    fn a_proper_crossing_intersects() {
        assert!(segments_intersect(
            seg(-1.0, 0.0, 1.0, 0.0),
            seg(0.0, -1.0, 0.0, 1.0)
        ));
    }

    #[test]
    fn a_shared_endpoint_does_not_intersect() {
        assert!(!segments_intersect(
            seg(0.0, 0.0, 1.0, 0.0),
            seg(1.0, 0.0, 1.0, 1.0)
        ));
        // A T-junction: one segment's endpoint lands in the other's interior.
        assert!(!segments_intersect(
            seg(-1.0, 0.0, 1.0, 0.0),
            seg(0.0, 0.0, 0.0, 1.0)
        ));
    }

    #[test]
    fn a_collinear_overlap_does_not_intersect() {
        assert!(!segments_intersect(
            seg(0.0, 0.0, 2.0, 0.0),
            seg(1.0, 0.0, 3.0, 0.0)
        ));
        // Touching end to end, still collinear.
        assert!(!segments_intersect(
            seg(0.0, 0.0, 2.0, 0.0),
            seg(2.0, 0.0, 4.0, 0.0)
        ));
    }

    #[test]
    fn parallel_segments_do_not_intersect() {
        assert!(!segments_intersect(
            seg(0.0, 0.0, 1.0, 0.0),
            seg(0.0, 1.0, 1.0, 1.0)
        ));
    }

    #[test]
    fn ring_area_signs_the_winding() {
        let square = [p(0.0, 0.0), p(2.0, 0.0), p(2.0, 2.0), p(0.0, 2.0)];
        let area = signed_ring_area(&square);
        let mut reversed = square;
        reversed.reverse();
        assert!((area.abs() - 4.0).abs() < 1e-12);
        assert!((signed_ring_area(&reversed) + area).abs() < 1e-12);
    }

    #[test]
    fn ring_area_ignores_a_repeated_closing_point() {
        let open = [p(0.0, 0.0), p(2.0, 0.0), p(2.0, 2.0), p(0.0, 2.0)];
        let closed = [
            p(0.0, 0.0),
            p(2.0, 0.0),
            p(2.0, 2.0),
            p(0.0, 2.0),
            p(0.0, 0.0),
        ];
        assert!((signed_ring_area(&open) - signed_ring_area(&closed)).abs() < 1e-12);
    }

    #[test]
    fn a_degenerate_ring_has_no_area() {
        assert!(signed_ring_area(&[]).abs() < f64::MIN_POSITIVE);
        assert!(signed_ring_area(&[p(0.0, 0.0), p(1.0, 1.0)]).abs() < f64::MIN_POSITIVE);
    }

    #[test]
    fn point_in_polygon_counts_crossings() {
        let square = [p(0.0, 0.0), p(2.0, 0.0), p(2.0, 2.0), p(0.0, 2.0)];
        assert!(point_in_polygon(p(1.0, 1.0), &square));
        assert!(!point_in_polygon(p(3.0, 1.0), &square));
        assert!(!point_in_polygon(p(-1.0, 1.0), &square));
        assert!(!point_in_polygon(p(1.0, 3.0), &square));
    }

    #[test]
    fn a_degenerate_polygon_contains_nothing() {
        assert!(!point_in_polygon(p(0.0, 0.0), &[]));
        assert!(!point_in_polygon(p(0.0, 0.0), &[p(0.0, 0.0), p(1.0, 1.0)]));
    }

    #[test]
    fn rings_are_a_hull_minus_its_holes() {
        let hull = vec![p(0.0, 0.0), p(10.0, 0.0), p(10.0, 10.0), p(0.0, 10.0)];
        let hole = vec![p(4.0, 4.0), p(6.0, 4.0), p(6.0, 6.0), p(4.0, 6.0)];
        let rings = vec![hull, hole];

        assert!(point_in_rings(p(1.0, 1.0), &rings));
        assert!(
            !point_in_rings(p(5.0, 5.0), &rings),
            "the hole is not inside"
        );
        assert!(!point_in_rings(p(20.0, 5.0), &rings));
    }

    #[test]
    fn a_ring_set_with_no_hull_contains_nothing() {
        assert!(!point_in_rings(p(0.0, 0.0), &[]));
        assert!(!point_in_rings(p(0.0, 0.0), &[Vec::new()]));
    }
}