{- |
  This module provides the 'BBox4' type for 4-dimensional bounding boxes (bounding hyper-volumes\).
-}

module Data.BoundingBox.B4 where

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

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

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

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

-- | Return the Z-range that this bounding box covers.
rangeZ :: BBox4 -> R.Range
rangeZ :: BBox4 -> Range
rangeZ BBox4
b = Scalar -> Scalar -> Range
R.Range (BBox4 -> Scalar
minZ BBox4
b) (BBox4 -> Scalar
maxZ BBox4
b)

-- | Return the W-range (4th coordinate) that this bounding box covers.
rangeW :: BBox4 -> R.Range
rangeW :: BBox4 -> Range
rangeW BBox4
b = Scalar -> Scalar -> Range
R.Range (BBox4 -> Scalar
minW BBox4
b) (BBox4 -> Scalar
maxW BBox4
b)

-- | Given ranges for each coordinate axis, construct a bounding box.
rangeXYZW :: R.Range -> R.Range -> R.Range -> R.Range -> BBox4
rangeXYZW :: Range -> Range -> Range -> Range -> BBox4
rangeXYZW (R.Range Scalar
x0 Scalar
x1) (R.Range Scalar
y0 Scalar
y1) (R.Range Scalar
z0 Scalar
z1) (R.Range Scalar
w0 Scalar
w1) = Scalar
-> Scalar
-> Scalar
-> Scalar
-> Scalar
-> Scalar
-> Scalar
-> Scalar
-> BBox4
BBox4 Scalar
x0 Scalar
y0 Scalar
z0 Scalar
w0 Scalar
x1 Scalar
y1 Scalar
z1 Scalar
w1

-- | 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 :: Vector4 -> Vector4 -> BBox4
bound_corners :: Vector4 -> Vector4 -> BBox4
bound_corners (Vector4 Scalar
xa Scalar
ya Scalar
za Scalar
wa) (Vector4 Scalar
xb Scalar
yb Scalar
zb Scalar
wb) =
  Scalar
-> Scalar
-> Scalar
-> Scalar
-> Scalar
-> Scalar
-> Scalar
-> Scalar
-> BBox4
BBox4 (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
min Scalar
za Scalar
zb) (Scalar -> Scalar -> Scalar
forall a. Ord a => a -> a -> a
min Scalar
wa Scalar
wb) (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) (Scalar -> Scalar -> Scalar
forall a. Ord a => a -> a -> a
max Scalar
za Scalar
zb) (Scalar -> Scalar -> Scalar
forall a. Ord a => a -> a -> a
max Scalar
wa Scalar
wb)

-- | Find the bounds of a list of points. (Throws an exception if the list is empty.)
bound_points :: [Vector4] -> BBox4
bound_points :: [Vector4] -> BBox4
bound_points [Vector4]
ps =
  let
    xs :: [Scalar]
xs = (Vector4 -> Scalar) -> [Vector4] -> [Scalar]
forall a b. (a -> b) -> [a] -> [b]
map Vector4 -> Scalar
v4x [Vector4]
ps
    ys :: [Scalar]
ys = (Vector4 -> Scalar) -> [Vector4] -> [Scalar]
forall a b. (a -> b) -> [a] -> [b]
map Vector4 -> Scalar
v4y [Vector4]
ps
    zs :: [Scalar]
zs = (Vector4 -> Scalar) -> [Vector4] -> [Scalar]
forall a b. (a -> b) -> [a] -> [b]
map Vector4 -> Scalar
v4z [Vector4]
ps
    ws :: [Scalar]
ws = (Vector4 -> Scalar) -> [Vector4] -> [Scalar]
forall a b. (a -> b) -> [a] -> [b]
map Vector4 -> Scalar
v4w [Vector4]
ps
  in Scalar
-> Scalar
-> Scalar
-> Scalar
-> Scalar
-> Scalar
-> Scalar
-> Scalar
-> BBox4
BBox4 ([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
minimum [Scalar]
zs) ([Scalar] -> Scalar
forall a. Ord a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
minimum [Scalar]
ws) ([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) ([Scalar] -> Scalar
forall a. Ord a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
maximum [Scalar]
zs) ([Scalar] -> Scalar
forall a. Ord a => [a] -> a
forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
maximum [Scalar]
ws)

-- | Test whether a given 4D vector is inside this bounding box.
within_bounds :: Vector4 -> BBox4 -> Bool
within_bounds :: Vector4 -> BBox4 -> Bool
within_bounds (Vector4 Scalar
x Scalar
y Scalar
z Scalar
w) BBox4
b =
  Scalar
x Scalar -> Range -> Bool
`R.within_bounds` (BBox4 -> Range
rangeX BBox4
b) Bool -> Bool -> Bool
&&
  Scalar
y Scalar -> Range -> Bool
`R.within_bounds` (BBox4 -> Range
rangeY BBox4
b) Bool -> Bool -> Bool
&&
  Scalar
z Scalar -> Range -> Bool
`R.within_bounds` (BBox4 -> Range
rangeZ BBox4
b) Bool -> Bool -> Bool
&&
  Scalar
w Scalar -> Range -> Bool
`R.within_bounds` (BBox4 -> Range
rangeW BBox4
b)

-- | Return the minimum values for all coordinates.
min_point :: BBox4 -> Vector4
min_point :: BBox4 -> Vector4
min_point (BBox4 Scalar
x0 Scalar
y0 Scalar
z0 Scalar
w0 Scalar
x1 Scalar
y1 Scalar
z1 Scalar
w1) = Scalar -> Scalar -> Scalar -> Scalar -> Vector4
Vector4 Scalar
x0 Scalar
y0 Scalar
z0 Scalar
w0

-- | Return the maximum values for all coordinates.
max_point :: BBox4 -> Vector4
max_point :: BBox4 -> Vector4
max_point (BBox4 Scalar
x0 Scalar
y0 Scalar
z0 Scalar
w0 Scalar
x1 Scalar
y1 Scalar
z1 Scalar
w1) = Scalar -> Scalar -> Scalar -> Scalar -> Vector4
Vector4 Scalar
x1 Scalar
y1 Scalar
z1 Scalar
w1

-- | 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 :: BBox4 -> BBox4 -> BBox4
union :: BBox4 -> BBox4 -> BBox4
union BBox4
b0 BBox4
b1 =
  let
    rx :: Range
rx = (BBox4 -> Range
rangeX BBox4
b0) Range -> Range -> Range
`R.union` (BBox4 -> Range
rangeX BBox4
b1)
    ry :: Range
ry = (BBox4 -> Range
rangeY BBox4
b0) Range -> Range -> Range
`R.union` (BBox4 -> Range
rangeY BBox4
b1)
    rz :: Range
rz = (BBox4 -> Range
rangeZ BBox4
b0) Range -> Range -> Range
`R.union` (BBox4 -> Range
rangeZ BBox4
b1)
    rw :: Range
rw = (BBox4 -> Range
rangeW BBox4
b0) Range -> Range -> Range
`R.union` (BBox4 -> Range
rangeW BBox4
b1)
  in Range -> Range -> Range -> Range -> BBox4
rangeXYZW Range
rx Range
ry Range
rz Range
rw

-- | 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 :: BBox4 -> BBox4 -> Maybe BBox4
isect :: BBox4 -> BBox4 -> Maybe BBox4
isect BBox4
b0 BBox4
b1 = do
  Range
rx <- (BBox4 -> Range
rangeX BBox4
b0) Range -> Range -> Maybe Range
`R.isect` (BBox4 -> Range
rangeX BBox4
b1)
  Range
ry <- (BBox4 -> Range
rangeY BBox4
b0) Range -> Range -> Maybe Range
`R.isect` (BBox4 -> Range
rangeY BBox4
b1)
  Range
rz <- (BBox4 -> Range
rangeZ BBox4
b0) Range -> Range -> Maybe Range
`R.isect` (BBox4 -> Range
rangeZ BBox4
b1)
  Range
rw <- (BBox4 -> Range
rangeW BBox4
b0) Range -> Range -> Maybe Range
`R.isect` (BBox4 -> Range
rangeW BBox4
b1)
  BBox4 -> Maybe BBox4
forall a. a -> Maybe a
forall (m :: * -> *) a. Monad m => a -> m a
return (Range -> Range -> Range -> Range -> BBox4
rangeXYZW Range
rx Range
ry Range
rz Range
rw)

-- | Efficiently compute the union of a list of bounding boxes.
unions :: [BBox4] -> BBox4
unions :: [BBox4] -> BBox4
unions [BBox4]
bs =
  let
    minP :: [Vector4]
minP = (BBox4 -> Vector4) -> [BBox4] -> [Vector4]
forall a b. (a -> b) -> [a] -> [b]
map BBox4 -> Vector4
min_point [BBox4]
bs
    maxP :: [Vector4]
maxP = (BBox4 -> Vector4) -> [BBox4] -> [Vector4]
forall a b. (a -> b) -> [a] -> [b]
map BBox4 -> Vector4
max_point [BBox4]
bs
  in
    Scalar
-> Scalar
-> Scalar
-> Scalar
-> Scalar
-> Scalar
-> Scalar
-> Scalar
-> BBox4
BBox4
      ([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
$ (Vector4 -> Scalar) -> [Vector4] -> [Scalar]
forall a b. (a -> b) -> [a] -> [b]
map Vector4 -> Scalar
v4x [Vector4]
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
$ (Vector4 -> Scalar) -> [Vector4] -> [Scalar]
forall a b. (a -> b) -> [a] -> [b]
map Vector4 -> Scalar
v4y [Vector4]
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
$ (Vector4 -> Scalar) -> [Vector4] -> [Scalar]
forall a b. (a -> b) -> [a] -> [b]
map Vector4 -> Scalar
v4z [Vector4]
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
$ (Vector4 -> Scalar) -> [Vector4] -> [Scalar]
forall a b. (a -> b) -> [a] -> [b]
map Vector4 -> Scalar
v4w [Vector4]
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
$ (Vector4 -> Scalar) -> [Vector4] -> [Scalar]
forall a b. (a -> b) -> [a] -> [b]
map Vector4 -> Scalar
v4x [Vector4]
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
$ (Vector4 -> Scalar) -> [Vector4] -> [Scalar]
forall a b. (a -> b) -> [a] -> [b]
map Vector4 -> Scalar
v4y [Vector4]
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
$ (Vector4 -> Scalar) -> [Vector4] -> [Scalar]
forall a b. (a -> b) -> [a] -> [b]
map Vector4 -> Scalar
v4z [Vector4]
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
$ (Vector4 -> Scalar) -> [Vector4] -> [Scalar]
forall a b. (a -> b) -> [a] -> [b]
map Vector4 -> Scalar
v4w [Vector4]
maxP)