voronoi-go 1.0.1

//! The shapes the playable area is clipped out of, and their geometry.
//!
//! Two kinds, and their differences are the whole reason this is an enum rather
//! than a trait object: a dead zone's outline is a closed curve parameterized by
//! angle, a board edge's is an infinite line parameterized by distance along it,
//! and the two run in **opposite directions**. A dead zone's offset increases
//! anticlockwise; a board edge's increases clockwise, so that the board's
//! interior sits on the same side of every shape's outline and the alive zone
//! clips against the edges the same way it clips against a disc.

use core::f64::consts::{PI, TAU};

use crate::geometry::{Arc, Circle, LineSegment, approx_equal, normalize_angle};
use crate::{EPSILON, Point, STONE_DIAMETER, STONE_RADIUS};

use super::SegId;

/// Identifies one shape — a dead-zone circle or a board edge — that the
/// playable area is clipped against.
///
/// Unlike [`SegId`], shape ids are never reused: a reclaimed dead zone that is
/// carved again gets a fresh id. It appears in the public API only as the
/// subject of a [`ZoneError`](crate::ZoneError).
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct ShapeId(u32);

impl ShapeId {
    /// The `n`th shape id.
    pub(super) const fn new(n: usize) -> Self {
        Self(n as u32)
    }

    /// The raw number, for diagnostics.
    #[must_use]
    pub const fn get(self) -> u32 {
        self.0
    }
}

/// Which inset board edge a boundary lies along.
///
/// The order of the variants is the order the four edges are traversed by
/// increasing offset: down the left, along the bottom, up the right, back along
/// the top.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub enum Edge {
    /// `x = STONE_RADIUS`, offset increasing downwards.
    Left,
    /// `y = board_size - STONE_RADIUS`, offset increasing rightwards.
    Bottom,
    /// `x = board_size - STONE_RADIUS`, offset increasing upwards.
    Right,
    /// `y = STONE_RADIUS`, offset increasing leftwards.
    Top,
}

impl Edge {
    /// Every edge, in traversal order.
    pub(super) const ALL: [Self; 4] = [Self::Left, Self::Bottom, Self::Right, Self::Top];
}

/// Whether a shape's segment list wraps around.
///
/// Both are stored as circular doubly-linked lists — that is what keeps
/// insertion and deletion uniform — but only a [`Closure::Closed`] shape's wrap
/// link stands for a real piece of outline. An [`Closure::Open`] shape's list
/// has a head and a tail, and the tail's link back to the head is bookkeeping:
/// walks stop there rather than following it.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum Closure {
    /// The outline is a closed curve; every segment spans to its successor.
    Closed,
    /// The outline is an open curve; the last segment spans nothing.
    Open,
}

/// What a shape is, and all the geometry that follows from it.
#[derive(Clone, Copy, Debug)]
pub enum ShapeKind {
    /// The disc around a stone that no other stone centre may enter. Its offset
    /// is the angle from the centre, in `[0, TAU)`, increasing anticlockwise.
    DeadZone(Circle),
    /// One inset board edge, as an infinite line. Its offset is the distance
    /// travelled along that line in the direction the board is circled, so the
    /// span the board actually occupies is `STONE_RADIUS ..= board_size -
    /// STONE_RADIUS` and everything outside that runs off the board.
    Boundary {
        /// Width and height of the board.
        board_size: f64,
        /// Which edge.
        edge: Edge,
    },
}

/// The two points where a shape crosses a circle.
///
/// `entry` is where the shape passes *into* the circle as its offset increases,
/// `exit` where it comes back out.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Intersection {
    /// Where the shape enters the circle.
    pub entry: Point,
    /// Where the shape leaves it.
    pub exit: Point,
}

/// The piece of outline one segment covers.
#[derive(Clone, Copy, Debug)]
pub enum Span {
    /// A stretch of a dead zone's circumference.
    Arc(Arc),
    /// A stretch of a board edge.
    Line(LineSegment),
}

impl Span {
    /// The point of this span closest to `p`.
    #[must_use]
    pub fn closest_point(self, p: Point) -> Point {
        match self {
            Self::Arc(arc) => arc.closest_point(p),
            Self::Line(line) => line.closest_point(p),
        }
    }

    /// The minimum distance from this span to `line`.
    #[must_use]
    pub fn distance_to_segment(self, line: LineSegment) -> f64 {
        match self {
            Self::Arc(arc) => arc.distance_to_segment(line),
            Self::Line(own) => own.distance_to(line),
        }
    }

    /// Where the span begins.
    ///
    /// Only the outline writer asks: the queries measure against a whole span
    /// rather than stepping along it.
    #[cfg(any(feature = "svg", test))]
    #[must_use]
    pub fn start_point(self) -> Point {
        match self {
            Self::Arc(arc) => arc.start_point(),
            Self::Line(line) => line.a,
        }
    }

    /// Where the span ends.
    #[cfg(any(feature = "svg", test))]
    #[must_use]
    pub fn end_point(self) -> Point {
        match self {
            Self::Arc(arc) => arc.end_point(),
            Self::Line(line) => line.b,
        }
    }
}

impl ShapeKind {
    /// A dead zone of the standard radius around `center`.
    #[must_use]
    pub fn dead_zone(center: Point) -> Self {
        Self::DeadZone(Circle::new(center, STONE_DIAMETER))
    }

    /// One inset edge of a `board_size` board.
    #[must_use]
    pub const fn boundary(board_size: f64, edge: Edge) -> Self {
        Self::Boundary { board_size, edge }
    }

    /// The circle this shape's outline lies on, for a dead zone.
    #[must_use]
    pub const fn circle(self) -> Option<Circle> {
        match self {
            Self::DeadZone(circle) => Some(circle),
            Self::Boundary { .. } => None,
        }
    }

    /// Whether this shape's outline closes on itself.
    #[must_use]
    pub const fn closure(self) -> Closure {
        match self {
            Self::DeadZone(_) => Closure::Closed,
            Self::Boundary { .. } => Closure::Open,
        }
    }

    /// The point at `offset` along this shape's outline.
    #[must_use]
    pub fn offset_to_point(self, offset: f64) -> Point {
        match self {
            Self::DeadZone(circle) => Point::new(
                circle.center.x + circle.radius * offset.cos(),
                circle.center.y + circle.radius * offset.sin(),
            ),
            Self::Boundary { board_size, edge } => match edge {
                Edge::Left => Point::new(STONE_RADIUS, offset),
                Edge::Bottom => Point::new(offset, board_size - STONE_RADIUS),
                Edge::Right => Point::new(board_size - STONE_RADIUS, board_size - offset),
                Edge::Top => Point::new(board_size - offset, STONE_RADIUS),
            },
        }
    }

    /// The offset of a point lying on this shape's outline. Inverse of
    /// [`ShapeKind::offset_to_point`].
    #[must_use]
    pub fn point_to_offset(self, point: Point) -> f64 {
        match self {
            Self::DeadZone(circle) => {
                normalize_angle((point.y - circle.center.y).atan2(point.x - circle.center.x))
            }
            Self::Boundary { board_size, edge } => match edge {
                Edge::Left => point.y,
                Edge::Bottom => point.x,
                Edge::Right => board_size - point.y,
                Edge::Top => board_size - point.x,
            },
        }
    }

    /// The piece of outline running from `start` to `end`.
    #[must_use]
    pub fn span(self, start: f64, end: f64) -> Span {
        match self {
            Self::DeadZone(circle) => Span::Arc(Arc::new(circle.center, circle.radius, start, end)),
            Self::Boundary { .. } => Span::Line(LineSegment::new(
                self.offset_to_point(start),
                self.offset_to_point(end),
            )),
        }
    }

    /// How far inside this shape `point` lies: positive within it, zero on its
    /// outline, negative outside.
    ///
    /// For a dead zone that is how far short of the rim the point falls; for a
    /// board edge, how far past the inset line it sits. Both are real distances
    /// in board units, which is what lets a caller ask the question with slack
    /// — see [`AliveZone::is_placeable`](crate::AliveZone::is_placeable).
    #[must_use]
    pub fn depth(self, point: Point) -> f64 {
        match self {
            Self::DeadZone(circle) => circle.radius - point.distance(circle.center),
            Self::Boundary { board_size, edge } => match edge {
                Edge::Left => STONE_RADIUS - point.x,
                Edge::Bottom => point.y - (board_size - STONE_RADIUS),
                Edge::Right => point.x - (board_size - STONE_RADIUS),
                Edge::Top => STONE_RADIUS - point.y,
            },
        }
    }

    /// Whether `point` is inside this shape — inside the disc for a dead zone,
    /// off the board for a boundary.
    ///
    /// Exact: a point exactly on the outline is outside. A stone centre at
    /// exactly [`STONE_DIAMETER`] from another's is legal, and the board's inset
    /// edge is the last line a centre may sit on.
    ///
    /// Only the tests ask, and they ask because this is the readable statement
    /// of what [`ShapeKind::depth`]'s sign means. The zone works in depths, so
    /// that one shape's answer composes into every shape's.
    #[cfg(test)]
    #[must_use]
    pub fn contains(self, point: Point) -> bool {
        self.depth(point) > 0.0
    }

    /// Where this shape's outline crosses `other`, or `None` if it does not
    /// properly cross it.
    #[must_use]
    pub fn intersect_circle(self, other: Circle) -> Option<Intersection> {
        match self {
            Self::DeadZone(circle) => intersect_circles(circle, other),
            Self::Boundary { board_size, edge } => intersect_boundary(board_size, edge, other),
        }
    }
}

/// Where two circles cross.
///
/// Tangency and coincidence are **rejected**, not smoothed. This is not a
/// tolerance on identity: at tangency the square root below goes negative and
/// the whole graph fills with NaN, and a pair of circles that touch at one point
/// splits neither into segments worth having. See `docs/design.md`.
fn intersect_circles(this: Circle, other: Circle) -> Option<Intersection> {
    let (r1, r2) = (this.radius, other.radius);
    let d = this.center.distance(other.center);

    // Too far apart to meet, or one nested inside the other.
    if d > r1 + r2 + EPSILON || d < (r1 - r2).abs() - EPSILON {
        return None;
    }
    // Concentric, externally tangent, or internally tangent.
    if d < EPSILON || approx_equal(d, r1 + r2) || approx_equal(d, (r1 - r2).abs()) {
        return None;
    }

    let a = (r1 * r1 - r2 * r2 + d * d) / (2.0 * d);
    let h = (r1 * r1 - a * a).sqrt();

    let dx = other.center.x - this.center.x;
    let dy = other.center.y - this.center.y;
    let foot = Point::new(this.center.x + a * dx / d, this.center.y + a * dy / d);

    let first = Point::new(foot.x + h * dy / d, foot.y - h * dx / d);
    let second = Point::new(foot.x - h * dy / d, foot.y + h * dx / d);

    // Which of the two is the entry depends on which way round the overlapped
    // arc runs. It is always the *shorter* way round, because a stone can never
    // be placed inside another stone's dead zone — so the two discs can never
    // overlap by more than half of either.
    let kind = ShapeKind::DeadZone(this);
    let sweep = (kind.point_to_offset(second) - kind.point_to_offset(first) + TAU) % TAU;
    if sweep < PI {
        Some(Intersection {
            entry: first,
            exit: second,
        })
    } else {
        Some(Intersection {
            entry: second,
            exit: first,
        })
    }
}

/// Where an inset board edge crosses a circle.
///
/// The edge enters the circle on its lower-offset side, which — because the
/// offsets circle the board — is from above on the left edge, from the left on
/// the bottom edge, and the mirror of those on the other two.
fn intersect_boundary(board_size: f64, edge: Edge, other: Circle) -> Option<Intersection> {
    let center = other.center;
    let radius = other.radius;

    match edge {
        Edge::Left | Edge::Right => {
            let x = if matches!(edge, Edge::Left) {
                STONE_RADIUS
            } else {
                board_size - STONE_RADIUS
            };
            let entry_sign = if matches!(edge, Edge::Left) {
                -1.0
            } else {
                1.0
            };

            let discriminant = radius * radius - (x - center.x) * (x - center.x);
            if discriminant <= EPSILON {
                return None;
            }
            let h = discriminant.sqrt();
            Some(Intersection {
                entry: Point::new(x, center.y + entry_sign * h),
                exit: Point::new(x, center.y - entry_sign * h),
            })
        }
        Edge::Bottom | Edge::Top => {
            let y = if matches!(edge, Edge::Bottom) {
                board_size - STONE_RADIUS
            } else {
                STONE_RADIUS
            };
            let entry_sign = if matches!(edge, Edge::Bottom) {
                -1.0
            } else {
                1.0
            };

            let discriminant = radius * radius - (y - center.y) * (y - center.y);
            if discriminant <= EPSILON {
                return None;
            }
            let h = discriminant.sqrt();
            Some(Intersection {
                entry: Point::new(center.x + entry_sign * h, y),
                exit: Point::new(center.x - entry_sign * h, y),
            })
        }
    }
}

/// A shape, together with the segments its outline has been split into.
#[derive(Clone, Debug)]
pub struct Shape {
    /// What the shape is.
    pub(super) kind: ShapeKind,
    /// Whether its segment list wraps.
    pub(super) closure: Closure,
    /// The lowest-offset segment, and the entry point of every walk. `None`
    /// when the outline has not been split at all.
    pub(super) head: Option<SegId>,
    /// How many segments the outline is split into. Every walk over the list is
    /// bounded by this.
    pub(super) count: usize,
}

impl Shape {
    /// A shape with an unsplit outline.
    pub(super) const fn new(kind: ShapeKind) -> Self {
        Self {
            kind,
            closure: kind.closure(),
            head: None,
            count: 0,
        }
    }

    /// What this shape is.
    #[must_use]
    pub const fn kind(&self) -> ShapeKind {
        self.kind
    }

    /// Whether this shape's segment list wraps around.
    #[must_use]
    pub const fn closure(&self) -> Closure {
        self.closure
    }

    /// The lowest-offset segment, if the outline has been split.
    #[must_use]
    pub const fn head(&self) -> Option<SegId> {
        self.head
    }

    /// How many segments the outline is split into.
    #[must_use]
    pub const fn count(&self) -> usize {
        self.count
    }

    /// Whether the outline is split into distinguishable pieces.
    ///
    /// A single segment does not divide an outline into anything — a lone
    /// segment on a closed curve spans the whole curve — so the closest-point
    /// and closest-distance queries treat one segment the same as none and fall
    /// back to the whole shape.
    #[must_use]
    pub const fn is_subdivided(&self) -> bool {
        self.count >= 2
    }
}

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

    use core::f64::consts::{FRAC_PI_2, PI, TAU};

    use super::{Edge, ShapeKind};
    use crate::geometry::{Circle, signed_ring_area};
    use crate::{Point, STONE_DIAMETER, STONE_RADIUS};

    const BOARD: f64 = 20.0;

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

    fn near(actual: f64, expected: f64) {
        assert!(
            (actual - expected).abs() < 1e-9,
            "expected {expected}, got {actual}"
        );
    }

    fn near_point(actual: Point, expected: Point) {
        near(actual.x, expected.x);
        near(actual.y, expected.y);
    }

    #[test]
    fn offsets_and_points_are_inverses_on_every_edge() {
        for edge in Edge::ALL {
            let shape = ShapeKind::boundary(BOARD, edge);
            for offset in [-3.0, 0.0, STONE_RADIUS, 7.25, BOARD - STONE_RADIUS, 41.0] {
                near(shape.point_to_offset(shape.offset_to_point(offset)), offset);
            }
        }
    }

    #[test]
    fn offsets_and_points_are_inverses_on_a_dead_zone() {
        let shape = ShapeKind::dead_zone(p(5.0, 7.0));
        for offset in [0.0, 0.5, PI, 4.0, TAU - 0.001] {
            near(shape.point_to_offset(shape.offset_to_point(offset)), offset);
        }
    }

    #[test]
    fn an_edge_starts_and_ends_at_the_inset_corners() {
        near_point(
            ShapeKind::boundary(BOARD, Edge::Left).offset_to_point(STONE_RADIUS),
            p(1.0, 1.0),
        );
        near_point(
            ShapeKind::boundary(BOARD, Edge::Left).offset_to_point(BOARD - STONE_RADIUS),
            p(1.0, 19.0),
        );
        near_point(
            ShapeKind::boundary(BOARD, Edge::Bottom).offset_to_point(STONE_RADIUS),
            p(1.0, 19.0),
        );
        near_point(
            ShapeKind::boundary(BOARD, Edge::Right).offset_to_point(STONE_RADIUS),
            p(19.0, 19.0),
        );
        near_point(
            ShapeKind::boundary(BOARD, Edge::Top).offset_to_point(STONE_RADIUS),
            p(19.0, 1.0),
        );
        near_point(
            ShapeKind::boundary(BOARD, Edge::Top).offset_to_point(BOARD - STONE_RADIUS),
            p(1.0, 1.0),
        );
    }

    #[test]
    fn board_edges_run_opposite_to_a_dead_zone() {
        // Increasing offset walks the four edges round the board one way, and a
        // dead zone's circumference the other. Both are traced here and their
        // signed areas must come out with opposite signs — that opposition is
        // what makes the board's interior clip like the outside of a disc.
        let corners: Vec<Point> = Edge::ALL
            .into_iter()
            .map(|edge| ShapeKind::boundary(BOARD, edge).offset_to_point(STONE_RADIUS))
            .collect();

        let disc = ShapeKind::dead_zone(p(10.0, 10.0));
        let circumference: Vec<Point> = (0..4)
            .map(|step| disc.offset_to_point(f64::from(step) * FRAC_PI_2))
            .collect();

        let board_winding = signed_ring_area(&corners);
        let disc_winding = signed_ring_area(&circumference);
        assert!(board_winding * disc_winding < 0.0);
    }

    #[test]
    fn a_dead_zone_contains_its_interior_only() {
        let shape = ShapeKind::dead_zone(p(10.0, 10.0));
        assert!(shape.contains(p(10.0, 10.0)));
        assert!(shape.contains(p(11.9, 10.0)));
        assert!(!shape.contains(p(12.0, 10.0)));
        assert!(!shape.contains(p(14.0, 10.0)));
    }

    #[test]
    fn a_boundary_contains_what_is_off_the_board() {
        assert!(ShapeKind::boundary(BOARD, Edge::Left).contains(p(0.5, 10.0)));
        assert!(!ShapeKind::boundary(BOARD, Edge::Left).contains(p(1.5, 10.0)));
        assert!(ShapeKind::boundary(BOARD, Edge::Top).contains(p(10.0, 0.5)));
        assert!(!ShapeKind::boundary(BOARD, Edge::Top).contains(p(10.0, 1.5)));
        assert!(ShapeKind::boundary(BOARD, Edge::Right).contains(p(19.5, 10.0)));
        assert!(!ShapeKind::boundary(BOARD, Edge::Right).contains(p(18.5, 10.0)));
        assert!(ShapeKind::boundary(BOARD, Edge::Bottom).contains(p(10.0, 19.5)));
        assert!(!ShapeKind::boundary(BOARD, Edge::Bottom).contains(p(10.0, 18.5)));
    }

    #[test]
    fn two_overlapping_dead_zones_cross_twice() {
        let left = ShapeKind::dead_zone(p(10.0, 10.0));
        let right = Circle::new(p(12.0, 10.0), STONE_DIAMETER);
        let crossing = left.intersect_circle(right).expect("they overlap");

        // Both crossings are on both circles.
        for point in [crossing.entry, crossing.exit] {
            near(point.distance(p(10.0, 10.0)), STONE_DIAMETER);
            near(point.distance(p(12.0, 10.0)), STONE_DIAMETER);
        }
        assert_ne!(crossing.entry, crossing.exit);
    }

    #[test]
    fn the_overlapped_arc_is_the_shorter_way_round() {
        let disc = ShapeKind::dead_zone(p(10.0, 10.0));
        for offset in [1.0, 2.0, 3.5, 3.9_f64] {
            for angle in [0.0, 1.0, 2.5, 4.0, 5.5_f64] {
                let other = Circle::new(
                    p(10.0 + offset * angle.cos(), 10.0 + offset * angle.sin()),
                    STONE_DIAMETER,
                );
                let crossing = disc.intersect_circle(other).expect("they overlap");
                let entry = disc.point_to_offset(crossing.entry);
                let exit = disc.point_to_offset(crossing.exit);
                let sweep = (exit - entry + TAU) % TAU;
                assert!(sweep < PI, "sweep {sweep} should be the shorter way round");
            }
        }
    }

    #[test]
    fn tangency_and_coincidence_are_rejected() {
        let disc = ShapeKind::dead_zone(p(10.0, 10.0));
        // Externally tangent: the two discs touch at exactly one point.
        assert!(
            disc.intersect_circle(Circle::new(
                p(10.0 + 2.0 * STONE_DIAMETER, 10.0),
                STONE_DIAMETER
            ))
            .is_none()
        );
        // Coincident.
        assert!(
            disc.intersect_circle(Circle::new(p(10.0, 10.0), STONE_DIAMETER))
                .is_none()
        );
        // Internally tangent.
        assert!(
            disc.intersect_circle(Circle::new(p(11.0, 10.0), STONE_DIAMETER + 1.0))
                .is_none()
        );
        // Far apart.
        assert!(
            disc.intersect_circle(Circle::new(p(30.0, 10.0), STONE_DIAMETER))
                .is_none()
        );
        // Nested.
        assert!(
            disc.intersect_circle(Circle::new(p(10.1, 10.0), 10.0))
                .is_none()
        );
    }

    #[test]
    fn an_edge_enters_a_circle_at_the_lower_offset() {
        for edge in Edge::ALL {
            let shape = ShapeKind::boundary(BOARD, edge);
            // A stone sitting right against this edge.
            let center = match edge {
                Edge::Left => p(1.5, 10.0),
                Edge::Bottom => p(10.0, 18.5),
                Edge::Right => p(18.5, 10.0),
                Edge::Top => p(10.0, 1.5),
            };
            let crossing = shape
                .intersect_circle(Circle::new(center, STONE_DIAMETER))
                .expect("the dead zone reaches the edge");

            let entry = shape.point_to_offset(crossing.entry);
            let exit = shape.point_to_offset(crossing.exit);
            assert!(entry < exit, "{edge:?}: entry {entry} exit {exit}");

            // Both crossings are on the edge line and on the circle.
            for point in [crossing.entry, crossing.exit] {
                near(point.distance(center), STONE_DIAMETER);
                near_point(shape.offset_to_point(shape.point_to_offset(point)), point);
            }
        }
    }

    #[test]
    fn an_edge_misses_a_circle_it_does_not_reach() {
        for edge in Edge::ALL {
            let shape = ShapeKind::boundary(BOARD, edge);
            assert!(
                shape
                    .intersect_circle(Circle::new(p(10.0, 10.0), STONE_DIAMETER))
                    .is_none()
            );
        }
    }

    #[test]
    fn an_edge_grazing_a_circle_is_rejected() {
        // Tangent from the inside: the dead zone touches the left edge line at
        // exactly one point.
        let shape = ShapeKind::boundary(BOARD, Edge::Left);
        assert!(
            shape
                .intersect_circle(Circle::new(
                    p(STONE_RADIUS + STONE_DIAMETER, 10.0),
                    STONE_DIAMETER
                ))
                .is_none()
        );
    }

    #[test]
    fn a_span_runs_between_its_two_offsets() {
        let disc = ShapeKind::dead_zone(p(0.0, 0.0));
        let arc = disc.span(0.0, FRAC_PI_2);
        near_point(arc.start_point(), p(STONE_DIAMETER, 0.0));
        near_point(arc.end_point(), p(0.0, STONE_DIAMETER));

        let edge = ShapeKind::boundary(BOARD, Edge::Left);
        let line = edge.span(STONE_RADIUS, BOARD - STONE_RADIUS);
        near_point(line.start_point(), p(1.0, 1.0));
        near_point(line.end_point(), p(1.0, 19.0));
    }
}