module Bench.Vector.Algo.Quickhull (quickhull) where

import Data.Vector.Unboxed as V

quickhull :: (Vector Double, Vector Double) -> (Vector Double, Vector Double)
{-# NOINLINE quickhull #-}
quickhull :: (Vector Double, Vector Double) -> (Vector Double, Vector Double)
quickhull (Vector Double
xs, Vector Double
ys) = Vector Double
xs' Vector Double
-> (Vector Double, Vector Double) -> (Vector Double, Vector Double)
forall a b. a -> b -> b
`seq` Vector Double
ys' Vector Double
-> (Vector Double, Vector Double) -> (Vector Double, Vector Double)
forall a b. a -> b -> b
`seq` (Vector Double
xs',Vector Double
ys')
    where
      (Vector Double
xs',Vector Double
ys') = Vector (Double, Double) -> (Vector Double, Vector Double)
forall a b.
(Unbox a, Unbox b) =>
Vector (a, b) -> (Vector a, Vector b)
V.unzip
                (Vector (Double, Double) -> (Vector Double, Vector Double))
-> Vector (Double, Double) -> (Vector Double, Vector Double)
forall a b. (a -> b) -> a -> b
$ Vector (Double, Double)
-> (Double, Double) -> (Double, Double) -> Vector (Double, Double)
forall {b}.
(Num b, Unbox b, Ord b) =>
Vector (b, b) -> (b, b) -> (b, b) -> Vector (b, b)
hsplit Vector (Double, Double)
points (Double, Double)
pmin (Double, Double)
pmax Vector (Double, Double)
-> Vector (Double, Double) -> Vector (Double, Double)
forall a. Unbox a => Vector a -> Vector a -> Vector a
V.++ Vector (Double, Double)
-> (Double, Double) -> (Double, Double) -> Vector (Double, Double)
forall {b}.
(Num b, Unbox b, Ord b) =>
Vector (b, b) -> (b, b) -> (b, b) -> Vector (b, b)
hsplit Vector (Double, Double)
points (Double, Double)
pmax (Double, Double)
pmin

      imin :: Int
imin = Vector Double -> Int
forall a. (Unbox a, Ord a) => Vector a -> Int
V.minIndex Vector Double
xs
      imax :: Int
imax = Vector Double -> Int
forall a. (Unbox a, Ord a) => Vector a -> Int
V.maxIndex Vector Double
xs

      points :: Vector (Double, Double)
points = Vector Double -> Vector Double -> Vector (Double, Double)
forall a b.
(Unbox a, Unbox b) =>
Vector a -> Vector b -> Vector (a, b)
V.zip Vector Double
xs Vector Double
ys
      pmin :: (Double, Double)
pmin   = Vector (Double, Double)
points Vector (Double, Double) -> Int -> (Double, Double)
forall a. Unbox a => Vector a -> Int -> a
V.! Int
imin
      pmax :: (Double, Double)
pmax   = Vector (Double, Double)
points Vector (Double, Double) -> Int -> (Double, Double)
forall a. Unbox a => Vector a -> Int -> a
V.! Int
imax


      hsplit :: Vector (b, b) -> (b, b) -> (b, b) -> Vector (b, b)
hsplit Vector (b, b)
points (b, b)
p1 (b, b)
p2
        | Vector (b, b) -> Int
forall a. Unbox a => Vector a -> Int
V.length Vector (b, b)
packed Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
2 = (b, b)
p1 (b, b) -> Vector (b, b) -> Vector (b, b)
forall a. Unbox a => a -> Vector a -> Vector a
`V.cons` Vector (b, b)
packed
        | Bool
otherwise = Vector (b, b) -> (b, b) -> (b, b) -> Vector (b, b)
hsplit Vector (b, b)
packed (b, b)
p1 (b, b)
pm Vector (b, b) -> Vector (b, b) -> Vector (b, b)
forall a. Unbox a => Vector a -> Vector a -> Vector a
V.++ Vector (b, b) -> (b, b) -> (b, b) -> Vector (b, b)
hsplit Vector (b, b)
packed (b, b)
pm (b, b)
p2
        where
          cs :: Vector b
cs     = ((b, b) -> b) -> Vector (b, b) -> Vector b
forall a b. (Unbox a, Unbox b) => (a -> b) -> Vector a -> Vector b
V.map (\(b, b)
p -> (b, b) -> (b, b) -> (b, b) -> b
forall {a}. Num a => (a, a) -> (a, a) -> (a, a) -> a
cross (b, b)
p (b, b)
p1 (b, b)
p2) Vector (b, b)
points
          packed :: Vector (b, b)
packed = (((b, b), b) -> (b, b)) -> Vector ((b, b), b) -> Vector (b, b)
forall a b. (Unbox a, Unbox b) => (a -> b) -> Vector a -> Vector b
V.map ((b, b), b) -> (b, b)
forall a b. (a, b) -> a
fst
                 (Vector ((b, b), b) -> Vector (b, b))
-> Vector ((b, b), b) -> Vector (b, b)
forall a b. (a -> b) -> a -> b
$ (((b, b), b) -> Bool) -> Vector ((b, b), b) -> Vector ((b, b), b)
forall a. Unbox a => (a -> Bool) -> Vector a -> Vector a
V.filter (\((b, b), b)
t -> ((b, b), b) -> b
forall a b. (a, b) -> b
snd ((b, b), b)
t b -> b -> Bool
forall a. Ord a => a -> a -> Bool
> b
0)
                 (Vector ((b, b), b) -> Vector ((b, b), b))
-> Vector ((b, b), b) -> Vector ((b, b), b)
forall a b. (a -> b) -> a -> b
$ Vector (b, b) -> Vector b -> Vector ((b, b), b)
forall a b.
(Unbox a, Unbox b) =>
Vector a -> Vector b -> Vector (a, b)
V.zip Vector (b, b)
points Vector b
cs

          pm :: (b, b)
pm     = Vector (b, b)
points Vector (b, b) -> Int -> (b, b)
forall a. Unbox a => Vector a -> Int -> a
V.! Vector b -> Int
forall a. (Unbox a, Ord a) => Vector a -> Int
V.maxIndex Vector b
cs

      cross :: (a, a) -> (a, a) -> (a, a) -> a
cross (a
x,a
y) (a
x1,a
y1) (a
x2,a
y2) = (a
x1a -> a -> a
forall a. Num a => a -> a -> a
-a
x)a -> a -> a
forall a. Num a => a -> a -> a
*(a
y2a -> a -> a
forall a. Num a => a -> a -> a
-a
y) a -> a -> a
forall a. Num a => a -> a -> a
- (a
y1a -> a -> a
forall a. Num a => a -> a -> a
-a
y)a -> a -> a
forall a. Num a => a -> a -> a
*(a
x2a -> a -> a
forall a. Num a => a -> a -> a
-a
x)