This is a first step to a visual and numeric comparison of Morton and Hilbert curves, in the context of geocode systems. The D3 animations are using vasturiano/d3-morton-order and vasturiano/d3-hilbert libraries.
This gist is only a interface test.
license: mit |
This is a first step to a visual and numeric comparison of Morton and Hilbert curves, in the context of geocode systems. The D3 animations are using vasturiano/d3-morton-order and vasturiano/d3-hilbert libraries.
This gist is only a interface test.
function hilbertDemo() { | |
var refWidth = parseInt( document.getElementById('reftab').getBoundingClientRect().width/2.0 ); | |
var svg = d3.select('svg#hilbert-chart'), | |
canvasWidth = Math.min(window.innerWidth, refWidth), //changed | |
hilbert; | |
function d3Digest() { | |
var hilbertData = { | |
start: 0, | |
length: Math.pow(4, globOrder) | |
}; | |
hilbert.order(globOrder).layout(hilbertData); | |
svg.selectAll('path') | |
.datum(hilbertData) | |
.attr('d', function(d) { return getHilbertPath(d.pathVertices); }) | |
.attr('transform', function(d) { | |
return 'scale('+ d.cellWidth + ') ' | |
+ 'translate(' + (d.startCell[0] +.5) + ',' + (d.startCell[1] +.5) + ')'; | |
}); | |
svg.select('path:not(.skeleton)') | |
.transition().duration(globOrder * 1000).ease(d3.easePoly) | |
.attrTween('stroke-dasharray', tweenDash); | |
function getHilbertPath(vertices) { | |
var path = 'M0 0L0 0'; | |
vertices.forEach(function(vert) { | |
switch(vert) { | |
case 'U': path += 'v-1'; break; | |
case 'D': path += 'v1'; break; | |
case 'L': path += 'h-1'; break; | |
case 'R': path += 'h1'; break; | |
} | |
}); | |
return path; | |
} | |
function tweenDash() { | |
var l = this.getTotalLength(), | |
i = d3.interpolateString("0," + l, l + "," + l); | |
return function(t) { return i(t); }; | |
} | |
} | |
hilbertDemo.d3Digest = d3Digest; // globalize reference | |
function init() { | |
hilbert = d3.hilbert() | |
.order(globOrder) | |
.canvasWidth(canvasWidth) | |
.simplifyCurves(false); | |
svg.attr("width", canvasWidth).attr("height", canvasWidth); | |
var canvas = svg.append('g'); | |
canvas.append('path').attr('class', 'skeleton'); | |
canvas.append('path'); | |
// Canvas zoom/pan | |
svg.call(d3.zoom() | |
.translateExtent([[0, 0], [canvasWidth, canvasWidth]]) | |
.scaleExtent([1, Infinity]) | |
.on("zoom", function() { | |
if (xzoomNode.value==1) canvas.attr("transform", d3.event.transform); | |
}) | |
); | |
// Value Tooltip | |
var valTooltip = d3.select('#val-tooltip2'); | |
svg.on('mouseover', function() { valTooltip.style("display", "inline"); }) | |
.on('mouseout', function() { valTooltip.style("display", "none"); }) | |
.on('mousemove', function () { | |
var coords = d3.mouse(canvas.node()); | |
var halfdigits = Math.ceil(globOrder/2); | |
var vv = hilbert.getValAtXY(coords[0], coords[1]); | |
var vv4 = parseInt(vv).toString(4).padStart(globOrder,'0'); | |
var vv32 = parseInt(vv).toString(32).padStart(halfdigits,'0'); | |
if (globOrder%2) vv32="-"; | |
valTooltip.html( "decimal: <code>"+vv +"</code><br/>quaternary: <code>"+vv4 +"</code><br/>base32: <code>"+vv32+"</code>" ) | |
//valTooltip.text(hilbert.getValAtXY(coords[0], coords[1])) | |
.style('left', d3.event.pageX+'px') | |
.style('top', d3.event.pageY+'px'); | |
}); | |
// Order slider | |
d3Digest(); | |
} | |
init(); | |
} |
<!DOCTYPE html> | |
<html> | |
<head> | |
<meta charset="utf-8"/> | |
<meta name="viewport" content="width=1000"/> | |
<title>Sp-filling curves, compare</title> | |
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/4.2.6/d3.min.js"></script> | |
<script src="https://unpkg.com/d3-simple-slider"></script> | |
<script src="https://unpkg.com/d3-morton"></script> | |
<script src="morton-demo.js"></script> | |
<script src="https://unpkg.com/d3-hilbert"></script> | |
<script src="hilbert-demo.js"></script> | |
<style> | |
body { | |
text-align: center; | |
} | |
table { | |
padding:10px; | |
border-bottom: 1px solid #ddd; | |
border-top: 1px solid #ddd; | |
} | |
svg { | |
margin: 10px; | |
} | |
svg path { | |
fill: none; | |
stroke: #3A5894; | |
stroke-width: 0.25; | |
stroke-linecap: square; | |
} | |
svg path.skeleton { | |
stroke: #EEE; | |
stroke-width: 0.1; | |
} | |
#val-tooltip1, #val-tooltip2 { | |
display: none; | |
position: absolute; | |
margin-top: 22px; | |
margin-left: -1px; | |
padding: 5px; | |
border-radius: 3px; | |
font: 11px sans-serif; | |
color: #eee; | |
background: rgba(0,0,140,0.9); | |
text-align: center; | |
pointer-events: none; | |
} | |
</style> | |
</head> | |
<body> | |
<a href="https://en.wikipedia.org/wiki/Space-filling_curve">Space-filling curve</a> <b>order</b>: | |
<!-- span id="xxvalue"></span --> | |
<select id="xvalue" onchange="changeOrder(this.value)"> | |
<option>1<option selected>2<option>3<option>4 | |
<option>5<option>6<option>8 | |
</select> | |
Zoom/pan: | |
<select id="xzoom"> | |
<option value="1" selected>Enable | |
<option value="0">Disable | |
</select> <small>(hover over the picture)</small> | |
<br/> <br/> | |
<h3>Quadrilateral (base4 codes)</h3> | |
<table id="reftab" border="0" width="60%" align="center"> | |
<tr> | |
<td><a href="https://en.wikipedia.org/wiki/Z-order_curve">MORTON</a><br/> | |
<svg id="morton-chart"></svg> | |
<div id="val-tooltip1"></div> | |
</td> | |
<td><a href="https://en.wikipedia.org/wiki/Hilbert_curve">HILBERT CURVE</a><br/> | |
<svg id="hilbert-chart"></svg> | |
<div id="val-tooltip2"></div> | |
</td> | |
</tr> | |
</table> | |
<script> | |
var globOrder = 2; // need also to change selected option | |
var xzoomNode = document.getElementById('xzoom'); | |
mortonDemo(); // morton-demo.js | |
hilbertDemo(); // hilbert-demo.js | |
function changeOrder(v) { | |
globOrder = v; // order change to new value | |
mortonDemo.d3Digest(); | |
hilbertDemo.d3Digest(); | |
} | |
</script> | |
<p>The curve with the <b>best code prefix preservation</b>? Less average distance? <br/> Seems Hilbert... Check base32 codes on Order-6. But we need to proff: the next gist will be it. | |
<br/>... And about hexagon, how to compare? Please help us to do it! </p> | |
<br/><h3>Hexagonal (base7 codes)</h3> | |
<img src="http://osm.codes/_foundations/hexagonalCell-geocode3c.png" width="90%"/> | |
</body> | |
</html> |
function mortonDemo() { | |
var refWidth = parseInt( document.getElementById('reftab').getBoundingClientRect().width/2.0 ); | |
var svg = d3.select('svg#morton-chart'), | |
canvasWidth = Math.min(refWidth, window.innerWidth ), //old Math.min(window.innerWidth, window.innerHeight - 100), | |
zOrder; | |
function d3Digest() { | |
var zOrderData = { | |
start: 0, | |
length: Math.pow(4, globOrder) | |
}; | |
zOrder.order(globOrder).layout(zOrderData); | |
svg.selectAll('path') | |
.datum(zOrderData) | |
.attr('d', function(d) { return getZOrderPath(d.pathVertices); }) | |
.attr('transform', function(d) { | |
return 'scale('+ d.cellWidth + ') ' | |
+ 'translate(' + (d.pathVertices[0][0] +.5) + ',' + (d.pathVertices[0][1] +.5) + ')'; | |
}); | |
svg.select('path:not(.skeleton)') | |
.transition().duration(globOrder * 1000).ease(d3.easePoly) | |
.attrTween('stroke-dasharray', tweenDash); | |
function getZOrderPath(vertices) { | |
var path = 'M0 0L0 0'; | |
vertices.forEach(function(vert) { | |
path += 'L' + vert.join(','); | |
}); | |
return path; | |
} | |
function tweenDash() { | |
var l = this.getTotalLength(), | |
i = d3.interpolateString("0," + l, l + "," + l); | |
return function(t) { return i(t); }; | |
} | |
} | |
mortonDemo.d3Digest = d3Digest; // globalize reference | |
function init() { | |
zOrder = d3.zOrder() | |
.order(globOrder) | |
.canvasWidth(canvasWidth) | |
.simplifyCurves(false); | |
svg.attr("width", canvasWidth).attr("height", canvasWidth); | |
var canvas = svg.append('g'); | |
canvas.append('path').attr('class', 'skeleton'); | |
canvas.append('path'); | |
// Canvas zoom/pan | |
svg.call(d3.zoom() | |
.translateExtent([[0, 0], [canvasWidth, canvasWidth]]) | |
.scaleExtent([1, Infinity]) | |
.on("zoom", function() { | |
if (xzoomNode.value==1) canvas.attr("transform", d3.event.transform); | |
}) | |
); | |
// Value Tooltip | |
var valTooltip = d3.select('#val-tooltip1'); | |
svg.on('mouseover', function() { valTooltip.style("display", "inline"); }) | |
.on('mouseout', function() { valTooltip.style("display", "none"); }) | |
.on('mousemove', function () { | |
var coords = d3.mouse(canvas.node()); | |
var halfdigits = Math.ceil(globOrder/2); | |
var vv = zOrder.getValAtXY(coords[0], coords[1]); | |
var vv4 = parseInt(vv).toString(4).padStart(globOrder,'0'); | |
var vv32 = parseInt(vv).toString(32).padStart(halfdigits,'0'); | |
if (globOrder%2) vv32="-"; | |
valTooltip.html( "decimal: "+vv +"<br/>quaternary: "+vv4 +"<br/>base32: "+vv32 ) | |
.style('left', d3.event.pageX+"px") | |
.style('top', d3.event.pageY+"px"); | |
}); | |
d3Digest(); | |
} | |
init(); | |
} |