Skip to content

Instantly share code, notes, and snippets.

@stuartpb
Forked from rbedia/hilbert.js
Created August 10, 2012 20:59
Show Gist options
  • Save stuartpb/3317841 to your computer and use it in GitHub Desktop.
Save stuartpb/3317841 to your computer and use it in GitHub Desktop.
Hilbert demo
/*
* 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;
}
<!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