-
-
Save stuartpb/3317841 to your computer and use it in GitHub Desktop.
Hilbert demo
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* Copyright 2010 Barricane Technology Ltd., All rights reserved. | |
* | |
* Released under the MIT licence. | |
*/ | |
/** | |
* Battenburg is simply a 2x2 matrix with non-mutating | |
* methods. | |
* | |
* @param {Object} a | |
* @param {Object} b | |
* @param {Object} c | |
* @param {Object} d | |
*/ | |
function Battenburg(a, b, c, d) { | |
this.a = a; | |
this.b = b; | |
this.c = c; | |
this.d = d; | |
} | |
/** | |
* Returns a new battenburg mirrored on the x=0 line, i.e. swaps up and down. | |
*/ | |
Battenburg.prototype.mirror_x = function() { | |
return new Battenburg(this.c, this.d, this.a, this.b); | |
} | |
/** | |
* Returns a new battenburg rotated 90 degress clockwise. | |
*/ | |
Battenburg.prototype.rotate_c = function(){ | |
return new Battenburg(this.c, this.a, this.d, this.b); | |
} | |
/** | |
* Returns a new battenburg rotated 90 degress counter-clockwise. | |
*/ | |
Battenburg.prototype.rotate_cc = function(){ | |
return new Battenburg(this.b, this.d, this.a, this.c); | |
} | |
Battenburg.prototype.divide_by_scalar = function(div) { | |
return new Battenburg(this.a / div, this.b / div, this.c / div, this.d /div) | |
} | |
Battenburg.prototype.add = function(bb) { | |
return new Battenburg(this.a + bb.a, this.b + bb.b, this.c + bb.c, this.d + bb.d) | |
} | |
/** | |
* This is recursive function for calculating the | |
* length of the hilbert curve required to get to | |
* the point (x,y). | |
* | |
* The third parameter is optional - it defaults to | |
* the degree of precision required for doubles. | |
* | |
* The fourth parameter should not be specified - | |
* it defaults to the correct value. This parameter | |
* only exists because it is given non-default values | |
* during the recursion. | |
* | |
* @param {double} x - 0 <= x < 1 | |
* @param {double} y - 0 <= y < 1 | |
* @param {int} recursion - optional | |
* @param {Battenburg} curve - don't specify this | |
*/ | |
function hilbert_2d_to_1d(x, y, recursion, curve) { | |
//console.log(x, y, recursion, curve); | |
if (curve === undefined) { | |
curve = new Battenburg(0.0, 0.25, 0.75, 0.5); | |
} | |
if (recursion === undefined) { | |
recursion = 28; // a good number for doubles | |
} | |
if (recursion <= 0) { | |
return 0.0; | |
} | |
var retv = undefined; | |
if (x >= 0.0 && x < 0.5 && y >= 0.0 && y < 0.5) { | |
retv = curve.a | |
+ hilbert_2d_to_1d( x*2, y*2 | |
, recursion - 1 | |
, curve.mirror_x().rotate_c() | |
) / 4; | |
} | |
if (x >= 0.5 && x < 1.0 && y >= 0.0 && y < 0.5) { | |
retv = curve.b | |
+ hilbert_2d_to_1d( (x - 0.5)*2, y*2 | |
, recursion - 1 | |
, curve | |
) / 4; | |
} | |
if (x >= 0.0 && x < 0.5 && y >= 0.5 && y < 1.0) { | |
retv = curve.c | |
+ hilbert_2d_to_1d( x*2, (y - 0.5)*2 | |
, recursion - 1 | |
, curve.mirror_x().rotate_cc() | |
) / 4; | |
} | |
if (x >= 0.5 && x < 1.0 && y >= 0.5 && y < 1.0) { | |
retv = curve.d | |
+ hilbert_2d_to_1d( (x - 0.5)*2, (y - 0.5)*2 | |
, recursion - 1 | |
, curve | |
) / 4; | |
} | |
//console.log(x, y, recursion, curve); | |
//console.log("retv: " + retv); | |
return retv; | |
} | |
function hilbert_1d_to_2d(d, recursion, curve) { | |
console.log(d, recursion, curve); | |
if (curve === undefined) { | |
curve = new Battenburg(0.0, 0.25, 0.75, 0.5); | |
} | |
if (recursion === undefined) { | |
recursion = 28; // a good number for doubles | |
} | |
if (recursion <= 0) { | |
return [0, 0]; | |
} | |
var retv = undefined; | |
if (d >= curve.a && d < curve.a + 0.25) { | |
var d_ = (d - curve.a) * 4; | |
var adj = hilbert_1d_to_2d(d_, recursion - 1, curve.rotate_cc().mirror_x()); | |
retv = [0 + adj[0]/2, 0 + adj[1]/2]; | |
} | |
if (d >= curve.b && d < curve.b + 0.25) { | |
var d_ = (d - curve.b) * 4; | |
var adj = hilbert_1d_to_2d(d_, recursion - 1, curve); | |
retv = [0.5 + adj[0]/2, 0 + adj[1]/2]; | |
} | |
if (d >= curve.c && d < curve.c + 0.25) { | |
var d_ = (d - curve.c) * 4; | |
var adj = hilbert_1d_to_2d(d_, recursion - 1, curve.rotate_c().mirror_x()); | |
retv = [0 + adj[0]/2, 0.5 + adj[1]/2]; | |
} | |
if (d >= curve.d && d < curve.d + 0.25) { | |
var d_ = (d - curve.d) * 4; | |
var adj = hilbert_1d_to_2d(d_, recursion - 1, curve); | |
retv = [0.5 + adj[0]/2, 0.5 + adj[1]/2]; | |
} | |
console.log(d, recursion, curve); | |
console.log("retv: " + retv); | |
return retv; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<!DOCTYPE html> | |
<html> | |
<head> | |
<title>Hilbert Demo</title> | |
<style> | |
body { | |
margin: 0; | |
font-family: sans; | |
} | |
/* don't put space underneath for ascenders */ | |
svg { display: block; height: auto;} | |
path { | |
fill: none; stroke: black; | |
stroke-width: 0.001px; | |
} | |
input[type="number"] { | |
width: 3em; | |
} | |
#controls { | |
text-align: center; | |
} | |
</style> | |
<script type="text/javascript" src="hilbert.js"></script> | |
<script type="text/javascript"> | |
function engage() { | |
var inPoints = document.getElementById('points') | |
var inLocked = document.getElementById('locked') | |
var inDepth = document.getElementById('depth') | |
var pow4points = inPoints.value | |
var points = Math.pow(4,pow4points) | |
var depth | |
if(inLocked.checked) { | |
inDepth.disabled = true; | |
inDepth.value = pow4points; | |
} else { | |
inDepth.disabled = false; | |
} | |
depth = inDepth.value; | |
var dc = document.getElementById('democurve'); | |
dc.setAttribute('d','M0,0'); | |
for (var i = 1; i < points; i++){ | |
dc.setAttribute('d',dc.getAttribute('d')+'L'+hilbert_1d_to_2d(i/points,depth).join()); | |
} | |
} | |
</script> | |
</head> | |
<body onload="engage()"> | |
<div id="controls"> | |
<label for="points">Points: 4^</label> | |
<input id="points" type="number" step="1" min="1" max="8" value="4" oninput="engage()"> | |
<label for="locked">Locked</label> | |
<input id="locked" type="checkbox" checked onchange="engage()"> | |
<label for="depth">Depth: </label> | |
<input id="depth" type="number" disabled step="1" min="1" max="28" value="4" oninput="engage()"> | |
</div> | |
<svg viewBox="0 0 1 1"> | |
<path id="democurve" d='M0,0'> | |
</svg> | |
</body> | |
</html> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment