//! Simple polygon type with validation and basic operations.
//!
//! Per invariant **I1** (spec §2): every parcel polygon must be simple
//! (no self-intersections, no holes), CCW-ordered, with no zero-length
//! edges and no collinear triples within tolerance.

use glam::DVec2;

use super::{segments_properly_intersect, signed_area, EPS_ANGLE, EPS_AREA, EPS_GEOM};

/// Validation errors returned by [`Polygon::new`] and friends.
#[derive(Debug, thiserror::Error)]
#[non_exhaustive]
pub enum PolygonError {
    /// Fewer than 3 vertices.
    #[error("polygon needs at least 3 vertices, got {0}")]
    TooFewVertices(usize),
    /// Two consecutive vertices coincide within `EPS_GEOM`.
    #[error("polygon has a zero-length edge at vertex {0}")]
    ZeroEdge(usize),
    /// Three consecutive vertices are collinear within `EPS_ANGLE`.
    #[error("polygon has collinear vertices at {0}")]
    CollinearTriple(usize),
    /// Polygon edges cross.
    #[error("polygon is self-intersecting")]
    SelfIntersecting,
    /// |signed area| < `EPS_AREA`.
    #[error("polygon has near-zero area")]
    Degenerate,
}

/// A simple polygon stored as a CCW ring of vertices. The ring is not
/// closed in storage (last vertex != first vertex).
#[derive(Debug, Clone, PartialEq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct Polygon {
    verts: Vec<DVec2>,
}

impl Polygon {
    /// Construct a polygon from a vertex ring. Validates I1.
    ///
    /// Cleans up trailing duplicates of the first vertex and reverses
    /// the ring if it was passed clockwise.
    ///
    /// # Errors
    ///
    /// Returns a [`PolygonError`] if validation fails.
    pub fn new(verts: Vec<DVec2>) -> Result<Self, PolygonError> {
        Self::new_inner(verts, true)
    }

    /// Like [`Polygon::new`] but does *not* reject collinear triples.
    /// Used internally for block boundaries, which legitimately
    /// contain collinear-corner vertices when adjacent road segments
    /// are end-to-end (the `colinear_roads` degenerate case in spec
    /// §5).
    pub(crate) fn new_relaxed(verts: Vec<DVec2>) -> Result<Self, PolygonError> {
        Self::new_inner(verts, false)
    }

    fn new_inner(mut verts: Vec<DVec2>, strict: bool) -> Result<Self, PolygonError> {
        // Drop a closing duplicate if present.
        if verts.len() >= 2 {
            let first = verts[0];
            let last = *verts.last().expect("len >= 2");
            if (first - last).length_squared() < EPS_GEOM * EPS_GEOM {
                verts.pop();
            }
        }
        if verts.len() < 3 {
            return Err(PolygonError::TooFewVertices(verts.len()));
        }
        // Zero-edge check.
        for i in 0..verts.len() {
            let j = (i + 1) % verts.len();
            if (verts[j] - verts[i]).length_squared() < EPS_GEOM * EPS_GEOM {
                return Err(PolygonError::ZeroEdge(i));
            }
        }
        // Self-intersection check first — bowtie shapes can have
        // zero algebraic area, which would otherwise be reported as
        // `Degenerate` and obscure the real reason.
        if has_self_intersection(&verts) {
            return Err(PolygonError::SelfIntersecting);
        }
        // Compute signed area; if negative, reverse to CCW.
        let mut area = signed_area(&verts);
        if area < 0.0 {
            verts.reverse();
            area = -area;
        }
        if area < EPS_AREA {
            return Err(PolygonError::Degenerate);
        }
        if strict {
            // Collinear triple check (parcel polygons only — block
            // polygons skip this).
            for i in 0..verts.len() {
                let h = (i + verts.len() - 1) % verts.len();
                let j = (i + 1) % verts.len();
                let a = (verts[i] - verts[h]).normalize_or_zero();
                let b = (verts[j] - verts[i]).normalize_or_zero();
                if (a.x * b.y - a.y * b.x).abs() < EPS_ANGLE && a.dot(b) > 0.0 {
                    return Err(PolygonError::CollinearTriple(i));
                }
            }
        }
        Ok(Self { verts })
    }

    /// Access the vertex ring (CCW, not closed).
    #[must_use]
    pub fn vertices(&self) -> &[DVec2] {
        &self.verts
    }

    /// Replace vertex `idx` with `pos` in place, without re-validating
    /// I1. Used by the shared-vertex registry during atomic vertex
    /// moves; the caller is responsible for calling [`Polygon::new`]
    /// (or equivalent validation) before relying on the polygon's
    /// invariants.
    pub(crate) fn set_vertex_unchecked(&mut self, idx: usize, pos: DVec2) {
        if idx < self.verts.len() {
            self.verts[idx] = pos;
        }
    }

    /// Number of vertices in the ring.
    #[must_use]
    pub fn len(&self) -> usize {
        self.verts.len()
    }

    /// Whether the ring is empty. Always false for a valid polygon
    /// (kept for clippy `len_without_is_empty`).
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.verts.is_empty()
    }

    /// Signed area; always non-negative for a valid CCW polygon.
    #[must_use]
    pub fn area(&self) -> f64 {
        signed_area(&self.verts).abs()
    }

    /// Edges as iterator of `(start, end)` pairs in ring order.
    pub fn edges(&self) -> impl Iterator<Item = (DVec2, DVec2)> + '_ {
        let n = self.verts.len();
        (0..n).map(move |i| (self.verts[i], self.verts[(i + 1) % n]))
    }

    /// Centroid (area-weighted), well-defined for non-degenerate
    /// polygons.
    #[must_use]
    pub fn centroid(&self) -> DVec2 {
        let mut a = 0.0;
        let mut cx = 0.0;
        let mut cy = 0.0;
        let n = self.verts.len();
        for i in 0..n {
            let p = self.verts[i];
            let q = self.verts[(i + 1) % n];
            let cross = p.x * q.y - q.x * p.y;
            a += cross;
            cx += (p.x + q.x) * cross;
            cy += (p.y + q.y) * cross;
        }
        a *= 0.5;
        if a.abs() < EPS_AREA {
            // Fall back to vertex average for near-degenerate input.
            let sum: DVec2 = self.verts.iter().copied().sum();
            return sum / (n as f64);
        }
        DVec2::new(cx / (6.0 * a), cy / (6.0 * a))
    }

    /// Clip this polygon against the closed half-plane defined by a
    /// point on the line and an inward normal. Returns `None` if the
    /// result is empty (everything was on the outer side) or invalid.
    ///
    /// Implements Sutherland–Hodgman polygon-vs-half-plane clipping.
    /// Robust for convex *and* concave inputs as long as the half
    /// plane carves a single piece.
    #[must_use]
    pub fn clip_half_plane(&self, point: DVec2, inward_normal: DVec2) -> Option<Self> {
        let n = inward_normal;
        if n.length_squared() < EPS_GEOM * EPS_GEOM {
            return Some(self.clone());
        }
        let n = n.normalize();
        let inside = |p: DVec2| (p - point).dot(n) >= -EPS_GEOM;
        let intersect = |a: DVec2, b: DVec2| -> Option<DVec2> {
            let da = (a - point).dot(n);
            let db = (b - point).dot(n);
            let denom = da - db;
            if denom.abs() < EPS_GEOM {
                return None;
            }
            let t = da / denom;
            Some(a + (b - a) * t)
        };

        let mut out = Vec::with_capacity(self.verts.len() + 2);
        let len = self.verts.len();
        for i in 0..len {
            let a = self.verts[i];
            let b = self.verts[(i + 1) % len];
            let a_in = inside(a);
            let b_in = inside(b);
            match (a_in, b_in) {
                (true, true) => out.push(b),
                (true, false) => {
                    if let Some(p) = intersect(a, b) {
                        out.push(p);
                    }
                }
                (false, true) => {
                    if let Some(p) = intersect(a, b) {
                        out.push(p);
                    }
                    out.push(b);
                }
                (false, false) => {}
            }
        }
        if out.len() < 3 {
            return None;
        }
        // Strip near-duplicate consecutive vertices.
        let cleaned = strip_near_duplicates(out);
        if cleaned.len() < 3 {
            return None;
        }
        Self::new(cleaned).ok()
    }

    /// Check whether this polygon contains a point (open interior, by
    /// even-odd rule). Valid for simple polygons of any convexity.
    #[must_use]
    pub fn contains(&self, p: DVec2) -> bool {
        let mut inside = false;
        let n = self.verts.len();
        let mut j = n - 1;
        for i in 0..n {
            let a = self.verts[i];
            let b = self.verts[j];
            let cond =
                (a.y > p.y) != (b.y > p.y) && p.x < (b.x - a.x) * (p.y - a.y) / (b.y - a.y) + a.x;
            if cond {
                inside = !inside;
            }
            j = i;
        }
        inside
    }
}

fn strip_near_duplicates(verts: Vec<DVec2>) -> Vec<DVec2> {
    let mut out: Vec<DVec2> = Vec::with_capacity(verts.len());
    for v in verts {
        if let Some(&last) = out.last() {
            if (v - last).length_squared() < EPS_GEOM * EPS_GEOM {
                continue;
            }
        }
        out.push(v);
    }
    if out.len() >= 2 {
        let first = out[0];
        let last = *out.last().expect("len >= 2");
        if (first - last).length_squared() < EPS_GEOM * EPS_GEOM {
            out.pop();
        }
    }
    out
}

fn has_self_intersection(verts: &[DVec2]) -> bool {
    let n = verts.len();
    if n < 4 {
        return false;
    }
    for i in 0..n {
        let a1 = verts[i];
        let a2 = verts[(i + 1) % n];
        // skip self and adjacent edges (share a vertex)
        for j in (i + 2)..n {
            // adjacency wrap: edge (n-1, 0) is adjacent to edge (0, 1)
            if i == 0 && j == n - 1 {
                continue;
            }
            let b1 = verts[j];
            let b2 = verts[(j + 1) % n];
            if segments_properly_intersect(a1, a2, b1, b2) {
                return true;
            }
        }
    }
    false
}

#[cfg(test)]
mod tests {
    use super::*;

    fn unit_square() -> Polygon {
        Polygon::new(vec![
            DVec2::new(0.0, 0.0),
            DVec2::new(1.0, 0.0),
            DVec2::new(1.0, 1.0),
            DVec2::new(0.0, 1.0),
        ])
        .unwrap()
    }

    #[test]
    fn unit_square_area_is_one() {
        assert!((unit_square().area() - 1.0).abs() < 1e-12);
    }

    #[test]
    fn cw_input_is_normalized_to_ccw() {
        let p = Polygon::new(vec![
            DVec2::new(0.0, 0.0),
            DVec2::new(0.0, 1.0),
            DVec2::new(1.0, 1.0),
            DVec2::new(1.0, 0.0),
        ])
        .unwrap();
        assert!((p.area() - 1.0).abs() < 1e-12);
    }

    #[test]
    fn collinear_triple_rejected() {
        let err = Polygon::new(vec![
            DVec2::new(0.0, 0.0),
            DVec2::new(1.0, 0.0),
            DVec2::new(2.0, 0.0),
            DVec2::new(2.0, 1.0),
            DVec2::new(0.0, 1.0),
        ])
        .unwrap_err();
        matches!(err, PolygonError::CollinearTriple(_));
    }

    #[test]
    fn self_intersection_rejected() {
        let err = Polygon::new(vec![
            DVec2::new(0.0, 0.0),
            DVec2::new(1.0, 1.0),
            DVec2::new(1.0, 0.0),
            DVec2::new(0.0, 1.0),
        ])
        .unwrap_err();
        assert!(matches!(err, PolygonError::SelfIntersecting));
    }

    #[test]
    fn contains_point() {
        let p = unit_square();
        assert!(p.contains(DVec2::new(0.5, 0.5)));
        assert!(!p.contains(DVec2::new(1.5, 0.5)));
    }

    #[test]
    fn half_plane_clip_keeps_inside() {
        let p = unit_square();
        // keep y >= 0.5
        let clipped = p
            .clip_half_plane(DVec2::new(0.0, 0.5), DVec2::new(0.0, 1.0))
            .unwrap();
        assert!((clipped.area() - 0.5).abs() < 1e-9);
    }

    #[test]
    fn half_plane_clip_returns_none_when_empty() {
        let p = unit_square();
        let clipped = p.clip_half_plane(DVec2::new(0.0, 2.0), DVec2::new(0.0, 1.0));
        assert!(clipped.is_none());
    }
}
