Hilbert curve: Difference between revisions

===Imperative===

<lang javascript>const hilbert = (width, spacing, points) => (x, y, lg, i1, i2, f) => {

if (lg === 1) {

const px = (width - x) * spacing;

const py = (width - y) * spacing;

points.push(px, py);

return;

}

lg >>= 1;

f(x + i1 * lg, y + i1 * lg, lg, i1, 1 - i2, f);

f(x + i2 * lg, y + (1 - i2) * lg, lg, i1, i2, f);

f(x + (1 - i1) * lg, y + (1 - i1) * lg, lg, i1, i2, f);

f(x + (1 - i2) * lg, y + i2 * lg, lg, 1 - i1, i2, f);

return points;

if (!order || order < 1) {

throw 'You need to give a valid positive integer';

} else {

order = Math.floor(order);

}

// Curve Constants

const width = 2 ** order;

const space = 10;

// SVG Setup

const size = 500;

const stroke = 2;

const col = "red";

const fill = "transparent";

// Prep and run function

const f = hilbert(width, space, []);

const points = f(0, 0, width, 0, 0, f);

const path = points.join(' ');

console.log(

`<svg xmlns="http://www.w3.org/2000/svg"

drawHilbert(6);</lang>

===Functional===

{{Trans|Python}}

A composition of generic pure functions which defines a Hilbert tree as the Nth application of a production rule to a seedling tree.

A list of points is derived by serialization of that tree.

Like the version above, generates an SVG string for display in a browser.

<lang JavaScript>(() => {

'use strict';

const main = () => {

// rule :: Dict Char [Char]

const rule = {

a: ['d', 'a', 'a', 'b'],

b: ['c', 'b', 'b', 'a'],

c: ['b', 'c', 'c', 'd'],

d: ['a', 'd', 'd', 'c']

};

// vectors :: Dict Char [(Int, Int)]

const vectors = ({

'a': [

[-1, 1],

[-1, -1],

[1, -1],

[1, 1]

],

'b': [

[1, -1],

[-1, -1],

[-1, 1],

[1, 1]

],

'c': [

[1, -1],

[1, 1],

[-1, 1],

[-1, -1]

],

'd': [

[-1, 1],

[1, 1],

[1, -1],

[-1, -1]

]

});

// hilbertCurve :: Int -> SVG string

const hilbertCurve = n => {

const w = 1024

return svgFromPoints(w)(

hilbertPoints(w)(

hilbertTree(n)

)

);

}

// hilbertTree :: Int -> Tree Char

const hilbertTree = n => {

const go = tree =>

Node(

tree.root,

0 < tree.nest.length ? (

map(go, tree.nest)

) : map(x => Node(x, []), rule[tree.root])

);

const seed = Node('a', []);

return 0 < n ? (

take(n, iterate(go, seed)).slice(-1)[0]

) : seed;

};

// hilbertPoints :: Size -> Tree Char -> [(x, y)]

// hilbertPoints :: Int -> Tree Char -> [(Int, Int)]

const hilbertPoints = w => tree => {

const go = d => (xy, tree) => {

const

r = Math.floor(d / 2),

centres = map(

v => [

xy[0] + (r * v[0]),

xy[1] + (r * v[1])

],

vectors[tree.root]

);

return 0 < tree.nest.length ? concat(

zipWith(go(r), centres, tree.nest)

) : centres;

};

const d = Math.floor(w / 2);

return go(d)([d, d], tree);

};

// svgFromPoints :: Int -> [(Int, Int)] -> String

const svgFromPoints = w => xys => ['<svg xmlns="http://www.w3.org/2000/svg"',

`width="500" height="500" viewBox="5 5 ${w} ${w}">`,

`<path d="M${concat(xys).join(' ')}" `,

'stroke-width="2" stroke="red" fill="transparent"/>',

'</svg>'

].join('\n');

// TEST -------------------------------------------

console.log(

hilbertCurve(6)

);

};

// GENERIC FUNCTIONS ----------------------------------

// Node :: a -> [Tree a] -> Tree a

const Node = (v, xs) => ({

type: 'Node',

root: v, // any type of value (consistent across tree)

nest: xs || []

});

// concat :: [[a]] -> [a]

// concat :: [String] -> String

const concat = xs =>

0 < xs.length ? (() => {

const unit = 'string' !== typeof xs[0] ? (

[]

) : '';

return unit.concat.apply(unit, xs);

})() : [];

// iterate :: (a -> a) -> a -> Gen [a]

function* iterate(f, x) {

let v = x;

while (true) {

yield(v);

v = f(v);

}

}

// Returns Infinity over objects without finite length.

// This enables zip and zipWith to choose the shorter

// argument when one is non-finite, like cycle, repeat etc

// length :: [a] -> Int

const length = xs =>

(Array.isArray(xs) || 'string' === typeof xs) ? (

xs.length

) : Infinity;

// map :: (a -> b) -> [a] -> [b]

const map = (f, xs) =>

(Array.isArray(xs) ? (

xs

) : xs.split('')).map(f);

// take :: Int -> [a] -> [a]

// take :: Int -> String -> String

const take = (n, xs) =>

'GeneratorFunction' !== xs.constructor.constructor.name ? (

xs.slice(0, n)

) : [].concat.apply([], Array.from({

length: n

}, () => {

const x = xs.next();

return x.done ? [] : [x.value];

}));

// Use of `take` and `length` here allows zipping with non-finite lists

// i.e. generators like cycle, repeat, iterate.

// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

const zipWith = (f, xs, ys) => {

const

lng = Math.min(length(xs), length(ys)),

as = take(lng, xs),

bs = take(lng, ys);

return Array.from({

length: lng

}, (_, i) => f(as[i], bs[i], i));

};

// MAIN ---

return main();

})();</lang>