Skip to content

Instantly share code, notes, and snippets.

@daniarleagk

daniarleagk/.block

Last active May 10, 2021 14:09
Show Gist options
  • Save daniarleagk/278709dedf09451b794ff72c4c05cda1 to your computer and use it in GitHub Desktop.
Save daniarleagk/278709dedf09451b794ff72c4c05cda1 to your computer and use it in GitHub Desktop.
Download ZIP
Z-Order curve range query
Raw
.block
license: mit
height: 1024
Raw
README.md

This example is inspired by the post Z-Order Brush D3 Example. The Z-Order is a space filling curve (SFC) and a commonly used technique in databases to store and query multidimensional point data (Tropf et al., Orenstein et al., Geo-Wave). The basic query pattern is a multidimensional rectangular query. Since SFC generates a linear order for a data sets, the query box should be split into minimal number of segments (ranges) for efficient processing of rectangular query.

For a given query rectangle, we generate a minimal set of ranges that cover all points inside. The goal is to omit range segments that lie outside the query box, therefore avoiding unnecessary database scans (Tropf et al., Orenstein et al.). Data points can be stored and indexed according to their Z-order keys in any database that supports efficient range scans (e.g. relational Database, Apache HBase or Apache Accumulo, both are open source Google Bigtable implementation and support efficient range and parallel scans).

The algorithm follows “divide & conquer” pattern. We assume bit strings as an input. This algorithm is called with a map function as parameter and a query box represented by bit strings of lower left corner and upper right corner. For the sake of simplicity, we use a bit array (bit string) as a map function. E.g. [0,1,0,1,0,1,0] is a “classical” pattern to interleave 4 bits numbers.

The main idea of this algorithm is to check if the query box consists solely of one continuous curve segment. If this true, we stop and return a segment (in worst case this can be a single cell), otherwise we “cut” the query box along the hyperplane, resulting two smaller query boxes. Then we conduct the our algorithm on both of them. After processing both sides, we check if the segments can be combined in one continuous segment. In worst case we return a set (list) of single cell addresses, that covered by the query box (e.g. consider a horizontal line query).

Splitting algorithm can be described as recursive routine with the following steps (function getRanges(hyperPlanePosition, queryRec, mapFunction, highstBit)) :

  1. Check if a query box is a point: check if query box is a point. If yes, return this point as a segment.
  2. Check if a query box consists of a one continuous segment:We use the following fact to implement this check. If the Z-Bit-String of lower left point has the same prefix (that can be empty) as an upper right point and lower left corner has a suffix 00000...0000 and right upper corner has a suffix 11111...11111. If yes, return this segment.
  3. CutTheBox :( function cutBox(hyperplaneDimension, index, queryRec, mapFunction)) : “cuts” the box in two parts. Before we run this procedure, we compute the index of a first position where Z-Bit-String of lower left corner and Z-Bit-String of an upper right corner are different (and a suffix does not follow the pattern above). Then we define the hyperplane (dimension) for this index position and compute two new query boxes (“left” from hyperplane and “right” from hyperplane)
  4. Recursive Call: we call recursively for our procedure for a two new small query boxes (“left” call and “right” call).
  5. Merge: In last step we merge ranges from a both recursive calls in one list. Additionally, we check the last segment of the “left” call with a last segment of a “right” call whether they can be combined in one continuous segment if it could not. We append “right” list to the “left” one.
Raw
index.html
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8">
<title>Z-Order Curve</title>
<script
src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.3/jquery.min.js">
</script>
<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>
<div class="brushArea" style="float:left">&nbsp;</div>
<div class="debugSvg">&nbsp;</div>
<div class="debugArea"></div>
<script type="text/javascript">
/**
* init variables
*/
var w = 512, h = 512, scale = 32;
var minCellNumber = 0;
var maxCellNumber = w / scale - 1;
var zMapFunction = "01010101";
// "0101010101010101";
var resolution = 4;
/**
* compute bitString for x and y
* we take only a highest bits
*/
function mapToBitStrings(x, y, mapFunction) {
var xResolution = 0;
var yResolution = 0;
// compute x resolution
for (var i = 0; i < mapFunction.length; i++) {
var dimension = mapFunction.charAt(i);
if (dimension == "0") {// x dimension
xResolution++;
} else {
yResolution++;
}
}
//
var xBinaryString = x.toString(2);
// binary rep
var yBinaryString = y.toString(2);
// binary rep
// extend both string or cut
if (resolution > xBinaryString.length) {
var nullbits = "";
var diff = xResolution - xBinaryString.length;
for (var i = 0; i < diff; i++) {
nullbits = nullbits + "0";
}
xBinaryString = nullbits + xBinaryString;
}
//
if (resolution > yBinaryString.length) {
var nullbits = "";
var diff = yResolution - yBinaryString.length;
for (var i = 0; i < diff; i++) {
nullbits = nullbits + "0";
}
yBinaryString = nullbits + yBinaryString;
}
return {
"xBitString" : xBinaryString,
"yBitString" : yBinaryString
};
}
/**
*
*/
function computeZCodeBitString(xBinaryString, yBinaryString,
mapFunction) {
var key = "";
var bitsX = xBinaryString.length;
var bitsY = yBinaryString.length;
for (var i = 0; i < mapFunction.length; i++) {
var dimension = mapFunction.charAt(i);
var index;
var pointVal;
if (dimension == "0") {// x dimension
pointVal = xBinaryString;
index = xBinaryString.length - bitsX;
bitsX--;
} else {// y dimension
pointVal = yBinaryString;
index = xBinaryString.length - bitsY;
bitsY--;
}
if (index < pointVal.length) {
// get the current bit value
var bit = pointVal.charAt(index);
key = key + bit;
}
}
return key;
}
/**
* computes z code based on mapFunction points x,y e.g. mapfunction e.g.
* [0,1,0,1,0,1] number of bits used for the function
*/
function computeZCode(x, y, mapFunction) {
var bitStrings = mapToBitStrings(x, y, mapFunction);
var xBinaryString = bitStrings.xBitString;
var yBinaryString = bitStrings.yBitString;
return computeZCodeBitString(xBinaryString, yBinaryString,
mapFunction);
}
/**
* convert to bisString and optionally extend to the length of the mapfunction
*
*/
function toBitString(zCode, mapFunction) {
var zCodeString = zCode.toString(2);
if (mapFunction.length > zCodeString.length) {
var diff = mapFunction.length - zCodeString.length;
var nullbits = "";
for (var i = 0; i < diff; i++) {
nullbits = nullbits + "0";
}
return nullbits + zCodeString;
}
return zCodeString.substr(zCode.lenth - mapFunction.length,
mapFunction.length);
}
/**
* -1 function computes x
*/
function getBitXYStringsFromZCode(zBitString, mapFunction) {
var xString = "";
var yString = "";
for (var i = 0; i < mapFunction.length; i++) {
if (mapFunction.charAt(i) == "0") {// append to x
xString = xString + zBitString.charAt(i);
} else {// appen to y
yString = yString + zBitString.charAt(i);
}
}
return {
"xStr" : xString,
"yStr" : yString
};
}
/**
* Computes based on the zcode and coordinates the x and y values parameters are
* bit strings
*/
function getRanges(hyperPlanePosition, queryRec, mapFunction, highstBit) {
// query rec
var xLow = queryRec.xLow;
var yLow = queryRec.yLow;
var xHigh = queryRec.xHigh;
var yHigh = queryRec.yHigh;
// the same length z code
var zCodeLow = computeZCode(xLow, yLow, mapFunction);
var zCodeHigh = computeZCode(xHigh, yHigh, mapFunction);
// compute first index starting from hyperplane position such as values a
// diffrenet
// find i l highst bit of hightest dimension
var index = 0;
var hyperplaneDimension = "0";
// x
var hyperplaneCutIndex = [ -1, -1 ];
for (var i = 0; i < highstBit; i++) {
// count position in each dimension
hyperplaneDimension = mapFunction.charAt(i);
if (mapFunction.charAt(i) == "0") {// x dimesnion
hyperplaneCutIndex[0]++;
} else {// y dimension
hyperplaneCutIndex[1]++;
}
index = i;
if (zCodeHigh.charAt(i) != zCodeLow.charAt(i)) {
break;
}
}
// check conditions 1
if (index >= highstBit - 1) {
return [ {
"zl" : parseInt(zCodeLow, 2),
"zh" : parseInt(zCodeHigh, 2)
} ];
}
// check condition 2
var allOnes = true;
var allNulls = true;
for (var i = index; i < highstBit; i++) {
if (zCodeHigh.charAt(i) != "1") {
allOnes = false;
break;
}
if (zCodeLow.charAt(i) != "0") {
allNulls = false;
break;
}
}
if (allOnes && allNulls) {
return [ {
"zl" : parseInt(zCodeLow, 2),
"zh" : parseInt(zCodeHigh, 2)
} ];
}
// both conditions not fulfilled cut the box along the hyperplane
var queryBoxes = cutBox(hyperplaneDimension, hyperplaneCutIndex,
queryRec, mapFunction);
// recursive call left
var rangesLeft = getRanges(hyperPlanePosition, queryBoxes[0],
mapFunction, highstBit);
var rangesRight = getRanges(hyperPlanePosition, queryBoxes[1],
mapFunction, highstBit);
// merge : last und first check
var lastLeft = rangesLeft[rangesLeft.length - 1].zh;
var firstRight = rangesRight[0].zl;
if (firstRight - lastLeft == 1) {
var mergeRange = {
"zl" : rangesLeft[rangesLeft.length - 1].zl,
"zh" : rangesRight[0].zh
};
rangesLeft[rangesLeft.length - 1] = mergeRange;
for (var i = 1; i < rangesRight.length; i++) {
rangesLeft.push(rangesRight[i]);
}
} else {
for (var i = 0; i < rangesRight.length; i++) {
rangesLeft.push(rangesRight[i]);
}
}
return rangesLeft;
}
/**
*
*/
function cutBox(hyperplaneDimension, index, queryRec, mapFunction) {
// query rec convert to strings
var lowStrings = mapToBitStrings(queryRec.xLow, queryRec.yLow,
mapFunction);
var highStrings = mapToBitStrings(queryRec.xHigh, queryRec.yHigh,
mapFunction);
// firts box below the hyperpale
var x1Low = lowStrings.xBitString.slice(0);
var y1Low = lowStrings.yBitString.slice(0);
var x1High = highStrings.xBitString.slice(0);
var y1High = highStrings.yBitString.slice(0);
// new coordinates
if (hyperplaneDimension == "0") {// x
// set bit to 0
x1High = simpleReplaceAndFill(index[0], x1High, "0", "1"); // remain
// part
// 0111111
} else {
// set bit to 0
y1High = simpleReplaceAndFill(index[1], y1High, "0", "1"); // remain
// part
// 0111111
}
// second box above the hyperplane
var x2Low = lowStrings.xBitString.slice(0);
var y2Low = lowStrings.yBitString.slice(0);
var x2High = highStrings.xBitString.slice(0);
var y2High = highStrings.yBitString.slice(0);
if (hyperplaneDimension == "0") {// x
// set bit to 1
x2Low = simpleReplaceAndFill(index[0], x2Low, "1", "0"); // remain
// part
// 1000000
} else {
// set bit to 1
y2Low = simpleReplaceAndFill(index[1], y2Low, "1", "0"); // remain
// part
// 100000
}
var queryBoxes = [ {
"xLow" : parseInt(x1Low, 2),
"yLow" : parseInt(y1Low, 2),
"xHigh" : parseInt(x1High, 2),
"yHigh" : parseInt(y1High, 2)
}, {
"xLow" : parseInt(x2Low, 2),
"yLow" : parseInt(y2Low, 2),
"xHigh" : parseInt(x2High, 2),
"yHigh" : parseInt(y2High, 2)
} ];
return queryBoxes;
}
/**
* string replacement
*/
function simpleReplaceAt(pos, source, c) {
return source.substr(0, pos) + c + source.substr(pos + 1);
}
/**
*
*/
function simpleReplaceAndFill(pos, source, c, fillc) {
var prefix = source.substr(0, pos) + c;
var f = "";
for (var i = pos + 1; i < source.length; i++) {
f = f + fillc;
}
return prefix + f;
}
/**
*
*/
function drawRec(queryRec) {
var path = [];
path.push({
"x" : parseInt(queryRec.xLow, 2),
"y" : parseInt(queryRec.yLow, 2)
});
path.push({
"x" : parseInt(queryRec.xLow, 2),
"y" : parseInt(queryRec.yHigh, 2)
});
path.push({
"x" : parseInt(queryRec.xHigh, 2),
"y" : parseInt(queryRec.yHigh, 2)
});
path.push({
"x" : pasreInt(queryRec.xHigh, 2),
"y" : parseInt(queryRec.yLow, 2)
});
path.push({
"x" : parseInt(queryRec.xLow, 2),
"y" : parseInt(queryRec.yLow, 2)
});
return path;
}
/**
*
* compute zvalue array
*/
function buildPath(mapFunction, resolution) {
var path = [];
var maxPoints = (1 << resolution) * (1 << resolution) - 1;
return buildPathFromRange(0, maxPoints, mapFunction);
}
/**
*
* compute zvalue array
*/
function buildPathFromRange(min, max, mapFunction) {
var path = [];
for (var x = min; x <= max; x++) {
var zString = toBitString(x.toString(2), mapFunction);
var coord = getBitXYStringsFromZCode(zString, mapFunction);
path.push({
"x" : parseInt(coord.xStr, 2) * scale,
"y" : parseInt(coord.yStr, 2) * scale
});
}
return path;
}
/**
* window definition
*/
function brushed() {
var extent = brush.extent();
var xLow = Math.round(extent[0][0] / scale);
var yLow = Math.round(extent[0][1] / scale);
var xHigh = Math.round(extent[1][0] / scale);
var yHigh = Math.round(extent[1][1] / scale);
// check if within area
if (xLow > maxCellNumber)
xLow = maxCellNumber;
if (yLow > maxCellNumber)
yLow = maxCellNumber;
if (xHigh > maxCellNumber)
xHigh = maxCellNumber;
if (yHigh > maxCellNumber)
yHigh = maxCellNumber;
// get path
var lowZ = parseInt(computeZCode(xLow, yLow, zMapFunction), 2);
var highZ = parseInt(computeZCode(xHigh, yHigh, zMapFunction), 2);
// compute rangess
var queryBox = {
"xLow" : xLow,
"yLow" : yLow,
"xHigh" : xHigh,
"yHigh" : yHigh
};
var ranges = getRanges(0, queryBox, zMapFunction,
zMapFunction.length - 1);
$(".debugArea").html(
"<p> XLow:" + xLow + " YLow " + yLow + " XHigh " + xHigh
+ " YHigh " + yHigh + " LowZ " + lowZ + " HighZ "
+ highZ + "</p>");
d3.select(".debugSvg").selectAll("svg").remove();
var svgArea = d3.select(".debugSvg").append("svg").attr("width", w)
.attr("height", h);
for (var i = 0; i < ranges.length; i++) {
var min = ranges[i].zl;
var max = ranges[i].zh;
var stroke = "blue";
//if (i % 2 == 0) {
// stroke = "blue";
//}
svgArea.append("path").attr("d",
line(buildPathFromRange(min, max, zMapFunction))).attr(
"stroke", stroke).attr("stroke-width", 2).attr("fill",
"none");
}
}
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 ] ]);
/**
* main line ge
*/
// line generator
var line = d3.svg.line().x(function(d) {
return d.x;
}).y(function(d) {
return d.y;
}).interpolate("linear");
var svg = d3.select(".brushArea").append("svg").attr("width", w).attr(
"height", h);
svg.append("path").attr("d", line(buildPath(zMapFunction, resolution)))
.attr("stroke", "#333").attr("stroke-width", 1).attr("fill",
"none");
//
svg.append("g").attr("class", "brush").call(brush);
</script>
<!-- <script type="text/javascript" src="js/skript.js"></script> -->
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment