content: {-# 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 Brillo.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 Brillo.Data.Point
  import Brillo.Data.Point.Arithmetic qualified as Pt
  import Brillo.Data.Vector
  
  
  -- | Check if line segment (P1-P2) clears a box (P3-P4) by being well outside it.
  segClearsBox ::
    -- | 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.
    Point ->
    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 ::
    -- | `P1`
    Point ->
    -- | `P2`
    Point ->
    -- | `P3`
    Point ->
    -- | the point on the line P1-P2 that is closest to `P3`
    Point
  {-# 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 ::
    -- | `P1`
    Point ->
    -- | `P2`
    Point ->
    -- | `P3`
    Point ->
    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 ::
    -- | `P1`
    Point ->
    -- | `P2`
    Point ->
    -- | `P3`
    Point ->
    -- | `P4`
    Point ->
    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 ::
    -- | `P1`
    Point ->
    -- | `P2`
    Point ->
    -- | `P3`
    Point ->
    -- | `P4`
    Point ->
    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 ::
    -- | P1 First point of segment.
    Point ->
    -- | P2 Second point of segment.
    Point ->
    -- | y value of line.
    Float ->
    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 ::
    -- | P1 First point of segment.
    Point ->
    -- | P2 Second point of segment.
    Point ->
    -- | x value of line.
    Float ->
    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 ::
    -- | `P1`
    Point ->
    -- | `P2`
    Point ->
    -- | `P3`
    Point ->
    -- | `P4`
    Point ->
    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 ::
    -- | P1 First point of segment.
    Point ->
    -- | P2 Second point of segment.
    Point ->
    -- | (y3) y value of horizontal segment.
    Float ->
    -- | (xa) Leftmost x value of horizontal segment.
    Float ->
    -- | (xb) Rightmost x value of horizontal segment.
    Float ->
    -- | (x3, y3) Intersection point, if any.
    Maybe Point
  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 ::
    -- | P1 First point of segment.
    Point ->
    -- | P2 Second point of segment.
    Point ->
    -- | (x3) x value of vertical segment
    Float ->
    -- | (ya) Lowest y value of vertical segment.
    Float ->
    -- | (yb) Highest y value of vertical segment.
    Float ->
    -- | (x3, y3) Intersection point, if any.
    Maybe Point
  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
  