-------------------------------------------------
-- |
-- Module      : Data.SpaceFillingCurves
-- Copyright   : (c) Raphael 'kena' Poss 2014
-- License     : Public domain (Unlicense)
--
-- Maintainer  : knz@thaumogen.net
-- Stability   : experimental
-- Portability : portable
--
-- Generators of space-filling curves.
-------------------------------------------------

module Data.SpaceFillingCurves (
  hilbert
, moore
) where

import Control.Applicative (Applicative(..), Alternative(..))

-- | Generate a Hilbert space-filling curve. (open curve)
--
-- The function generates 4^@n@ points, shifted from the origin
-- by (@x0@, @y0@). The pair (@xi@, @yi@) determines the planar
-- coordinates of the I vector ("X axis") and the pair (@xj@, @yj@)
-- the coordinates of the J vector ("Y axis").
hilbert :: (Eq n, Num n, Fractional f, Alternative p) => n -> f -> f -> f -> f -> f -> f -> p (f,f)
hilbert :: forall n f (p :: * -> *).
(Eq n, Num n, Fractional f, Alternative p) =>
n -> f -> f -> f -> f -> f -> f -> p (f, f)
hilbert n
0 f
x0 f
y0 f
xi f
xj f
yi f
yj = (f, f) -> p (f, f)
forall a. a -> p a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (f
x0 f -> f -> f
forall a. Num a => a -> a -> a
+ (f
xi f -> f -> f
forall a. Num a => a -> a -> a
+ f
yi) f -> f -> f
forall a. Fractional a => a -> a -> a
/ f
2, f
y0 f -> f -> f
forall a. Num a => a -> a -> a
+ (f
xj f -> f -> f
forall a. Num a => a -> a -> a
+ f
yj) f -> f -> f
forall a. Fractional a => a -> a -> a
/ f
2)
hilbert n
n f
x0 f
y0 f
xi f
xj f
yi f
yj = p (f, f)
a p (f, f) -> p (f, f) -> p (f, f)
forall a. p a -> p a -> p a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
<|> p (f, f)
b p (f, f) -> p (f, f) -> p (f, f)
forall a. p a -> p a -> p a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
<|> p (f, f)
c p (f, f) -> p (f, f) -> p (f, f)
forall a. p a -> p a -> p a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
<|> p (f, f)
d
   where
     a :: p (f, f)
a = n -> f -> f -> f -> f -> f -> f -> p (f, f)
forall n f (p :: * -> *).
(Eq n, Num n, Fractional f, Alternative p) =>
n -> f -> f -> f -> f -> f -> f -> p (f, f)
hilbert (n
nn -> n -> n
forall a. Num a => a -> a -> a
-n
1) (f
x0)           (f
y0)           (f
yif -> f -> f
forall a. Fractional a => a -> a -> a
/f
2)  (f
yjf -> f -> f
forall a. Fractional a => a -> a -> a
/f
2)  (f
xif -> f -> f
forall a. Fractional a => a -> a -> a
/f
2)  (f
xjf -> f -> f
forall a. Fractional a => a -> a -> a
/f
2)
     b :: p (f, f)
b = n -> f -> f -> f -> f -> f -> f -> p (f, f)
forall n f (p :: * -> *).
(Eq n, Num n, Fractional f, Alternative p) =>
n -> f -> f -> f -> f -> f -> f -> p (f, f)
hilbert (n
nn -> n -> n
forall a. Num a => a -> a -> a
-n
1) (f
x0f -> f -> f
forall a. Num a => a -> a -> a
+f
xif -> f -> f
forall a. Fractional a => a -> a -> a
/f
2)      (f
y0f -> f -> f
forall a. Num a => a -> a -> a
+f
xjf -> f -> f
forall a. Fractional a => a -> a -> a
/f
2)      (f
xif -> f -> f
forall a. Fractional a => a -> a -> a
/f
2)  (f
xjf -> f -> f
forall a. Fractional a => a -> a -> a
/f
2)  (f
yif -> f -> f
forall a. Fractional a => a -> a -> a
/f
2)  (f
yjf -> f -> f
forall a. Fractional a => a -> a -> a
/f
2)
     c :: p (f, f)
c = n -> f -> f -> f -> f -> f -> f -> p (f, f)
forall n f (p :: * -> *).
(Eq n, Num n, Fractional f, Alternative p) =>
n -> f -> f -> f -> f -> f -> f -> p (f, f)
hilbert (n
nn -> n -> n
forall a. Num a => a -> a -> a
-n
1) (f
x0f -> f -> f
forall a. Num a => a -> a -> a
+f
xif -> f -> f
forall a. Fractional a => a -> a -> a
/f
2f -> f -> f
forall a. Num a => a -> a -> a
+f
yif -> f -> f
forall a. Fractional a => a -> a -> a
/f
2) (f
y0f -> f -> f
forall a. Num a => a -> a -> a
+f
xjf -> f -> f
forall a. Fractional a => a -> a -> a
/f
2f -> f -> f
forall a. Num a => a -> a -> a
+f
yjf -> f -> f
forall a. Fractional a => a -> a -> a
/f
2) (f
xif -> f -> f
forall a. Fractional a => a -> a -> a
/f
2)  (f
xjf -> f -> f
forall a. Fractional a => a -> a -> a
/f
2)  (f
yif -> f -> f
forall a. Fractional a => a -> a -> a
/f
2)  (f
yjf -> f -> f
forall a. Fractional a => a -> a -> a
/f
2)
     d :: p (f, f)
d = n -> f -> f -> f -> f -> f -> f -> p (f, f)
forall n f (p :: * -> *).
(Eq n, Num n, Fractional f, Alternative p) =>
n -> f -> f -> f -> f -> f -> f -> p (f, f)
hilbert (n
nn -> n -> n
forall a. Num a => a -> a -> a
-n
1) (f
x0f -> f -> f
forall a. Num a => a -> a -> a
+f
xif -> f -> f
forall a. Fractional a => a -> a -> a
/f
2f -> f -> f
forall a. Num a => a -> a -> a
+f
yi)   (f
y0f -> f -> f
forall a. Num a => a -> a -> a
+f
xjf -> f -> f
forall a. Fractional a => a -> a -> a
/f
2f -> f -> f
forall a. Num a => a -> a -> a
+f
yj)   (-f
yif -> f -> f
forall a. Fractional a => a -> a -> a
/f
2) (-f
yjf -> f -> f
forall a. Fractional a => a -> a -> a
/f
2) (-f
xif -> f -> f
forall a. Fractional a => a -> a -> a
/f
2) (-f
xjf -> f -> f
forall a. Fractional a => a -> a -> a
/f
2)

-- | Generate a Moore space-filling curve. (closed curve)
--
-- The function generates 4^@n@ points, shifted from the origin
-- by (@x0@, @y0@). The pair (@xi@, @yi@) determines the planar
-- coordinates of the I vector ("X axis") and the pair (@xj@, @yj@)
-- the coordinates of the J vector ("Y axis").
moore :: (Eq n, Num n, Fractional f, Alternative p) => n -> f -> f -> f -> f -> f -> f -> p (f,f)
moore :: forall n f (p :: * -> *).
(Eq n, Num n, Fractional f, Alternative p) =>
n -> f -> f -> f -> f -> f -> f -> p (f, f)
moore n
0 f
x0 f
y0 f
xi f
xj f
yi f
yj = (f, f) -> p (f, f)
forall a. a -> p a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (f
x0 f -> f -> f
forall a. Num a => a -> a -> a
+ (f
xi f -> f -> f
forall a. Num a => a -> a -> a
+ f
yi) f -> f -> f
forall a. Fractional a => a -> a -> a
/ f
2, f
y0 f -> f -> f
forall a. Num a => a -> a -> a
+ (f
xj f -> f -> f
forall a. Num a => a -> a -> a
+ f
yj) f -> f -> f
forall a. Fractional a => a -> a -> a
/ f
2)
moore n
n f
x0 f
y0 f
xi f
xj f
yi f
yj = p (f, f)
a p (f, f) -> p (f, f) -> p (f, f)
forall a. p a -> p a -> p a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
<|> p (f, f)
b p (f, f) -> p (f, f) -> p (f, f)
forall a. p a -> p a -> p a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
<|> p (f, f)
c p (f, f) -> p (f, f) -> p (f, f)
forall a. p a -> p a -> p a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
<|> p (f, f)
d
   where
     a :: p (f, f)
a = n -> f -> f -> f -> f -> f -> f -> p (f, f)
forall n f (p :: * -> *).
(Eq n, Num n, Fractional f, Alternative p) =>
n -> f -> f -> f -> f -> f -> f -> p (f, f)
hilbert (n
nn -> n -> n
forall a. Num a => a -> a -> a
-n
1) (f
x0f -> f -> f
forall a. Num a => a -> a -> a
+f
xif -> f -> f
forall a. Fractional a => a -> a -> a
/f
2)       (f
y0f -> f -> f
forall a. Num a => a -> a -> a
+f
xjf -> f -> f
forall a. Fractional a => a -> a -> a
/f
2)      (-f
xif -> f -> f
forall a. Fractional a => a -> a -> a
/f
2) (f
xjf -> f -> f
forall a. Fractional a => a -> a -> a
/f
2) (f
yif -> f -> f
forall a. Fractional a => a -> a -> a
/f
2) (f
yjf -> f -> f
forall a. Fractional a => a -> a -> a
/f
2)
     b :: p (f, f)
b = n -> f -> f -> f -> f -> f -> f -> p (f, f)
forall n f (p :: * -> *).
(Eq n, Num n, Fractional f, Alternative p) =>
n -> f -> f -> f -> f -> f -> f -> p (f, f)
hilbert (n
nn -> n -> n
forall a. Num a => a -> a -> a
-n
1) (f
x0f -> f -> f
forall a. Num a => a -> a -> a
+f
xif -> f -> f
forall a. Fractional a => a -> a -> a
/f
2f -> f -> f
forall a. Num a => a -> a -> a
+f
yif -> f -> f
forall a. Fractional a => a -> a -> a
/f
2)  (f
y0f -> f -> f
forall a. Num a => a -> a -> a
+f
xjf -> f -> f
forall a. Fractional a => a -> a -> a
/f
2f -> f -> f
forall a. Num a => a -> a -> a
+f
yjf -> f -> f
forall a. Fractional a => a -> a -> a
/f
2) (-f
xif -> f -> f
forall a. Fractional a => a -> a -> a
/f
2) (f
xjf -> f -> f
forall a. Fractional a => a -> a -> a
/f
2) (f
yif -> f -> f
forall a. Fractional a => a -> a -> a
/f
2) (f
yjf -> f -> f
forall a. Fractional a => a -> a -> a
/f
2)
     c :: p (f, f)
c = n -> f -> f -> f -> f -> f -> f -> p (f, f)
forall n f (p :: * -> *).
(Eq n, Num n, Fractional f, Alternative p) =>
n -> f -> f -> f -> f -> f -> f -> p (f, f)
hilbert (n
nn -> n -> n
forall a. Num a => a -> a -> a
-n
1) (f
x0f -> f -> f
forall a. Num a => a -> a -> a
+f
xif -> f -> f
forall a. Fractional a => a -> a -> a
/f
2f -> f -> f
forall a. Num a => a -> a -> a
+f
yi)    (f
y0f -> f -> f
forall a. Num a => a -> a -> a
+f
xjf -> f -> f
forall a. Fractional a => a -> a -> a
/f
2f -> f -> f
forall a. Num a => a -> a -> a
+f
yj)   (f
xif -> f -> f
forall a. Fractional a => a -> a -> a
/f
2)  (f
xjf -> f -> f
forall a. Fractional a => a -> a -> a
/f
2) (f
yif -> f -> f
forall a. Fractional a => a -> a -> a
/f
2) (-f
yjf -> f -> f
forall a. Fractional a => a -> a -> a
/f
2)
     d :: p (f, f)
d = n -> f -> f -> f -> f -> f -> f -> p (f, f)
forall n f (p :: * -> *).
(Eq n, Num n, Fractional f, Alternative p) =>
n -> f -> f -> f -> f -> f -> f -> p (f, f)
hilbert (n
nn -> n -> n
forall a. Num a => a -> a -> a
-n
1) (f
x0f -> f -> f
forall a. Num a => a -> a -> a
+f
xif -> f -> f
forall a. Fractional a => a -> a -> a
/f
2f -> f -> f
forall a. Num a => a -> a -> a
+f
yif -> f -> f
forall a. Fractional a => a -> a -> a
/f
2)  (f
y0f -> f -> f
forall a. Num a => a -> a -> a
+f
xjf -> f -> f
forall a. Fractional a => a -> a -> a
/f
2f -> f -> f
forall a. Num a => a -> a -> a
+f
yjf -> f -> f
forall a. Fractional a => a -> a -> a
/f
2) (f
xif -> f -> f
forall a. Fractional a => a -> a -> a
/f
2)  (f
xjf -> f -> f
forall a. Fractional a => a -> a -> a
/f
2) (f
yif -> f -> f
forall a. Fractional a => a -> a -> a
/f
2) (-f
yjf -> f -> f
forall a. Fractional a => a -> a -> a
/f
2)