smoothie 0.1.3 → 0.2

raw patch · 5 files changed

+125/−110 lines, 5 files

Files

• CHANGELOG.md +7/−1
• smoothie.cabal +6/−4
• src/Data/Spline.hs +13/−6
• src/Data/Spline/CP.hs +2/−2
• src/Data/Spline/Polynomial.hs +97/−97

@@ -1,6 +1,12 @@+## 0.2++- Function 'smooth' has a new name; 'sample'.+- Enhanced internal implementation.+- Fixed some documentation formatting issues.+ ## 0.1.3 -- Support for GHC 7.10+- Support for GHC 7.10.  ## 0.1.2 

@@ -1,5 +1,5 @@ name:                smoothie
-version:             0.1.3
+version:             0.2
 synopsis:            Smooth curves via several splines and polynomials.
 description:         This package exports several splines and curves you can use
                      to interpolate points in between.
@@ -20,11 +20,13 @@ 
   ghc-options:         -W -Wall -O2 -funbox-strict-fields
 
-  default-extensions:  DeriveFunctor
+  default-extensions:  DeriveFoldable
+                     , DeriveFunctor
+                     , DeriveTraversable
 
   exposed-modules:     Data.Spline
-                    , Data.Spline.CP
-                    , Data.Spline.Polynomial
+                     , Data.Spline.CP
+                     , Data.Spline.Polynomial
 
 
   build-depends:       base   >= 4.7  && < 5.0

@@ -19,8 +19,8 @@     -- * Spline     Spline   , spline-    -- * Smoothing values along splines-  , smooth+    -- * Sampling values from splines+  , sample   ) where  import Data.List ( sortBy )@@ -43,12 +43,19 @@ spline :: (Ord a,Ord s) => [(CP s a,Polynomial s a)] -> Spline s a spline = uncurry spline_ . unzip . dupLast . sortBy (comparing fst)   where-    dupLast s = s ++ [last s]     spline_ cps polys = Spline (fromList cps) (fromList polys) --- |Smoothly interpolate a point on a spline.-smooth :: (Ord s) => Spline s a -> s -> Maybe a-smooth (Spline cps polys) s = do+-- |Sample a point on a spline.+sample :: (Ord s) => Spline s a -> s -> Maybe a+sample (Spline cps polys) s = do   i <- bsearchLower (\(CP s' _) -> compare s s') cps   p <- polys !? i   unPolynomial p s cps++-- Duplicate the last element in a list.+--+-- Warning: unsafe function.+dupLast :: [a] -> [a]+dupLast [] = []+dupLast [x] = [x,x]+dupLast (x:xs) = x : dupLast xs

@@ -14,10 +14,10 @@     CP(..)
   ) where
 
--- | A 'CP' is a *control point*. A curve passes through control points and
+-- | A 'CP' is a **control point**. A curve passes through control points and
 -- the shape of the curve is determined by the polynomials used to interpolate
 -- values in between.
 --
 -- @CP s a@ is a control point of sampling type 's' and carried type 'a'. In
 -- most cases, 's' must be 'Ord' and 'a' must be 'Additive' and 'Fractional'.
-data CP s a = CP !s !a deriving (Functor,Eq,Ord,Show)
+data CP s a = CP !s !a deriving (Foldable,Functor,Eq,Ord,Show,Traversable)

@@ -1,98 +1,98 @@ -------------------------------------------------------------------------------- |
--- Copyright   : (C) 2015 Dimitri Sabadie
--- License     : BSD3
---
--- Maintainer  : Dimitri Sabadie <dimitri.sabadie@gmail.com>
--- Stability   : experimental
--- Portability : portable
---
-----------------------------------------------------------------------------
-
-module Data.Spline.Polynomial (
-    -- * Polynomial
-    Polynomial(unPolynomial)
-    -- * Polynomials for interpolation
-  , hold
-  , linear
-  , linearBy
-  , cosine
-    -- * Helpers
-  , bsearchLower
-  ) where
-
-import Control.Monad ( guard )
-import Data.Spline.CP
-import Data.Vector as V ( Vector, (!?), length )
-import Linear ( Additive(lerp) )
-
--- |A 'Polynomial' is used to interpolate in between a spline’s control points.
-newtype Polynomial s a = Polynomial { unPolynomial :: s -> Vector (CP s a) -> Maybe a}
-
--- |Constant polynomial – a.k.a. /no interpolation/.
---
--- Given two control points and a sample value in between, the 'hold' polynomial
--- won’t perform any interpolation but it just /holds/ the value carried by the
--- lower control point along the whole curve between the two control points.
-hold :: (Ord s) => Polynomial s a
-hold = Polynomial go
-  where
-    go s cps = do
-        li <- bsearchLower (\(CP s' _) -> compare s s') cps
-        CP _ r <- cps !? li
-        return r
-
--- |Parametric linear polynomial.
---
--- This form applies a pre-filter on the input before performing a linear
--- interpolation. Instead of:
---
--- @ lerp x a b @
---
--- We have:
---
--- @ lerp (pref x) a b @
---
--- This can be used to implement 1-degree splines if @pref = id@, basic cubic
--- non-hermitian splines if @pref = (^3)@, cosine splines if
--- @pref = \x -> (1 - cos (x*pi)) * 0.5@, and so on and so forth.
-linearBy :: (Additive a,Fractional s,Ord s) => (s -> s) -> Polynomial s (a s)
-linearBy pref = Polynomial go
-  where
-    go s cps = do
-        li <- bsearchLower (\(CP s' _) -> compare s s') cps
-        lower <- cps !? li
-        upper <- cps !? succ li
-        return $ lerp_ s lower upper
-    lerp_ x (CP s0 a) (CP s1 b) = lerp x' b a
-      where
-        x' = (pref x - s0) / (s1 - s0)
-
--- |1-degree polynomial – a.k.a. /straight line interpolation/, or /linear
--- interpolation/.
---
--- This polynomial connects control points with straight lines.
---
--- Note: implemented with @linearBy id@.
-linear :: (Additive a,Fractional s,Ord s) => Polynomial s (a s)
-linear = linearBy id
-
--- |Cosine polynomial.
-cosine :: (Additive a,Floating s,Ord s) => Polynomial s (a s)
-cosine = linearBy $ \x -> (1 - cos (x * pi)) * 0.5
-
--- |Helper binary search that search the ceiling index for the
--- value to be searched according to the predicate.
-bsearchLower :: (a -> Ordering) -> Vector a -> Maybe Int
-bsearchLower p v = go 0 (pred $ V.length v)
-  where
-    go start end = do
-        guard (start <= end)
-        ma <- v !? m
-        ma1 <- v !? succ m
-        case p ma of
-          LT -> go start (pred m)
-          EQ -> Just m
-          GT -> if p ma1 == LT then Just m else go (succ m) end
-      where
-        m = (end + start) `div` 2
+-- |+-- Copyright   : (C) 2015 Dimitri Sabadie+-- License     : BSD3+--+-- Maintainer  : Dimitri Sabadie <dimitri.sabadie@gmail.com>+-- Stability   : experimental+-- Portability : portable+--+----------------------------------------------------------------------------++module Data.Spline.Polynomial (+    -- * Polynomial+    Polynomial(unPolynomial)+    -- * Polynomials for interpolation+  , hold+  , linear+  , linearBy+  , cosine+    -- * Helpers+  , bsearchLower+  ) where++import Control.Monad ( guard )+import Data.Spline.CP+import Data.Vector as V ( Vector, (!?), length )+import Linear ( Additive(lerp) )++-- |A 'Polynomial' is used to interpolate in between a spline’s control points.+newtype Polynomial s a = Polynomial { unPolynomial :: s -> Vector (CP s a) -> Maybe a}++-- |Constant polynomial – a.k.a. /no interpolation/.+--+-- Given two control points and a sample value in between, the 'hold' polynomial+-- won’t perform any interpolation but it just /holds/ the value carried by the+-- lower control point along the whole curve between the two control points.+hold :: (Ord s) => Polynomial s a+hold = Polynomial go+  where+    go s cps = do+        li <- bsearchLower (\(CP s' _) -> compare s s') cps+        CP _ r <- cps !? li+        return r++-- |Parametric linear polynomial.+--+-- This form applies a pre-filter on the input before performing a linear+-- interpolation. Instead of:+--+-- @ lerp x a b @+--+-- We have:+--+-- @ lerp (pref x) a b @+--+-- This can be used to implement 1-degree splines if @pref = id@, basic cubic+-- non-hermitian splines if @pref = (^3)@, cosine splines if+-- @pref = \x -> (1 - cos (x*pi)) * 0.5@, and so on and so forth.+linearBy :: (Additive a,Fractional s,Ord s) => (s -> s) -> Polynomial s (a s)+linearBy pref = Polynomial go+  where+    go s cps = do+        li <- bsearchLower (\(CP s' _) -> compare s s') cps+        lower <- cps !? li+        upper <- cps !? succ li+        return $ lerp_ s lower upper+    lerp_ x (CP s0 a) (CP s1 b) = lerp x' b a+      where+        x' = (pref x - s0) / (s1 - s0)++-- |1-degree polynomial – a.k.a. /straight line interpolation/, or /linear+-- interpolation/.+--+-- This polynomial connects control points with straight lines.+--+-- Note: implemented with @linearBy id@.+linear :: (Additive a,Fractional s,Ord s) => Polynomial s (a s)+linear = linearBy id++-- |Cosine polynomial.+cosine :: (Additive a,Floating s,Ord s) => Polynomial s (a s)+cosine = linearBy $ \x -> (1 - cos (x * pi)) * 0.5++-- |Helper binary search that search the ceiling index for the+-- value to be searched according to the predicate.+bsearchLower :: (a -> Ordering) -> Vector a -> Maybe Int+bsearchLower p v = go 0 (pred $ V.length v)+  where+    go start end = do+        guard (start <= end)+        ma <- v !? m+        ma1 <- v !? succ m+        case p ma of+          LT -> go start (pred m)+          EQ -> Just m+          GT -> if p ma1 == LT then Just m else go (succ m) end+      where+        m = (end + start) `div` 2