{- |
  This module provides the 'BBox2' type for 2-dimensional bounding boxes.
-}

module Data.BoundingBox.B2 where

import Data.Vector.Class
import Data.Vector.V2
import qualified Data.BoundingBox.Range as R

-- | A 'BBox2' is a 2D bounding box (aligned to the coordinate axies).
data BBox2 = BBox2 {BBox2 -> Scalar
minX, BBox2 -> Scalar
minY, BBox2 -> Scalar
maxX, BBox2 -> Scalar
maxY :: {-# UNPACK #-} !Scalar} deriving (BBox2 -> BBox2 -> Bool
(BBox2 -> BBox2 -> Bool) -> (BBox2 -> BBox2 -> Bool) -> Eq BBox2
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: BBox2 -> BBox2 -> Bool
== :: BBox2 -> BBox2 -> Bool
$c/= :: BBox2 -> BBox2 -> Bool
/= :: BBox2 -> BBox2 -> Bool
Eq, Int -> BBox2 -> ShowS
[BBox2] -> ShowS
BBox2 -> String
(Int -> BBox2 -> ShowS)
-> (BBox2 -> String) -> ([BBox2] -> ShowS) -> Show BBox2
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: Int -> BBox2 -> ShowS
showsPrec :: Int -> BBox2 -> ShowS
$cshow :: BBox2 -> String
show :: BBox2 -> String
$cshowList :: [BBox2] -> ShowS
showList :: [BBox2] -> ShowS
Show)

-- | Return the X-range that this bounding box covers.
rangeX :: BBox2 -> R.Range
rangeX :: BBox2 -> Range
rangeX BBox2
b = Scalar -> Scalar -> Range
R.Range (BBox2 -> Scalar
minX BBox2
b) (BBox2 -> Scalar
maxX BBox2
b)

-- | Return the Y-range that this bounding box covers.
rangeY :: BBox2 -> R.Range
rangeY :: BBox2 -> Range
rangeY BBox2
b = Scalar -> Scalar -> Range
R.Range (BBox2 -> Scalar
minY BBox2
b) (BBox2 -> Scalar
maxY BBox2
b)

-- | Given ranges for each coordinate axis, construct a bounding box.
rangeXY :: R.Range -> R.Range -> BBox2
rangeXY :: Range -> Range -> BBox2
rangeXY (R.Range Scalar
x0 Scalar
x1) (R.Range Scalar
y0 Scalar
y1) = Scalar -> Scalar -> Scalar -> Scalar -> BBox2
BBox2 Scalar
x0 Scalar
y0 Scalar
x1 Scalar
y1

-- | Given a pair of corner points, construct a bounding box. (The points must be from opposite corners, but it doesn't matter /which/ corners nor which order they are given in.)
bound_corners :: Vector2 -> Vector2 -> BBox2
bound_corners :: Vector2 -> Vector2 -> BBox2
bound_corners (Vector2 Scalar
xa Scalar
ya) (Vector2 Scalar
xb Scalar
yb) = Scalar -> Scalar -> Scalar -> Scalar -> BBox2
BBox2 (Scalar -> Scalar -> Scalar
forall a. Ord a => a -> a -> a
min Scalar
xa Scalar
xb) (Scalar -> Scalar -> Scalar
forall a. Ord a => a -> a -> a
min Scalar
ya Scalar
yb) (Scalar -> Scalar -> Scalar
forall a. Ord a => a -> a -> a
max Scalar
xa Scalar
xb) (Scalar -> Scalar -> Scalar
forall a. Ord a => a -> a -> a
max Scalar
ya Scalar
yb)

-- | Find the bounds of a list of points. (Throws an exception if the list is empty.)
bound_points :: [Vector2] -> BBox2
bound_points :: [Vector2] -> BBox2
bound_points [Vector2]
ps =
  let
    xs :: [Scalar]
xs = (Vector2 -> Scalar) -> [Vector2] -> [Scalar]
forall a b. (a -> b) -> [a] -> [b]
map Vector2 -> Scalar
v2x [Vector2]
ps
    ys :: [Scalar]
ys = (Vector2 -> Scalar) -> [Vector2] -> [Scalar]
forall a b. (a -> b) -> [a] -> [b]
map Vector2 -> Scalar
v2y [Vector2]
ps
  in Scalar -> Scalar -> Scalar -> Scalar -> BBox2
BBox2 ([Scalar] -> Scalar
forall a. Ord a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
minimum [Scalar]
xs) ([Scalar] -> Scalar
forall a. Ord a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
minimum [Scalar]
ys) ([Scalar] -> Scalar
forall a. Ord a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
maximum [Scalar]
xs) ([Scalar] -> Scalar
forall a. Ord a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
maximum [Scalar]
ys)

-- | Test whether a given 2D vector is inside this bounding box.
within_bounds :: Vector2 -> BBox2 -> Bool
within_bounds :: Vector2 -> BBox2 -> Bool
within_bounds (Vector2 Scalar
x Scalar
y) BBox2
b =
  Scalar
x Scalar -> Range -> Bool
`R.within_bounds` (BBox2 -> Range
rangeX BBox2
b) Bool -> Bool -> Bool
&&
  Scalar
y Scalar -> Range -> Bool
`R.within_bounds` (BBox2 -> Range
rangeY BBox2
b)

-- | Return the minimum values for both coordinates. (In usual 2D space, the bottom-left corner point.)
min_point :: BBox2 -> Vector2
min_point :: BBox2 -> Vector2
min_point (BBox2 Scalar
x0 Scalar
y0 Scalar
x1 Scalar
y1) = Scalar -> Scalar -> Vector2
Vector2 Scalar
x0 Scalar
y0

-- | Return the maximum values for both coordinates. (In usual 2D space, the top-right corner point.)
max_point :: BBox2 -> Vector2
max_point :: BBox2 -> Vector2
max_point (BBox2 Scalar
x0 Scalar
y0 Scalar
x1 Scalar
y1) = Scalar -> Scalar -> Vector2
Vector2 Scalar
x1 Scalar
y1

-- | Take the union of two bounding boxes. The result is a new bounding box that contains all the points the original boxes contained, plus any extra space between them.
union :: BBox2 -> BBox2 -> BBox2
union :: BBox2 -> BBox2 -> BBox2
union BBox2
b0 BBox2
b1 =
  let
    rx :: Range
rx = (BBox2 -> Range
rangeX BBox2
b0) Range -> Range -> Range
`R.union` (BBox2 -> Range
rangeX BBox2
b1)
    ry :: Range
ry = (BBox2 -> Range
rangeY BBox2
b0) Range -> Range -> Range
`R.union` (BBox2 -> Range
rangeY BBox2
b1)
  in Range -> Range -> BBox2
rangeXY Range
rx Range
ry

-- | Take the intersection of two bounding boxes. If the boxes do not overlap, return 'Nothing'. Otherwise return a new bounding box containing only the points common to both argument boxes.
isect :: BBox2 -> BBox2 -> Maybe BBox2
isect :: BBox2 -> BBox2 -> Maybe BBox2
isect BBox2
b0 BBox2
b1 = do
  Range
rx <- (BBox2 -> Range
rangeX BBox2
b0) Range -> Range -> Maybe Range
`R.isect` (BBox2 -> Range
rangeX BBox2
b1)
  Range
ry <- (BBox2 -> Range
rangeY BBox2
b0) Range -> Range -> Maybe Range
`R.isect` (BBox2 -> Range
rangeY BBox2
b1)
  BBox2 -> Maybe BBox2
forall a. a -> Maybe a
forall (m :: * -> *) a. Monad m => a -> m a
return (Range -> Range -> BBox2
rangeXY Range
rx Range
ry)

-- | Efficiently compute the union of a list of bounding boxes.
unions :: [BBox2] -> BBox2
unions :: [BBox2] -> BBox2
unions [BBox2]
bs =
  let
    minP :: [Vector2]
minP = (BBox2 -> Vector2) -> [BBox2] -> [Vector2]
forall a b. (a -> b) -> [a] -> [b]
map BBox2 -> Vector2
min_point [BBox2]
bs
    maxP :: [Vector2]
maxP = (BBox2 -> Vector2) -> [BBox2] -> [Vector2]
forall a b. (a -> b) -> [a] -> [b]
map BBox2 -> Vector2
max_point [BBox2]
bs
  in
    Scalar -> Scalar -> Scalar -> Scalar -> BBox2
BBox2
      ([Scalar] -> Scalar
forall a. Ord a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
minimum ([Scalar] -> Scalar) -> [Scalar] -> Scalar
forall a b. (a -> b) -> a -> b
$ (Vector2 -> Scalar) -> [Vector2] -> [Scalar]
forall a b. (a -> b) -> [a] -> [b]
map Vector2 -> Scalar
v2x [Vector2]
minP) ([Scalar] -> Scalar
forall a. Ord a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
minimum ([Scalar] -> Scalar) -> [Scalar] -> Scalar
forall a b. (a -> b) -> a -> b
$ (Vector2 -> Scalar) -> [Vector2] -> [Scalar]
forall a b. (a -> b) -> [a] -> [b]
map Vector2 -> Scalar
v2y [Vector2]
minP)
      ([Scalar] -> Scalar
forall a. Ord a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
maximum ([Scalar] -> Scalar) -> [Scalar] -> Scalar
forall a b. (a -> b) -> a -> b
$ (Vector2 -> Scalar) -> [Vector2] -> [Scalar]
forall a b. (a -> b) -> [a] -> [b]
map Vector2 -> Scalar
v2x [Vector2]
maxP) ([Scalar] -> Scalar
forall a. Ord a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
maximum ([Scalar] -> Scalar) -> [Scalar] -> Scalar
forall a b. (a -> b) -> a -> b
$ (Vector2 -> Scalar) -> [Vector2] -> [Scalar]
forall a b. (a -> b) -> [a] -> [b]
map Vector2 -> Scalar
v2y [Vector2]
maxP)