Line.hs

{-# 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