Skip to content

Instantly share code, notes, and snippets.

@w8r

w8r/Readme.md

Last active November 13, 2020 13:07
Show Gist options
  • Save w8r/d4660e6acbf56a0ad6b06e491afeec65 to your computer and use it in GitHub Desktop.
Save w8r/d4660e6acbf56a0ad6b06e491afeec65 to your computer and use it in GitHub Desktop.
Download ZIP
Spatial hash on morton curve
Raw
Readme.md

Spatial hash on morton curve

Virtual grid with that works like a flat spatial index

Raw
index.html
<!DOCTYPE html>
<html>
<head>
<title>Z-curve hash for boxes and segments with range queries</title>
<script type="text/javascript" src="https://unpkg.com/splaytree@0.1.1/dist/splay.js"></script>
<script type="text/javascript" src="https://unpkg.com/liang-barsky@1.0.1/dist/liang-barsky.js"></script>
<script type="text/javascript" src="https://unpkg.com/d3-quadtree@1.0.3"></script>
<script type="text/javascript" src="https://unpkg.com/d3-dispatch@1.0.3/build/d3-dispatch.js"></script>
<script type="text/javascript" src="https://unpkg.com/d3-timer@1.0.7/build/d3-timer.js"></script>
<script type="text/javascript" src="https://unpkg.com/d3-collection@1.0.4/build/d3-collection.js"></script>
<script type="text/javascript" src="https://unpkg.com/d3-force@1.1.0/build/d3-force.js"></script>
<script type="text/javascript" src="https://unpkg.com/bresenham-zingl@0.1.0/dist/bresenham.js"></script>
<script type="text/javascript" src="https://unpkg.com/bezier-intersect@0.0.1/dist/bezier-intersect.js"></script>
<script type="text/javascript" src="morton.js"></script>
<script type="text/javascript" src="ubtree.js"></script>
<style type="text/css">
body, html, #canvas {
width: 100%;
height: 100%;
margin: 0;
padding: 0;
}
body {
background: #ddd;
font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;
}
#canvas {
background: #fff;
}
#control {
position: absolute;
top: 20px;
right: 20px;
background: #fff;
box-shadow: 0 0 5px rgba(80,80,80, 0.5);
padding: 5px 10px;
border-radius: 5px;
}
#control p {
padding: 0;
margin: 4px;
}
#range {
position: absolute;
bottom: 20px;
left: 20px;
width: 90%;
}
#indicator {
position: absolute;
bottom: 50px;
right: 20px;
left: 20px;
font-size: 1.5em;
font-weight: 300;
color: #222222;
}
</style>
</head>
<body>
<canvas id="canvas"></canvas>
<input type="range" id="range" min="10" max="10000" value="1000" />
<div id="indicator">1000</div>
<form id="control">
<p><label><input type="checkbox" name="nodes" checked> nodes</label></p>
<p><label><input type="checkbox" name="edges" checked> edges</label></p>
<p><label><input type="checkbox" name="grid"> grid</label></p>
<p><label><select name="level">
<option value="1">1</option>
<option value="2">2</option>
<option value="3">3</option>
<option value="4">4</option>
<option value="5">5</option>
<option value="6">6</option>
<option value="7">7</option>
<option value="8" selected>8</option>
<option value="9">9</option>
<option value="10">10</option>
<option value="11">11</option>
<option value="12">12</option>
</select> level</label></p>
</form>
<script type="text/javascript" src="index.js"></script>
</body>
</html>
Raw
index.js
const screenWidth = document.documentElement.clientWidth;
const screenHeight = document.documentElement.clientHeight;
const pxRatio = window.devicePixelRatio;
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const w = canvas.width = screenWidth * devicePixelRatio;
const h = canvas.height = screenHeight * devicePixelRatio;
const stats = {
queries: 0,
totalTime: 0,
getAverage() {
return `${this.totalTime / this.queries}ms`;
},
clear() {
this.totalTime = this.queries = 0;
}
};
canvas.style.width = screenWidth + 'px';
canvas.style.height = screenHeight + 'px';
function scaleGraphToFitBounds(G, bounds) {
var min = Math.min, max = Math.max;
var bbox = getBounds(G);
var cx = (bounds[0] + bounds[2]) / 2,
cy = (bounds[1] + bounds[3]) / 2,
gcx = (bbox[0] + bbox[2]) / 2,
gcy = (bbox[1] + bbox[3]) / 2;
var tx = cx - gcx,
ty = cy - gcy;
var scale = min(
(bounds[2] - bounds[0]) / (bbox[2] - bbox[0]),
(bounds[3] - bounds[1]) / (bbox[3] - bbox[1])
);
G.nodes.forEach(function (n) {
n.x = cx + ((n.x + tx) - cx) * scale;
n.y = cy + ((n.y + ty) - cy) * scale;
});
}
function getBounds(g) {
return g.nodes.reduce((b, n) => {
b[0] = Math.min(b[0], n.x);
b[1] = Math.min(b[1], n.y);
b[2] = Math.max(b[2], n.x);
b[3] = Math.max(b[3], n.y);
return b;
}, [Infinity, Infinity, -Infinity, -Infinity]);
}
function generateDenseTree(N = 550, width = 1000, height = 1000) {
let counter = 0;
return {
nodes: new Array(N).fill(0).map(function(_, i) {
counter++;
return {
id: i,
text: 'Node #' + i,
x: Math.random() * width,
y: Math.random() * height,
r: 3 + Math.random() * 8
};
}),
edges: new Array(N - 1).fill(0).map(function(_, i) {
counter++;
return {
id: i,
curvature: (i % 3 === 0) ? 1 : 1,
//curvature: 0,
source: Math.floor(Math.sqrt(i)),
target: i + 1
};
})
};
}
var N = 1000;
var data, nodesMap, simulation;
const SZ = 5;
var flatStorage;
let foundNodes = [];
let foundEdges = [];
let selectedNode = null;
let showIndex = false;
function populate(n) {
N = n;
foundNodes = [];
foundEdges = [];
selectedNode = null;
if (simulation) simulation.stop();
data = generateDenseTree(N, w, h);
nodesMap = data.nodes.reduce((a, n) => {
a[n.id] = n;
return a;
}, {});
flatStorage = new Float32Array(SZ * 2 * N);
simulation = layout(data, onLayoutDone);
}
const qBounds = [0, 0, 0, 0];
function render() {
ctx.clearRect(0, 0, w, h);
if (showIndex) {
ctx.lineWidth = 0.5;
renderIndex();
ctx.lineWidth = 1;
ctx.beginPath();
U._checkedNodes.forEach((n) => {
const b = U.keyToBBox(n.key);
ctx.rect(b[0], b[1], b[2] - b[0], b[3] - b[1]);
});
ctx.globalAlpha = 0.2;
ctx.fillStyle = 'blue';
ctx.fill();
ctx.globalAlpha = 1;
}
const Nn = data.nodes.length;
// const { nodes, edges } = U.size === 0 ? data : U.query([0, 0, w, h])
// .reduce((a, id) => {
// if (!a.ids[id]) {
// a.ids[id] = true;
// if (id >= Nn) a.edges.push(data.edges[id - Nn]);
// else a.nodes.push(data.nodes[id]);
// }
// return a;
// }, { nodes: [], edges: [], ids: {} });
const { nodes, edges } = data;
// edges
ctx.beginPath();
ctx.strokeStyle = '#707070';
edges.forEach((e) => {
const s = nodesMap[e.source],
t = nodesMap[e.target];
ctx.moveTo(s.x, s.y);
if (e.curvature === 0) {
ctx.lineTo(t.x, t.y);
} else {
const cp = getQuadraticControlPoint(s.x, s.y, t.x, t.y);
ctx.quadraticCurveTo(cp.x, cp.y, t.x, t.y);
}
});
ctx.stroke();
ctx.closePath();
// highlighted edges
ctx.beginPath();
ctx.fillStyle = 'red';
ctx.strokeStyle = '#505050';
ctx.lineWidth = 5;
foundEdges.forEach((e) => {
const s = nodesMap[e.source],
t = nodesMap[e.target];
ctx.moveTo(s.x, s.y);
if (e.curvature === 0) {
ctx.lineTo(t.x, t.y);
} else {
const cp = getQuadraticControlPoint(s.x, s.y, t.x, t.y);
ctx.quadraticCurveTo(cp.x, cp.y, t.x, t.y);
}
});
ctx.stroke();
// nodes;
ctx.beginPath();
ctx.fillStyle = 'orange';
ctx.strokeStyle = '#333333';
ctx.lineWidth = 1;
nodes.forEach((n) => {
ctx.moveTo(n.x + n.r, n.y);
ctx.arc(n.x, n.y, n.r, 0, 2 * Math.PI, false);
});
ctx.stroke();
ctx.fill();
if (selectedNode) {
ctx.beginPath();
ctx.fillStyle = 'red';
ctx.strokeStyle = '#333333';
ctx.moveTo(selectedNode.x + selectedNode.r, selectedNode.y);
ctx.arc(selectedNode.x, selectedNode.y, selectedNode.r, 0, 2 * Math.PI, false);
ctx.stroke();
ctx.fill();
}
ctx.beginPath();
ctx.fillStyle = 'red';
ctx.strokeStyle = '#333333';
ctx.lineWidth = 15;
foundNodes.forEach((n) => {
ctx.moveTo(n.x + n.r, n.y);
ctx.arc(n.x, n.y, n.r, 0, 2 * Math.PI, false);
});
ctx.stroke();
ctx.fill();
ctx.lineWidth = 1;
// query
ctx.beginPath();
ctx.strokeStyle = 'brown';
ctx.rect(qBounds[0], qBounds[1], qBounds[2] - qBounds[0], qBounds[3] - qBounds[1]);
ctx.closePath();
ctx.stroke();
}
function renderIndex() {
const map = {};
const nodesToDraw = [];
U.forEach((n) => {
if (!map[n.key]) {
map[n.key] = true;
nodesToDraw.push(n);
}
});
ctx.beginPath();
nodesToDraw.forEach((n) => {
const b = U.keyToBBox(n.key);
ctx.rect(b[0], b[1], b[2] - b[0], b[3] - b[1]);
});
ctx.closePath();
ctx.stroke();
}
function getRandomColor() {
const letters = '0123456789ABCDEF';
let color = '#';
for (var i = 0; i < 6; i++) {
color += letters[Math.floor(Math.random() * 16)];
}
return color;
}
canvas.addEventListener('mousemove', ({ clientX, clientY }) => {
const x = clientX * pxRatio;
const y = clientY * pxRatio;
const offset = 10 * pxRatio;
foundNodes.length = 0;
foundEdges.length = 0;
qBounds[0] = x - offset;
qBounds[1] = y - offset;
qBounds[2] = x + offset;
qBounds[3] = y + offset;
const Nn = data.nodes.length;
const before = Date.now();
U.query(qBounds).forEach((id) => {
if (id >= Nn) {
foundEdges.push(data.edges[id - Nn]);
} else {
foundNodes.push(data.nodes[id]);
}
});
stats.totalTime += (Date.now() - before);
stats.queries++;
requestAnimationFrame(render);
});
canvas.addEventListener('click', ({ clientX, clientY }) => {
const mx = clientX * pxRatio;
const my = clientY * pxRatio;
requestAnimationFrame(render);
});
function onLayoutDone() {
indexNodes();
indexEdges();
}
function indexNodes() {
console.time('insert nodes into UB');
data.nodes.forEach(({ x, y, r }, i) => {
const bbox = [x - r, y - r, x + r, y + r];
const pos = i * SZ;
flatStorage[pos + 0] = bbox[0];
flatStorage[pos + 1] = bbox[1];
flatStorage[pos + 2] = bbox[2];
flatStorage[pos + 3] = bbox[3];
flatStorage[pos + 4] = POLYGON;
U.insert(i);
});
console.timeEnd('insert nodes into UB');
}
function indexEdges() {
console.time('insert edges into UB');
const offset = data.nodes.length;
data.edges.forEach(({ source, target, curvature }, i) => {
const s = nodesMap[source],
t = nodesMap[target];
const pos = SZ * (offset + i);
// console.log(source, target);
flatStorage[pos + 0] = /*s.x; */ source;
flatStorage[pos + 1] = /*s.y; */ target;
flatStorage[pos + 2] = curvature; // t.x;
flatStorage[pos + 3] = t.y;
flatStorage[pos + 4] = curvature === 0 ? LINESTRING : CURVE;
U.insert(offset + i);
});
console.timeEnd('insert edges into UB');
}
function updateNodes() {
data.nodes.map((n, i) => {
const { x, y, r } = n;
const pos = i * SZ;
flatStorage[pos + 0] = x - r;
flatStorage[pos + 1] = y - r;
flatStorage[pos + 2] = x + r;
flatStorage[pos + 3] = y + r;
flatStorage[pos + 4] = POLYGON;
U.update(i);
});
}
function updateEdges() {
const offset = data.nodes.length;
data.edges.forEach(({ source, target }, i) => {
const s = nodesMap[source],
t = nodesMap[target];
const pos = SZ * (offset + i);
flatStorage[pos + 0] = source; //s.x;
flatStorage[pos + 1] = target; //s.y;
flatStorage[pos + 2] = t.x;
flatStorage[pos + 3] = t.y;
flatStorage[pos + 4] = LINESTRING;
U.update(offset + i);
});
}
function clearNodesIndex() {
console.time('clear nodes');
data.nodes.forEach((e, i) => U.remove(i))
console.timeEnd('clear nodes');
}
function clearEdgesIndex() {
console.time('clear edges');
const offset = data.nodes.length;
data.edges.forEach((e, i) => U.remove(offset + i));
console.timeEnd('clear edges');
}
function layout(data, callback = () => {}) {
const m = data.nodes.length < 1000 ? 1.2 : 1;
return d3.forceSimulation(data.nodes)
.force('charge', d3.forceManyBody())
.force('link', d3.forceLink(data.edges.map((e) => ({
id: e.id,
target: e.target,
source: e.source
}))
)
.id((d) => d.id)
.distance(25 * m))
.force('collision', d3.forceCollide(15 * m))
.force('center', d3.forceCenter(w / 2, h / 2))
.force("y", d3.forceY(0))
.force("x", d3.forceX(0))
.alphaDecay(0.1)
.on('tick', render)
.on('end', callback);
}
const U = new UBTree(6);
const form = document.querySelector('#control');
form.addEventListener('change', function() {
setTimeout(function() {
var nodesIndex = form['nodes'].checked;
var edgesIndex = form['edges'].checked;
var level = form['level'].value;
U.clear();
U.setLevel(level);
if (nodesIndex) indexNodes();
if (edgesIndex) indexEdges();
showIndex = form['grid'].checked;
render();
}, 50);
});
const indicator = document.querySelector('#indicator');
const rangeInput = document.querySelector('#range');
var populateTimer = 0;
function onGraphChanged() {
clearTimeout(populateTimer);
populateTimer = requestAnimationFrame(() => {
N = parseInt(rangeInput.value);
indicator.innerHTML = `G = (${N}<sub>V</sub> &times; ${N}<sub>E</sub>)`;
populate(N);
});
}
rangeInput.addEventListener('change', onGraphChanged);
onGraphChanged();
Raw
morton.js
// Morton lookup tables.
// Based on http://graphics.stanford.edu/~seander/bithacks.html#InterleaveTableLookup
(function (f) {
if (typeof module !== 'undefined') module.exports = f();
else window.morton = f();
}) (function() {
var X = [ 0, 1 ], Y = [ 0, 2 ];
for (var i = 4; i < 0xFFFF; i <<= 2) {
for (var j = 0, l = X.length; j < l; j++) {
X.push((X[j] | i));
Y.push((X[j] | i) << 1);
}
}
// Only works for 24 bit input numbers (up to 16777215).
function morton(x, y) {
return (Y[y & 0xFF] | X[x & 0xFF]) +
(Y[(y >> 8) & 0xFF] | X[(x >> 8) & 0xFF]) * 0x10000 +
(Y[(y >> 16) & 0xFF] | X[(x >> 16) & 0xFF]) * 0x100000000;
};
morton.code = function code(z, x, y) {
if (z > 24) throw 'Morton codes are only supported up to Z=24';
var Z = 1 << (24 - z);
return morton(x * Z, y * Z);
};
morton.range = function range(z, x, y) {
if (z > 24) throw 'Morton ranges are only supported up to Z=24';
var Z = 1 << (24 - z);
var lower = morton(x * Z, y * Z);
return [ lower, lower + Z * Z - 1 ];
};
var rX, rY;
function reverse(c, dest = []) {
if (c > 0xFFFFFFFFFFFF) throw 'Only morton codes up to 48 bits are supported.';
if (!rX) {
// Create reverse lookup tables.
rX = {}; rY = {};
for (var i = 0; i < 256; i++) {
rX[morton(i, 0)] = i;
rY[morton(0, i)] = i;
}
}
var x = rX[c & 0x5555];
var y = rY[c & 0xAAAA];
if (c > 0xFFFF) {
c /= 0x10000;
x |= rX[c & 0x5555] << 8;
y |= rY[c & 0xAAAA] << 8;
if (c > 0xFFFF) {
c /= 0x10000;
x |= rX[c & 0x5555] << 16;
y |= rY[c & 0xAAAA] << 16;
}
}
dest[0] = x;
dest[1] = y;
return dest;
}
morton.reverse = reverse;
morton.decode = function decode(z, c) {
var output = reverse(c);
var Z = 1 << (24 - z);
return [ output[0] / Z, output[1] / Z ];
};
morton.min = function min(lhs, rhs) {
// Isolate the encoded coordinates.
var lhsX = lhs & 0x55555555; // lhsX = -f-e -d-c -b-a -9-8 -7-6 -5-4 -3-2 -1-0
var rhsX = rhs & 0x55555555; // rhsX = -f-e -d-c -b-a -9-8 -7-6 -5-4 -3-2 -1-0
var lhsY = lhs & 0xAAAAAAAA; // lhsY = f-e- d-c- b-a- 9-8- 7-6- 5-4- 3-2- 1-0-
var rhsY = rhs & 0xAAAAAAAA; // rhsY = f-e- d-c- b-a- 9-8- 7-6- 5-4- 3-2- 1-0-
// Find the minimum of the encoded coordinates and combine them into a single word.
return Math.min(lhsX, rhsX) + Math.min(lhsY, rhsY);
}
return morton;
});
Raw
ubtree.js
View raw

(Sorry about that, but we can’t show files that are this big right now.)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment