{-# LANGUAGE PatternGuards #-}

-- | Geometric functions concerning lines and segments.
--
--   A @Line@ is taken to be infinite in length, while a @Seg@ is finite length
--   line segment represented by its two endpoints.
module Graphics.Gloss.Geometry.Line
        ( segClearsBox

        -- * Closest points
        , closestPointOnLine
        , closestPointOnLineParam

        -- * Line-Line intersection
        , intersectLineLine

        -- * Seg-Line intersection
        , intersectSegLine
        , intersectSegHorzLine
        , intersectSegVertLine

        -- * Seg-Seg intersection
        , intersectSegSeg
        , intersectSegHorzSeg
        , intersectSegVertSeg)

where
import Graphics.Gloss.Data.Point
import Graphics.Gloss.Data.Vector
import qualified Graphics.Gloss.Data.Point.Arithmetic as Pt

-- | Check if line segment (P1-P2) clears a box (P3-P4) by being well outside it.
segClearsBox
        :: Point        -- ^ P1 First point of segment.
        -> Point        -- ^ P2 Second point of segment.
        -> Point        -- ^ P3 Lower left point of box.
        -> Point        -- ^ P4 Upper right point of box.
        -> Bool

segClearsBox (x1, y1) (x2, y2) (xa, ya) (xb, yb)
        | x1 < xa, x2 < xa      = True
        | x1 > xb, x2 > xb      = True
        | y1 < ya, y2 < ya      = True
        | y1 > yb, y2 > yb      = True
        | otherwise             = False


-- | Given an infinite line which intersects `P1` and `P1`,
--      return the point on that line that is closest to `P3`
closestPointOnLine
        :: Point        -- ^ `P1`
        -> Point        -- ^ `P2`
        -> Point        -- ^ `P3`
        -> Point        -- ^ the point on the line P1-P2 that is closest to `P3`

{-# INLINE closestPointOnLine #-}

closestPointOnLine p1 p2 p3
        = p1 Pt.+ (u `mulSV` (p2 Pt.- p1))
        where   u       = closestPointOnLineParam p1 p2 p3


-- | Given an infinite line which intersects P1 and P2,
--      let P4 be the point on the line that is closest to P3.
--
--      Return an indication of where on the line P4 is relative to P1 and P2.
--
-- @
--      if P4 == P1 then 0
--      if P4 == P2 then 1
--      if P4 is halfway between P1 and P2 then 0.5
-- @
--
-- @
--        |
--       P1
--        |
--     P4 +---- P3
--        |
--       P2
--        |
-- @
--
{-# INLINE closestPointOnLineParam #-}
closestPointOnLineParam
        :: Point        -- ^ `P1`
        -> Point        -- ^ `P2`
        -> Point        -- ^ `P3`
        -> Float

closestPointOnLineParam p1 p2 p3
        = (p3 Pt.- p1) `dotV` (p2 Pt.- p1)
        / (p2 Pt.- p1) `dotV` (p2 Pt.- p1)



-- Line-Line intersection -----------------------------------------------------

-- | Given four points specifying two lines, get the point where the two lines
--   cross, if any. Note that the lines extend off to infinity, so the
--   intersection point might not line between either of the two pairs of points.
--
-- @
--     \\      /
--      P1  P4
--       \\ /
--        +
--       / \\
--      P3  P2
--     /     \\
-- @
--
intersectLineLine
        :: Point        -- ^ `P1`
        -> Point        -- ^ `P2`
        -> Point        -- ^ `P3`
        -> Point        -- ^ `P4`
        -> Maybe Point

intersectLineLine (x1, y1) (x2, y2) (x3, y3) (x4, y4)
 = let  dx12    = x1 - x2
        dx34    = x3 - x4

        dy12    = y1 - y2
        dy34    = y3 - y4

        den     = dx12 * dy34  - dy12 * dx34

   in if den == 0
        then Nothing
        else let
                det12   = x1*y2 - y1*x2
                det34   = x3*y4 - y3*x4

                numx    = det12 * dx34 - dx12 * det34
                numy    = det12 * dy34 - dy12 * det34
             in Just (numx / den, numy / den)


-- Segment-Line intersection --------------------------------------------------
-- | Get the point where a segment @P1-P2@ crosses an infinite line @P3-P4@,
--   if any.
--
intersectSegLine
        :: Point        -- ^ `P1`
        -> Point        -- ^ `P2`
        -> Point        -- ^ `P3`
        -> Point        -- ^ `P4`
        -> Maybe Point

intersectSegLine p1 p2 p3 p4
        -- TODO: merge closest point check with intersection, reuse subterms.
        | Just p0       <- intersectLineLine p1 p2 p3 p4
        , t12           <- closestPointOnLineParam p1 p2 p0
        , t12 >= 0 && t12 <= 1
        = Just p0

        | otherwise
        = Nothing


-- | Get the point where a segment crosses a horizontal line, if any.
--
-- @
--                + P1
--               /
--       -------+---------
--             /        y0
--         P2 +
-- @
--
intersectSegHorzLine
        :: Point        -- ^ P1 First point of segment.
        -> Point        -- ^ P2 Second point of segment.
        -> Float        -- ^ y value of line.
        -> Maybe Point
intersectSegHorzLine (x1, y1) (x2, y2) y0

        -- seg is on line
        | y1 == y0, y2 == y0    = Nothing

        -- seg is above line
        | y1 > y0,  y2 > y0     = Nothing

        -- seg is below line
        | y1 < y0,  y2 < y0     = Nothing

        -- seg is a single point on the line.
        -- this should be caught by the first case,
        -- but we'll test for it anyway.
        | y2 - y1 == 0
        = Just (x1, y1)

        | otherwise
        = Just ( (y0 - y1) * (x2 - x1) / (y2 - y1) + x1
               , y0)



-- | Get the point where a segment crosses a vertical line, if any.
--
-- @
--              |
--              |   + P1
--              | /
--              +
--            / |
--       P2 +   |
--              | x0
-- @
--
intersectSegVertLine
        :: Point        -- ^ P1 First point of segment.
        -> Point        -- ^ P2 Second point of segment.
        -> Float        -- ^ x value of line.
        -> Maybe Point

intersectSegVertLine (x1, y1) (x2, y2) x0

        -- seg is on line
        | x1 == x0, x2 == x0    = Nothing

        -- seg is to right of line
        | x1 > x0,  x2 > x0     = Nothing

        -- seg is to left of line
        | x1 < x0,  x2 < x0     = Nothing

        -- seg is a single point on the line.
        -- this should be caught by the first case,
        -- but we'll test for it anyway.
        | x2 - x1 == 0
        = Just (x1, y1)

        | otherwise
        = Just (  x0
               , (x0 - x1) * (y2 - y1) / (x2 - x1) + y1)


-- Segment-Segment intersection -----------------------------------------------

-- | Get the point where a segment @P1-P2@ crosses another segement @P3-P4@,
--   if any.
intersectSegSeg
        :: Point        -- ^ `P1`
        -> Point        -- ^ `P2`
        -> Point        -- ^ `P3`
        -> Point        -- ^ `P4`
        -> Maybe Point

intersectSegSeg p1 p2 p3 p4
        -- TODO: merge closest point checks with intersection, reuse subterms.
        | Just p0       <- intersectLineLine p1 p2 p3 p4
        , t12           <- closestPointOnLineParam p1 p2 p0
        , t23           <- closestPointOnLineParam p3 p4 p0
        , t12 >= 0 && t12 <= 1
        , t23 >= 0 && t23 <= 1
        = Just p0

        | otherwise
        = Nothing


-- | Check if an arbitrary segment intersects a horizontal segment.
--
-- @
--                 + P2
--                /
-- (xa, y3)  +---+----+ (xb, y3)
--              /
--          P1 +
-- @

intersectSegHorzSeg
        :: Point        -- ^ P1 First point of segment.
        -> Point        -- ^ P2 Second point of segment.
        -> Float        -- ^ (y3) y value of horizontal segment.
        -> Float        -- ^ (xa) Leftmost x value of horizontal segment.
        -> Float        -- ^ (xb) Rightmost x value of horizontal segment.
        -> Maybe Point  -- ^ (x3, y3) Intersection point, if any.

intersectSegHorzSeg p1@(x1, y1) p2@(x2, y2) y0 xa xb
        | segClearsBox p1 p2 (xa, y0) (xb, y0)
        = Nothing

        | x0 < xa       = Nothing
        | x0 > xb       = Nothing
        | otherwise     = Just (x0, y0)

        where x0 | (y2 - y1) == 0 = x1
                 | otherwise      = (y0 - y1) * (x2 - x1) / (y2 - y1) + x1


-- | Check if an arbitrary segment intersects a vertical segment.
--
-- @
--      (x3, yb) +
--               |   + P1
--               | /
--               +
--             / |
--        P2 +   |
--               + (x3, ya)
-- @

intersectSegVertSeg
        :: Point        -- ^ P1 First point of segment.
        -> Point        -- ^ P2 Second point of segment.
        -> Float        -- ^ (x3) x value of vertical segment
        -> Float        -- ^ (ya) Lowest y value of vertical segment.
        -> Float        -- ^ (yb) Highest y value of vertical segment.
        -> Maybe Point  -- ^ (x3, y3) Intersection point, if any.

intersectSegVertSeg p1@(x1, y1) p2@(x2, y2) x0 ya yb
        | segClearsBox p1 p2 (x0, ya) (x0, yb)
        = Nothing

        | y0 < ya       = Nothing
        | y0 > yb       = Nothing
        | otherwise     = Just (x0, y0)

        where y0 | (x2 - x1) == 0 = y1
                 | otherwise      = (x0 - x1) * (y2 - y1) / (x2 - x1) + y1