Skip to content

Instantly share code, notes, and snippets.

@schnerd

schnerd/.block

Created April 24, 2018 16:46
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save schnerd/d50c3d8faab9f73310004ef72a5db8f4 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save schnerd/d50c3d8faab9f73310004ef72a5db8f4 to your computer and use it in GitHub Desktop.
Download ZIP
Hilbert Curve with Query
Raw
.block
license: mit
Raw
README.md
Raw
hilbert-demo.js
function hilbertDemo() {
var svg = d3.select('svg#hilbert-chart'),
canvasWidth = Math.min(window.innerWidth, window.innerHeight - 100),
hilbert,
order = 6,
brushSelection = [
[canvasWidth * 0.1, canvasWidth * 0.1],
[canvasWidth * 0.45, canvasWidth * 0.45]
];
function d3Digest() {
var hilbertData = {
start: 0,
length: Math.pow(4, order)
};
hilbert.order(order).layout(hilbertData);
svg.selectAll('.skeleton, .main-path')
.datum(hilbertData)
.attr('d', function(d) { return getHilbertPath(d.pathVertices); })
.attr('transform', transform);
if (brushSelection) {
var hilbertRange = getHilbertRange();
var hilbertHighlightData = {
start: hilbertRange[0],
length: hilbertRange[1] - hilbertRange[0]
};
hilbert.layout(hilbertHighlightData);
svg.selectAll('.highlight-path')
.datum(hilbertHighlightData)
.attr('d', function(d) { return getHilbertPath(d.pathVertices); })
.attr('transform', transform);
}
function transform(d) {
return 'scale('+ d.cellWidth + ') '
+ 'translate(' + (d.startCell[0] +.5) + ',' + (d.startCell[1] +.5) + ')';
}
/**
* Computing the hilbert distance for each of the four bounding box corners
* alone is not enough. There may be another point on the perimeter of the
* bounding box that has a lower/higher distance. This function generates
* a list of points around the perimeter and then computes the hilbert
* distance for each of those points to get a better idea of the full range
* we'd need to scan.
*/
function getHilbertRange() {
var increment = 1;
var xExtent = [brushSelection[0][0], brushSelection[1][0]];
var yExtent = [brushSelection[0][1], brushSelection[1][1]];
// Generate points around the perimeter from bounding box
var points = [];
for (var x = xExtent[0]; x <= xExtent[1]; x+= increment) {
points.push([x, yExtent[0]]);
points.push([x, yExtent[1]]);
}
for (var y = yExtent[0]; y <= yExtent[1]; y+= increment) {
points.push([xExtent[0], y]);
points.push([xExtent[1], y]);
}
// Convert to hilbert distances (distance along the curve)
var distances = points.map(p => hilbert.getValAtXY.apply(hilbert, p))
var start = Math.min.apply(null, distances);
var end = Math.max.apply(null, distances);
return [start, end];
}
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 orderChange(newOrder) {
order = newOrder;
d3Digest();
}
function init() {
hilbert = d3.hilbert()
.order(order)
.canvasWidth(canvasWidth)
.simplifyCurves(false);
var brush = d3.brush()
.on("brush", brushed)
.extent([[0, 0], [canvasWidth, canvasWidth]]);
function brushed() {
brushSelection = d3.event.selection;
d3Digest();
}
svg.attr("width", canvasWidth).attr("height", canvasWidth);
var canvas = svg.append('g');
canvas.append('path').attr('class', 'skeleton');
canvas.append('path').attr('class', 'main-path');
canvas.append('path').attr('class', 'highlight-path');
var brushNode = canvas.append("g").attr("class", "brush").call(brush);
brush.move(brushNode, brushSelection);
// Canvas zoom/pan
svg.call(d3.zoom()
.translateExtent([[0, 0], [canvasWidth, canvasWidth]])
.scaleExtent([1, Infinity])
.on("zoom", function() {
canvas.attr("transform", d3.event.transform);
})
);
// Value Tooltip
var valTooltip = d3.select('#val-tooltip');
svg.on('mouseover', function() { valTooltip.style("display", "inline"); })
.on('mouseout', function() { valTooltip.style("display", "none"); })
.on('mousemove', function () {
var coords = d3.mouse(canvas.node());
console.log(coords);
valTooltip.text(hilbert.getValAtXY(coords[0], coords[1]))
.style('left', d3.event.pageX)
.style('top', d3.event.pageY);
});
// Order slider
$('input#hilbert-order').slider({
step: 1,
max: 9,
min: 0,
value: order,
tooltip: 'always',
tooltip_position: 'bottom',
formatter: function(d) {
return 'Order: ' + d;
}
}).on('change', function(e) {
orderChange(e.value.newValue);
});
d3Digest();
}
init();
}
Raw
index.html
<head>
<script src="//code.jquery.com/jquery-3.1.0.min.js"></script>
<script src="//cdnjs.cloudflare.com/ajax/libs/d3/4.2.6/d3.min.js"></script>
<script src="//cdnjs.cloudflare.com/ajax/libs/bootstrap-slider/9.1.3/bootstrap-slider.min.js"></script>
<script src="//unpkg.com/[email protected]/build/d3-hilbert.min.js"></script>
<script src="hilbert-demo.js"></script>
<link rel="stylesheet" href="//maxcdn.bootstrapcdn.com/bootstrap/3.3.7/css/bootstrap.min.css">
<link rel="stylesheet" href="//cdnjs.cloudflare.com/ajax/libs/bootstrap-slider/9.1.3/css/bootstrap-slider.min.css">
<style>
body {
text-align: center;
}
svg {
margin: 10px;
}
path.main-path {
fill: none;
stroke: #3A5894;
stroke-width: 0.2;
stroke-linecap: square;
}
path.highlight-path {
fill: none;
stroke: #ff0000;
stroke-width: 0.2;
stroke-linecap: square;
}
path.skeleton {
fill: none;
stroke: #EEE;
stroke-width: 0.1;
}
#val-tooltip {
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;
}
.brush .selection {
stroke: none;
}
</style>
</head>
<body>
<svg id="hilbert-chart"></svg>
<div id="hilbert-controls">
<input id="hilbert-order" />
</div>
<div id="val-tooltip"></div>
<script>
hilbertDemo();
</script>
</body>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment