use super::{Rect, Vec2};
use alga::general::{ClosedDiv, ClosedMul, ClosedSub};
use nalgebra::{RealField, Scalar};
use num_traits::Zero;

#[derive(Debug)]
pub struct LineSegment<T: Scalar + Copy> {
    pub start: Vec2<T>,
    pub end: Vec2<T>,
}

impl<T: Scalar + Copy> LineSegment<T> {
    pub fn new(start: Vec2<T>, end: Vec2<T>) -> Self {
        Self { start, end }
    }

    /* Helper function to check if this line contains a point. This function is very efficient, but
     * must only be used for points that are collinear with the segment. This is checked only by
     * assertion, so make sure that everything is ok in release mode.
     */
    pub(crate) fn contains_collinear(&self, point: Vec2<T>) -> bool
    where
        T: PartialOrd,
    {
        point.x <= super::partial_max(self.start.x, self.end.x)
            && point.x >= super::partial_max(self.start.x, self.end.x)
            && point.y <= super::partial_min(self.start.y, self.end.y)
            && point.y >= super::partial_min(self.start.y, self.end.y)
    }

    /// Checks if two segments intersect. This is much more efficient than trying to find the exact
    /// point of intersection, so it should be used if it is not strictly necessary to know it.
    pub fn intersect(ls1: &LineSegment<T>, ls2: &LineSegment<T>) -> bool
    where
        T: Scalar + Copy + ClosedSub + ClosedMul + PartialOrd + Zero,
    {
        /* This algorithm works by checking the triplet orientation of the first lines points with the
         * first point of the second line. After that it does the same for the second point of the
         * second line. If the orientations are different, that must mean the second line starts
         * "before" the first line and ends "after" it. It does the same, but with the roles of first
         * and second line reversed. If both of these conditions are met, it follows that the lines
         * must have crossed.
         *
         * Edge case: If an orientation comes out as collinear, the point of the other line that was
         * checked may be on the other line or after/before it (if you extend the segment). If it is on
         * the other line, this also means, the lines cross, since one line "stands" on the other.
         * If however none of the collinear cases are like this, the lines cannot touch, because line
         * segment a point was collinear with was not long enough.
         */

        // Cache the necessary orientations.
        let ls1_ls2start_orientation = triplet_orientation(ls1.start, ls1.end, ls2.start);
        let ls1_ls2end_orientation = triplet_orientation(ls1.start, ls1.end, ls2.end);
        let ls2_ls1start_orientation = triplet_orientation(ls2.start, ls2.end, ls1.start);
        let ls2_ls1end_orientation = triplet_orientation(ls2.start, ls2.end, ls1.end);

        // Check for the first case that wase described (general case).
        if ls1_ls2start_orientation != ls1_ls2end_orientation
            && ls2_ls1start_orientation != ls2_ls1end_orientation
        {
            return true;
        }

        // Check if the start of ls2 lies on ls1
        if ls1_ls2start_orientation == TripletOrientation::Collinear
            && ls1.contains_collinear(ls2.start)
        {
            return true;
        }
        // Check if the end of ls2 lies on ls1
        if ls1_ls2end_orientation == TripletOrientation::Collinear
            && ls1.contains_collinear(ls2.end)
        {
            return true;
        }

        // Check if the start of ls1 lies on ls2
        if ls2_ls1start_orientation == TripletOrientation::Collinear
            && ls2.contains_collinear(ls1.start)
        {
            return true;
        }
        // Check if the end of ls1 lies on ls2
        if ls2_ls1end_orientation == TripletOrientation::Collinear
            && ls2.contains_collinear(ls1.end)
        {
            return true;
        }

        false
    }

    pub fn intersection(line_a: &LineSegment<T>, line_b: &LineSegment<T>) -> Option<Vec2<T>>
    where
        T: ClosedSub + ClosedMul + ClosedDiv + Zero + RealField,
    {
        // Calculate the differences of each line value from starting point to end point
        // coordinate.
        let dax = line_a.end.x - line_a.start.x;
        let dbx = line_b.end.x - line_b.start.x;
        let day = line_a.end.y - line_a.start.y;
        let dby = line_b.end.y - line_b.start.y;

        // Calculate determinant to see, if the lines are parallel or not
        // TODO: Collinearity check?
        let d = (dax * dby) - (day * dbx);
        if d == T::zero() {
            None
        } else {
            let ad = (line_a.start.x * line_a.end.y) - (line_a.start.y * line_a.end.x);
            let bd = (line_b.start.x * line_b.end.y) - (line_b.start.y * line_b.end.x);

            let out = Vec2::new(((ad * dbx) - (dax * bd)) / d, ((ad * dby) - (day * bd)) / d);

            /* Since the line intersection, not the line segment intersection is calculated, a
             * bounding check is necessary, to see if the intersection still lies inside both of
             * the segments. We know it's on the lines, so checking with the lines bounding box is
             * faster than checking where on the line exactly it would be.
             */
            if Rect::bounding_rect(line_a.start, line_a.end).contains(out)
                && Rect::bounding_rect(line_b.start, line_b.end).contains(out)
            {
                Some(out)
            } else {
                None
            }
        }
    }
}

#[derive(PartialEq, Eq)]
pub(crate) enum TripletOrientation {
    Clockwise,
    Counterclockwise,
    Collinear,
}

/// Helper function to determine which direction one would turn to traverse from the first point
/// over the second to the third point. The third option is collinear, in which case the three points
/// are on the same line.
pub(crate) fn triplet_orientation<T>(a: Vec2<T>, b: Vec2<T>, c: Vec2<T>) -> TripletOrientation
where
    T: Scalar + Copy + ClosedSub + ClosedMul + PartialOrd + Zero,
{
    /* Check the slopes of the vector from a to b and b to c. If the slope of ab is greater than
     * that of bc, the rotation is clockwise. If ab is smaller than bc it's counterclockwise. If
     * they are the same it follows that the three points are collinear.
     */
    match (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y) {
        q if q > T::zero() => TripletOrientation::Clockwise,
        q if q < T::zero() => TripletOrientation::Counterclockwise,
        _ => TripletOrientation::Collinear,
    }
}