Skip to content

Instantly share code, notes, and snippets.

@jaredwinick
Last active January 26, 2023 21:54
Show Gist options
  • Save jaredwinick/5073432 to your computer and use it in GitHub Desktop.
Save jaredwinick/5073432 to your computer and use it in GitHub Desktop.
Z-Order Curve with Query

Z-Order curves are used to encode multiple dimensions to one dimension while maintaining locality. This feature makes them useful for indexing multidimensional data such as geospatial data. In BigTable-like systems (Accumulo, HBase, Cassandra a z-order curve index can translate a bounding box query to a single range scan. As this example shows, sometimes the locality properties of the curve are very good and few points outside the bounding box are scanned. Other times though, many points outside the bounding box are scanned if using a single range.

This example was inspired by Mike Bostock's Quadtree example

<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8">
<title>Z-Order Curve</title>
<script src="http://d3js.org/d3.v3.min.js"></script>
<style type="text/css">
body {
background: #fff;
}
.brush .extent {
stroke: #fff;
fill-opacity: .125;
shape-rendering: crispEdges;
}
</style>
</head>
<body>
<script type="text/javascript">
var w = 1200,
h = 800,
scale = 8;
var brush = d3.svg.brush()
.x(d3.scale.identity().domain([0, w]))
.y(d3.scale.identity().domain([0, h]))
.on("brush", brushed)
.extent([[100, 100], [200, 200]]);
// http://stackoverflow.com/questions/4909263/how-to-efficiently-de-interleave-bits-inverse-morton
deinterleave = function(x)
{
x = x & 0x55555555;
x = (x | (x >> 1)) & 0x33333333;
x = (x | (x >> 2)) & 0x0F0F0F0F;
x = (x | (x >> 4)) & 0x00FF00FF;
x = (x | (x >> 8)) & 0x0000FFFF;
return x;
}
// http://graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN
interleave = function(x, y) {
var B = [0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF];
var S = [1, 2, 4, 8];
x = (x | (x << S[3])) & B[3];
x = (x | (x << S[2])) & B[2];
x = (x | (x << S[1])) & B[1];
x = (x | (x << S[0])) & B[0];
y = (y | (y << S[3])) & B[3];
y = (y | (y << S[2])) & B[2];
y = (y | (y << S[1])) & B[1];
y = (y | (y << S[0])) & B[0];
z = x | (y << 1);
return z;
}
// Builds the x,y points for the z curve with the given range of values
buildCurve = function(startZ, endZ) {
var curve = [];
for ( var z = startZ; z < endZ; ++z ) {
var x = deinterleave(z);
var y = deinterleave(z >> 1);
curve.push( {"x" : x*scale, "y" : y*scale} );
}
return curve;
}
var lineFunction = d3.svg.line()
.x(function(d) { return d.x; })
.y(function(d) { return d.y; })
.interpolate("linear");
var svg = d3.select("body").append("svg")
.attr("width", w)
.attr("height", h);
svg.append("path")
.attr("d", lineFunction( buildCurve(0, 30000) ))
.attr("stroke", "#333")
.attr("stroke-width", 1)
.attr("fill", "none");
svg.append("path")
.attr("class", "scanned")
.attr("stroke", "#f00")
.attr("stroke-width", 1)
.attr("fill", "none");
svg.append("g")
.attr("class", "brush")
.call(brush);
brushed();
function brushed() {
var extent = brush.extent();
// get the z values for the extent
zUL = zFromPoint( Math.round(extent[0][0]/scale), Math.round(extent[0][1]/scale) );
zLR = zFromPoint( Math.round(extent[1][0]/scale), Math.round(extent[1][1]/scale) );
// Set the data for the scanned path
svg.selectAll(".scanned")
.attr("d", lineFunction( buildCurve(zUL, zLR) ))
}
function zFromPoint(x, y) {
return interleave(x, y);
}
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment