klyff_msdf 0.1.3

use glam::Vec2;

use super::EPS;
use crate::{math_curve::cross, math_segment::unsigned_dist_point_to_segment_sqr};

#[derive(Debug)]
pub(super) enum SegmentIntersection {
    /// Lines are parallel, do nothing.
    Parallel,
    /// Colinear
    Colinear,
    /// Not parallel but segments are too short to meet. Returns closest distance measure for other
    /// calculations.
    NonIntersecting { closest_distance_sqr: f32 },
    /// Split seg1 and seg2, and defer validation check until later.
    Intersect { s1_t: f32, s2_t: f32, pos: Vec2 },
}

/// Tests if two segments intersect. The intersection point must not be the start or end point of
/// at least one segment (i.e T junction and X junctions counts as intersecting, but V junction does not)
pub(super) fn segment_intersection(
    s1_from: Vec2,
    s1_to: Vec2,
    s2_from: Vec2,
    s2_to: Vec2,
) -> SegmentIntersection {
    let p = s1_from;
    let r = s1_to - s1_from;
    let q = s2_from;
    let s = s2_to - s2_from;

    let rxs = cross(r, s);
    let q_p = q - p;

    // EPS alone is too strict.
    if rxs.abs() < 0.1 {
        if cross(q_p, r).abs() >= EPS {
            return SegmentIntersection::Parallel;
        } else {
            return SegmentIntersection::Colinear;
        }
    }

    let t = cross(q_p, s) / rxs;
    let u = cross(q_p, r) / rxs;

    let interval = 0.0..=1.0;
    let exclude_endpoint = EPS..=1.0 - EPS;

    if interval.contains(&t)
        && interval.contains(&u)
        && (exclude_endpoint.contains(&t) || exclude_endpoint.contains(&u))
    {
        SegmentIntersection::Intersect {
            s1_t: t,
            s2_t: u,
            pos: p + r * t,
        }
    } else {
        let distance = unsigned_dist_point_to_segment_sqr(s1_from, s2_from, s2_to)
            .min(unsigned_dist_point_to_segment_sqr(s1_to, s2_from, s2_to));
        SegmentIntersection::NonIntersecting {
            closest_distance_sqr: distance,
        }
    }
}

#[cfg(test)]
mod test {
    use glam::vec2;

    #[test]
    fn should_not_intersect() {
        let intersect = super::segment_intersection(
            vec2(-266.3527, 4449.188),
            vec2(-185.5053, 4421.2437),
            vec2(-184.95523, 421.05334),
            vec2(-93.31085, 389.377),
        );
        assert!(
            !matches!(
                intersect,
                crate::polygon_clipping::intersection::SegmentIntersection::Intersect { .. }
            ),
            "{intersect:?}"
        );
    }

    #[test]
    fn should_intersect_t_junction() {
        let intersect = super::segment_intersection(
            vec2(0.0, 0.0),
            vec2(10.0, 10.0),
            vec2(2.0, 2.0),
            vec2(8.0, -8.0),
        );
        assert!(
            matches!(
                intersect,
                crate::polygon_clipping::intersection::SegmentIntersection::Intersect { .. }
            ),
            "{intersect:?}"
        );
    }

    #[test]
    fn should_intersect_x_junction() {
        let intersect = super::segment_intersection(
            vec2(0.0, 0.0),
            vec2(10.0, 10.0),
            vec2(0.0, 10.0),
            vec2(10.0, 0.0),
        );
        assert!(
            matches!(
                intersect,
                crate::polygon_clipping::intersection::SegmentIntersection::Intersect { .. }
            ),
            "{intersect:?}"
        );
    }

    #[test]
    fn should_not_intersect_v_junction() {
        let intersect = super::segment_intersection(
            vec2(0.0, 0.0),
            vec2(10.0, 10.0),
            vec2(0.0, 0.0),
            vec2(8.0, 6.0),
        );
        assert!(
            !matches!(
                intersect,
                crate::polygon_clipping::intersection::SegmentIntersection::Intersect { .. }
            ),
            "{intersect:?}"
        );
    }
}