voronoi-go 1.0.1

//! Line segments, circles and arcs, with the closest-point and closest-distance
//! queries the alive zone is built out of.

use core::f64::consts::TAU;

use crate::Point;

use super::segments_intersect;

/// Reduces an angle in radians to `[0, TAU)`.
#[must_use]
pub fn normalize_angle(angle: f64) -> f64 {
    let normalized = angle % TAU;
    if normalized < 0.0 {
        normalized + TAU
    } else {
        normalized
    }
}

/// Whether `angle` falls in the span swept from `start` to `end` going
/// anticlockwise. All three must already be normalized to `[0, TAU)`; a span
/// that crosses zero is handled.
fn angle_in_span(angle: f64, start: f64, end: f64) -> bool {
    if start <= end {
        angle >= start && angle <= end
    } else {
        angle >= start || angle <= end
    }
}

/// A straight segment between two points.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct LineSegment {
    /// One end.
    pub a: Point,
    /// The other end.
    pub b: Point,
}

impl LineSegment {
    /// The segment from `a` to `b`.
    #[must_use]
    pub const fn new(a: Point, b: Point) -> Self {
        Self { a, b }
    }

    /// The point of this segment closest to `p`.
    ///
    /// A degenerate segment — both ends the same point — has no direction to
    /// project onto, and answers with its start.
    #[must_use]
    pub fn closest_point(self, p: Point) -> Point {
        let dx = self.b.x - self.a.x;
        let dy = self.b.y - self.a.y;
        let length_squared = dx * dx + dy * dy;

        // A magnitude test, not an identity test: this asks whether the segment
        // has any length at all, and only exact zero makes the division below
        // undefined.
        #[allow(clippy::float_cmp)]
        if length_squared == 0.0 {
            return self.a;
        }

        let t = (((p.x - self.a.x) * dx + (p.y - self.a.y) * dy) / length_squared).clamp(0.0, 1.0);
        Point::new(self.a.x + t * dx, self.a.y + t * dy)
    }

    /// The minimum distance between two segments, `0.0` when they properly
    /// cross.
    ///
    /// Because the crossing test is strict (see [`segments_intersect`]),
    /// segments that merely touch fall through to the endpoint sweep, which
    /// gives `0.0` for them as well.
    #[must_use]
    pub fn distance_to(self, other: Self) -> f64 {
        if segments_intersect(self, other) {
            return 0.0;
        }

        let from_a = self.a.distance(other.closest_point(self.a));
        let from_b = self.b.distance(other.closest_point(self.b));
        let to_a = other.a.distance(self.closest_point(other.a));
        let to_b = other.b.distance(self.closest_point(other.b));

        from_a.min(from_b).min(to_a).min(to_b)
    }
}

/// A full circle.
#[derive(Clone, Copy, Debug)]
pub struct Circle {
    /// Centre.
    pub center: Point,
    /// Radius.
    pub radius: f64,
}

impl Circle {
    /// The circle of radius `radius` about `center`.
    #[must_use]
    pub const fn new(center: Point, radius: f64) -> Self {
        Self { center, radius }
    }

    /// The point of the circle's boundary closest to `p`.
    ///
    /// Every boundary point is equidistant from the centre, so a `p` at the
    /// centre answers with the point at angle zero.
    #[must_use]
    pub fn closest_point(self, p: Point) -> Point {
        let dx = p.x - self.center.x;
        let dy = p.y - self.center.y;
        let dist = (dx * dx + dy * dy).sqrt();

        // A magnitude test, not an identity test: only exact zero leaves no
        // direction from the centre towards `p`.
        #[allow(clippy::float_cmp)]
        if dist == 0.0 {
            return Point::new(self.center.x + self.radius, self.center.y);
        }

        let scale = self.radius / dist;
        Point::new(self.center.x + dx * scale, self.center.y + dy * scale)
    }

    /// The minimum distance from `segment` to this circle's **boundary**, and
    /// `0.0` when the segment crosses it.
    ///
    /// A segment wholly inside the disc is not distance zero: it answers with
    /// its distance to the boundary from within.
    #[must_use]
    pub fn distance_to_segment(self, segment: LineSegment) -> f64 {
        let dist_a = self.center.distance(segment.a);
        let dist_b = self.center.distance(segment.b);

        match (dist_a < self.radius, dist_b < self.radius) {
            // One end in, one end out: the segment crosses the boundary.
            (true, false) | (false, true) => 0.0,
            // Both ends outside: the segment still crosses if it dips inside.
            (false, false) => {
                let closest = segment.closest_point(self.center);
                let dist = self.center.distance(closest);
                if dist < self.radius {
                    0.0
                } else {
                    dist - self.radius
                }
            }
            // Both ends inside: the nearest boundary is beyond the further end.
            (true, true) => self.radius - dist_a.max(dist_b),
        }
    }
}

/// An arc of a circle, swept anticlockwise from `start_angle` to `end_angle`.
#[derive(Clone, Copy, Debug)]
pub struct Arc {
    /// Centre of the circle the arc lies on.
    pub center: Point,
    /// Radius of that circle.
    pub radius: f64,
    /// Angle, in radians, where the arc starts.
    pub start_angle: f64,
    /// Angle, in radians, where the arc ends.
    pub end_angle: f64,
}

impl Arc {
    /// The arc of `radius` about `center` from `start_angle` to `end_angle`.
    #[must_use]
    pub const fn new(center: Point, radius: f64, start_angle: f64, end_angle: f64) -> Self {
        Self {
            center,
            radius,
            start_angle,
            end_angle,
        }
    }

    /// The circle this arc lies on.
    #[must_use]
    pub const fn circle(self) -> Circle {
        Circle::new(self.center, self.radius)
    }

    /// The point at `angle` on this arc's circle.
    #[must_use]
    pub fn point_at(self, angle: f64) -> Point {
        Point::new(
            self.center.x + self.radius * angle.cos(),
            self.center.y + self.radius * angle.sin(),
        )
    }

    /// Where the arc begins.
    #[must_use]
    pub fn start_point(self) -> Point {
        self.point_at(self.start_angle)
    }

    /// Where the arc ends.
    #[must_use]
    pub fn end_point(self) -> Point {
        self.point_at(self.end_angle)
    }

    /// Whether `angle`, given in radians in any range, lies within the arc's
    /// span.
    #[must_use]
    pub fn contains_angle(self, angle: f64) -> bool {
        angle_in_span(
            normalize_angle(angle),
            normalize_angle(self.start_angle),
            normalize_angle(self.end_angle),
        )
    }

    /// The point of the arc closest to `p`.
    ///
    /// If `p` bears on the arc's span, that is the radial projection; otherwise
    /// it is whichever end is angularly nearer.
    #[must_use]
    pub fn closest_point(self, p: Point) -> Point {
        let angle_to_point = normalize_angle((p.y - self.center.y).atan2(p.x - self.center.x));
        let start = normalize_angle(self.start_angle);
        let end = normalize_angle(self.end_angle);

        let closest_angle = if angle_in_span(angle_to_point, start, end) {
            angle_to_point
        } else {
            let to_start = (angle_to_point - start).abs();
            let to_start = to_start.min(TAU - to_start);
            let to_end = (angle_to_point - end).abs();
            let to_end = to_end.min(TAU - to_end);
            if to_start < to_end { start } else { end }
        };

        self.point_at(closest_angle)
    }

    /// The minimum distance between `segment` and this arc.
    ///
    /// Four candidates: each segment end projected onto the arc, each arc end
    /// projected onto the segment, and — when the segment's nearest approach to
    /// the centre bears on the arc's span — that approach's radial offset.
    #[must_use]
    pub fn distance_to_segment(self, segment: LineSegment) -> f64 {
        let from_a = segment.a.distance(self.closest_point(segment.a));
        let from_b = segment.b.distance(self.closest_point(segment.b));
        let mut minimum = from_a.min(from_b);

        let arc_start = self.start_point();
        minimum = minimum.min(arc_start.distance(segment.closest_point(arc_start)));

        let arc_end = self.end_point();
        minimum = minimum.min(arc_end.distance(segment.closest_point(arc_end)));

        let closest_to_center = segment.closest_point(self.center);
        let bearing =
            (closest_to_center.y - self.center.y).atan2(closest_to_center.x - self.center.x);
        if self.contains_angle(bearing) {
            let dist_to_center = self.center.distance(closest_to_center);
            minimum = minimum.min((dist_to_center - self.radius).abs());
        }

        minimum
    }
}

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

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

    use super::{Arc, Circle, LineSegment, normalize_angle};
    use crate::Point;

    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))
    }

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

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

    #[test]
    fn normalize_angle_lands_in_one_turn() {
        near(normalize_angle(0.0), 0.0);
        near(normalize_angle(-FRAC_PI_2), TAU - FRAC_PI_2);
        near(normalize_angle(TAU + 1.0), 1.0);
        assert!(normalize_angle(-1e-9) < TAU);
    }

    #[test]
    fn closest_point_on_segment_projects_and_clamps() {
        let segment = seg(0.0, 0.0, 10.0, 0.0);
        near_point(segment.closest_point(p(5.0, 3.0)), p(5.0, 0.0));
        near_point(segment.closest_point(p(-4.0, 3.0)), p(0.0, 0.0));
        near_point(segment.closest_point(p(40.0, 3.0)), p(10.0, 0.0));
    }

    #[test]
    fn a_degenerate_segment_answers_with_its_start() {
        let segment = seg(2.0, 2.0, 2.0, 2.0);
        near_point(segment.closest_point(p(9.0, 9.0)), p(2.0, 2.0));
    }

    #[test]
    fn crossing_segments_are_zero_apart() {
        near(
            seg(-1.0, 0.0, 1.0, 0.0).distance_to(seg(0.0, -1.0, 0.0, 1.0)),
            0.0,
        );
    }

    #[test]
    fn touching_segments_are_zero_apart_via_the_endpoint_sweep() {
        // `segments_intersect` is strict, so this does not short circuit — the
        // endpoint sweep has to find the zero on its own.
        near(
            seg(0.0, 0.0, 1.0, 0.0).distance_to(seg(1.0, 0.0, 2.0, 0.0)),
            0.0,
        );
    }

    #[test]
    fn parallel_segments_are_their_offset_apart() {
        near(
            seg(0.0, 0.0, 1.0, 0.0).distance_to(seg(0.0, 3.0, 1.0, 3.0)),
            3.0,
        );
    }

    #[test]
    fn closest_point_on_circle_projects_radially() {
        let circle = Circle::new(p(0.0, 0.0), 2.0);
        near_point(circle.closest_point(p(5.0, 0.0)), p(2.0, 0.0));
        near_point(circle.closest_point(p(0.5, 0.0)), p(2.0, 0.0));
    }

    #[test]
    fn a_point_at_the_centre_answers_with_angle_zero() {
        let circle = Circle::new(p(3.0, 4.0), 2.0);
        near_point(circle.closest_point(p(3.0, 4.0)), p(5.0, 4.0));
    }

    #[test]
    fn circle_to_segment_covers_all_three_cases() {
        let circle = Circle::new(p(0.0, 0.0), 2.0);
        // One end in, one out.
        near(circle.distance_to_segment(seg(0.0, 0.0, 5.0, 0.0)), 0.0);
        // Both out, but the chord dips inside.
        near(circle.distance_to_segment(seg(-5.0, 1.0, 5.0, 1.0)), 0.0);
        // Both out, entirely clear.
        near(circle.distance_to_segment(seg(-5.0, 5.0, 5.0, 5.0)), 3.0);
        // Both in: distance to the boundary from within.
        near(circle.distance_to_segment(seg(-0.5, 0.0, 0.5, 0.0)), 1.5);
    }

    #[test]
    fn closest_point_on_arc_projects_within_the_span() {
        let arc = Arc::new(p(0.0, 0.0), 1.0, 0.0, FRAC_PI_2);
        near_point(
            arc.closest_point(p(5.0, 5.0)),
            p(0.5_f64.sqrt(), 0.5_f64.sqrt()),
        );
    }

    #[test]
    fn closest_point_on_arc_falls_back_to_the_nearer_end() {
        let arc = Arc::new(p(0.0, 0.0), 1.0, 0.0, FRAC_PI_2);
        near_point(arc.closest_point(p(5.0, -5.0)), p(1.0, 0.0));
        near_point(arc.closest_point(p(-5.0, 5.0)), p(0.0, 1.0));
    }

    #[test]
    fn an_arc_span_may_cross_zero() {
        let arc = Arc::new(p(0.0, 0.0), 1.0, 3.0 * FRAC_PI_2, FRAC_PI_2);
        assert!(arc.contains_angle(0.0));
        assert!(arc.contains_angle(-0.5));
        assert!(!arc.contains_angle(PI));
        near_point(arc.closest_point(p(5.0, 0.0)), p(1.0, 0.0));
    }

    #[test]
    fn arc_to_segment_finds_the_radial_approach() {
        let arc = Arc::new(p(0.0, 0.0), 1.0, 0.0, PI);
        near(arc.distance_to_segment(seg(-5.0, 4.0, 5.0, 4.0)), 3.0);
    }

    #[test]
    fn arc_to_segment_ignores_the_circle_outside_the_span() {
        // The segment is 3 away from the lower half of the circle, but that
        // half is not part of the arc: the nearest arc point is an endpoint.
        let arc = Arc::new(p(0.0, 0.0), 1.0, 0.0, PI);
        let distance = arc.distance_to_segment(seg(-5.0, -4.0, 5.0, -4.0));
        near(distance, 4.0);
    }

    #[test]
    fn arc_touching_a_segment_is_zero() {
        let arc = Arc::new(p(0.0, 0.0), 1.0, 0.0, PI);
        near(arc.distance_to_segment(seg(1.0, -1.0, 1.0, 1.0)), 0.0);
    }

    #[test]
    fn arc_to_segment_measures_candidates_not_crossings() {
        // A chord crossing the arc's interior is not detected as a crossing:
        // the metric is the minimum over the five candidate pairs, and for this
        // chord that minimum is the radial approach. The distance-to-a-circle
        // query is the one that reports crossings; this one is a sweep of
        // nearest approaches and is used where that is what is wanted.
        let arc = Arc::new(p(0.0, 0.0), 1.0, 0.0, PI);
        near(arc.distance_to_segment(seg(-5.0, 0.5, 5.0, 0.5)), 0.5);
    }
}