Skip to content

Instantly share code, notes, and snippets.

@kkdd

kkdd/README.md

Last active July 4, 2022 22:18
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save kkdd/92a185b33e387aa1de19cbce2ba7464f to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save kkdd/92a185b33e387aa1de19cbce2ba7464f to your computer and use it in GitHub Desktop.
Download ZIP
r-tree.js and draggable demonstration
Raw
README.md
Raw
index.html
<!DOCTYPE html>
<meta charset="utf-8">
<title>Braun projection</title>
<style>
.frame {
fill: none;
stroke: #000;
stroke-width: 2px;
}
.fill {
fill: #fff;
}
.graticule {
fill: none;
stroke: #aaa;
stroke-width: 0.5px;
stroke-opacity: 0.5;
}
.land {
fill: #ddd;
}
.boundary {
fill: none;
stroke: #fff;
stroke-width: 0.5px;
}
.rect {
fill: #8f0;
fill-opacity: .25;
stroke: #0f0;
stroke-width: 0.4px;
pointer-events: none;
}
.rects {
fill: #44f;
fill-opacity: .6;
stroke: #00f;
stroke-width: 0.2px;
pointer-events: none;
}
</style>
<div id="canvas" width="600" height="400"></div>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script src="https://unpkg.com/topojson-client@3"></script>
<script src="./r-tree.js"></script>
<!-- https://github.com/kkdd/javascript-hilbert-r-tree/tree/master/r-tree -->
<script>
var rect, points = [[90, -10], [140, 30]]; // bounding rectangle
var rects, rectsData = [
{x: 105, y: -45, width: 40, height: 20},
{x: 155, y: -35, width: 30, height: 40},
{x: 145, y: 25, width: 40, height: 30},
{x: 115, y: -15, width: 20, height: 30},
{x: 105, y: 55, width: 20, height: 10},
{x: 15, y: -15, width: 30, height: 30},
{x: -165, y: -25, width: 60, height: 20},
{x: -125, y: 35, width: 80, height: 10},
{x: -155, y: 55, width: 20, height: 10},
{x: -155, y: 15, width: 20, height: 20},
{x: -95, y: -15, width: 50, height: 20},
];
for (var i=0;i<1000; i++) {
var pt = [Math.random()*2-1, Math.random()*2-1];
if (pt[0]*pt[0]+pt[1]*pt[1] < 1) {
rectsData.push({x: Math.floor(pt[0]*70+30), y: Math.floor(pt[1]*70), width: Math.floor(Math.random()*6+2), height: Math.floor(Math.random()*6+2)});
}
}
var maxNodes = 4; // Maximum number of nodes within a bounding rectangle
var tree = new RTree(maxNodes);
tree.batchInsert(rectsData);
var svg = d3.select("#canvas")
.append("svg")
.attr("width", 600)
.attr("height", 400);
function braunRaw(lambda, phi) {
return [lambda, Math.tan(phi/2)*2];
}
braunRaw.invert = function(x, y) {
return [x, Math.atan(y/2)*2];
};
var width = +svg.attr("width"), height = +svg.attr("height");
var projection = d3.geoProjection(braunRaw)
.scale((width - 3) / (2 * Math.PI))
.translate([width/2, height/2])
.precision(0.1);
var path = d3.geoPath()
.projection(projection);
var graticule = d3.geoGraticule();
svg.append("defs").append("path")
.datum(graticule.outline())
.attr("id", "sphere")
.attr("d", path);
svg.append("use")
.attr("class", "frame")
.attr("xlink:href", "#sphere");
svg.append("use")
.attr("class", "fill")
.attr("xlink:href", "#sphere");
svg.append("path")
.datum(graticule)
.attr("class", "graticule")
.attr("d", path);
var drag = d3.drag()
.on("drag", function (d, i) {
var pt = [d3.event.x, d3.event.y];
points[i] = projection.invert(pt);
drawGeom();
d3.select(this)
.attr("cx", d.x = pt[0])
.attr("cy", d.y = pt[1]);
});
svg.selectAll("circle")
.data(points).enter()
.append("circle")
.attr("cx", function (d) {return projection(d)[0]})
.attr("cy", function (d) {return projection(d)[1]})
.attr("r", "2.5px")
.attr("stroke-width", "1px")
.attr("stroke", function(d, i) { return ["#00f", "#f00"][i]; })
.attr("fill", "#fff")
.call(drag);
drawGeom();
function drawGeom() {
if (rect) {rect.remove()}
if (rects) {rects.remove()}
rect = svg.append("path")
.datum(boundRect(points))
.attr("class", "rect")
.attr("d", path);
var options = {xPeriod: 360, includedOnly: true, searchIndex: true}; // coping with antimeridian-crossing case (overlapping/intersecting rectangles)
var resultIndexes = tree.search(bound2rect(points), options);
var resultRects = resultIndexes.map(function (i) {
return boundRect(rect2bound(rectsData[i]));
});
rects = svg.selectAll("rects")
.data(resultRects).enter()
.append("path")
.attr("class", "rects")
.attr("d", path);
}
function rect2bound(rect) {
return [[rect.x, rect.y], [rect.x+rect.width, rect.y+rect.height]];
}
function bound2rect(bb) {
var height = bb[1][1] - bb[0][1],
width = moduloPascal(bb[1][0] - bb[0][0], 360);
return {x: bb[0][0], y: bb[0][1], width: width, height: height};
}
function moduloPascal(a, b) {
return (a%b+b)%b;
}
d3.json("https://unpkg.com/world-atlas@1/world/50m.json", function(error, world) {
svg.insert("path", ".graticule")
.datum(topojson.feature(world, world.objects.land))
.attr("class", "land")
.attr("d", path);
svg.insert("path", ".graticule")
.datum(topojson.mesh(world, world.objects.countries, function(a, b) { return a !== b; }))
.attr("class", "boundary")
.attr("d", path);
});
function boundRect(pnts) {
var coords = [[pnts[0][0],pnts[0][1]]]
.concat(parallel(pnts[0][0], pnts[1][0], pnts[0][1]))
.concat(parallel(pnts[0][0], pnts[1][0], pnts[1][1]).reverse());
return rfc7946tod3({type: "Polygon", coordinates: [coords]})
}
function parallel(λ0, λ1, φ) {
if (λ0 > λ1) λ1 += 360;
var dλ = λ1 - λ0,
step = dλ / Math.ceil(dλ);
return d3.range(λ0, λ1 + 0.5 * step, step).map(function(λ) { return [normalise(λ), φ]; });
}
function normalise(x) {
return (x + 180) % 360 - 180;
}
// https://github.com/tyrasd/rfc7946-to-d3
function rfc7946tod3(geojson) {
switch ((geojson && geojson.type) || null) {
case 'FeatureCollection':
geojson.features.forEach(rfc7946tod3)
break
case 'GeometryCollection':
geojson.geometries.forEach(rfc7946tod3)
break
case 'Feature':
rfc7946tod3(geojson.geometry)
break
case 'MultiPolygon':
geojson.coordinates.forEach(function(polygon) {
polygon.forEach(function(ring) {
ring.reverse()
})
})
break
case 'Polygon':
geojson.coordinates.forEach(function(ring) {
ring.reverse()
})
break
}
return geojson
}
</script>
Raw
r-tree.js
var RTreeRectangle = (function () {
function RTreeRectangle(x, y, width, height, data, leafIndex) {
this.x = x;
this.y = y;
this.width = width;
this.height = height;
this.data = data;
this.leafIndex = leafIndex;
this.children = [];
}
RTreeRectangle.generateEmptyNode = function () {
return new RTreeRectangle(Infinity, Infinity, 0, 0, null, null);
};
RTreeRectangle.prototype.overlaps = function (anotherRect) {
return this.x < anotherRect.x + anotherRect.width && this.x + this.width > anotherRect.x && this.y + this.height > anotherRect.y && anotherRect.y + anotherRect.height > this.y;
};
RTreeRectangle.prototype.contains = function (anotherRect) {
return this.x <= anotherRect.x && this.x + this.width >= anotherRect.x + anotherRect.width && this.y <= anotherRect.y && this.y + this.height >= anotherRect.y + anotherRect.height;
};
RTreeRectangle.prototype.growRectangleToFit = function (anotherRect) {
if (this.x === Infinity) {
this.height = anotherRect.height;
this.width = anotherRect.width;
this.x = anotherRect.x;
this.y = anotherRect.y;
}
else {
this.height = Math.max(this.y + this.height, anotherRect.y + anotherRect.height) - Math.min(this.y, anotherRect.y);
this.width = Math.max(this.x + this.width, anotherRect.x + anotherRect.width) - Math.min(this.x, anotherRect.x);
this.x = Math.min(this.x, anotherRect.x);
this.y = Math.min(this.y, anotherRect.y);
}
};
RTreeRectangle.prototype.areaIfGrownBy = function (anotherRect) {
if (this.x === Infinity) {
return anotherRect.height * anotherRect.width;
}
else {
return (Math.max(this.y + this.height, anotherRect.y + anotherRect.height) - Math.min(this.y, anotherRect.y)) * (Math.max(this.x + this.width, anotherRect.x + anotherRect.width) - Math.min(this.x, anotherRect.x)) - this.getArea();
}
};
RTreeRectangle.prototype.getArea = function () {
return this.height * this.width;
};
RTreeRectangle.prototype.getCenter = function () {
return {x: Math.ceil(this.x + this.width * 0.5), y: Math.ceil(this.y + this.height * 0.5)};
};
RTreeRectangle.prototype.splitIntoSiblings = function () {
var pivot = Math.floor(this.children.length / 2);
var sibling1 = RTreeRectangle.generateEmptyNode();
var sibling2 = RTreeRectangle.generateEmptyNode();
HilbertCurves.sortRect(this.children).forEach(function (rect, i) {
if (i <= pivot) {
sibling1.insertChildRectangle(rect);
}
else {
sibling2.insertChildRectangle(rect);
}
});
this.children.length = 0;
return [sibling1, sibling2];
};
RTreeRectangle.prototype.numberOfChildren = function () {
return this.children.length;
};
RTreeRectangle.prototype.isLeafNode = function () {
return this.children.length === 0;
};
RTreeRectangle.prototype.hasLeafNodes = function () {
return this.isLeafNode() || this.children[0].isLeafNode();
};
RTreeRectangle.prototype.insertChildRectangle = function (insertRect) {
insertRect.parent = this;
this.children.push(insertRect);
this.growRectangleToFit(insertRect);
};
RTreeRectangle.prototype.removeChildRectangle = function (removeRect) {
this.children.splice(this.children.indexOf(removeRect), 1);
};
RTreeRectangle.prototype.getSubtreeData = function (indexData) {
if (this.children.length === 0) {
return [this[indexData]];
}
return this.children.map(function (x) {return x.getSubtreeData(indexData)}).flatten();
};
return RTreeRectangle;
}());
var RTree = (function () {
function RTree(maxNodes) {
this.maxNodes = maxNodes;
this.count = 0;
this.root = RTreeRectangle.generateEmptyNode();
}
RTree.prototype._recursiveSeach = function (searchRect, node, includedOnly, indexData) {
var _this = this;
if (searchRect.contains(node)) {
return node.getSubtreeData(indexData);
}
else if (node.isLeafNode()) {
return (includedOnly===true)?[]:node.getSubtreeData(indexData);
}
else {
var overlapped = node.children.filter(function (x) {return x.overlaps(searchRect);});
return overlapped.map(function (iterateNode) {return _this._recursiveSeach(searchRect, iterateNode, includedOnly, indexData)}).flatten();
}
};
RTree.prototype.search = function (searchBoundary, options) {
if (!options) {options = {}}
var cycles, _this = this;
var indexData = options.searchIndex?"leafIndex":"data";
if (!options.xPeriod) {cycles = [0];}
else {
var xperi = options.xPeriod;
var dx = _this.root.x - searchBoundary.x;
var start = Math.ceil((dx - searchBoundary.width)/xperi);
var len = Math.floor((dx + _this.root.width)/xperi) - start + 1;
cycles = Array.from(Array(len), (_, i) => (start+i)*xperi); // range()
}
var result = cycles.map(function (dx) {
var searchRect = new RTreeRectangle(dx + searchBoundary.x, searchBoundary.y, searchBoundary.width, searchBoundary.height, null, null);
return _this._recursiveSeach(searchRect, _this.root, options.includedOnly, indexData);
});
return result.flatten();
};
RTree.prototype.insert = function (dataPoint) {
var currentNode = this.root;
if (currentNode) {
var insertRect = new RTreeRectangle(dataPoint.x, dataPoint.y, dataPoint.width, dataPoint.height, dataPoint.data, this.count);
while (!currentNode.hasLeafNodes()) {
currentNode.growRectangleToFit(insertRect);
currentNode = currentNode.children.minBy(function (rect) {return rect.areaIfGrownBy(insertRect)});
}
currentNode.insertChildRectangle(insertRect);
this.balanceTreePath(insertRect);
this.count += 1;
}
};
RTree.prototype._recursiveTreeLayer = function (listOfRectangles, level) {
if (level === void 0) {level = 1;}
var numberOfParents = Math.ceil(listOfRectangles.length / this.maxNodes);
var nodeLevel = [];
var childCount = 0;
var parent;
for (var i = 0; i < numberOfParents; i++) {
parent = RTreeRectangle.generateEmptyNode();
childCount = Math.min(this.maxNodes, listOfRectangles.length);
for (var y = 0; y < childCount; y++) {
parent.insertChildRectangle(listOfRectangles.pop());
}
nodeLevel.push(parent);
}
if (numberOfParents > 1) {
return this._recursiveTreeLayer(nodeLevel, level + 1);
}
else {
return nodeLevel;
}
};
RTree.prototype.batchInsert = function (listOfData) {
var count = this.count;
var rectangles = listOfData.map(function (dataPoint, i) {
return new RTreeRectangle(dataPoint.x, dataPoint.y, dataPoint.width, dataPoint.height, dataPoint.data, i + count);
});
var sorted = HilbertCurves.sortRect(rectangles);
this.root = this._recursiveTreeLayer(sorted)[0];
this.count += listOfData.length;
};
RTree.prototype.balanceTreePath = function (leafRectangle) {
var currentNode = leafRectangle;
while (currentNode.parent && currentNode.parent.numberOfChildren() > this.maxNodes) {
var currentNode = currentNode.parent;
if (currentNode != this.root) {
currentNode.parent.removeChildRectangle(currentNode);
currentNode.splitIntoSiblings().forEach(function (rect) {
currentNode.parent.insertChildRectangle(rect);
});
}
else if (currentNode == this.root) {
currentNode.splitIntoSiblings().forEach(function (rect) {
currentNode.insertChildRectangle(rect);
});
}
}
};
return RTree;
}());
var HilbertCurves;
(function (HilbertCurves) {
function sortRect(listOfRectangles) {
var center, min = Infinity, max = -Infinity;
listOfRectangles.forEach(function (rect) {
center = rect.getCenter();
max = Math.max(max, center.x, center.y);
min = Math.min(min, center.x, center.y);
});
var maxCoord = max - min;
var sorted = listOfRectangles.sort(function (rect) {
center = rect.getCenter();
return HilbertCurves.toHilbertCoordinates(maxCoord, center.x-min, center.y-min);
});
return sorted;
}
HilbertCurves.sortRect = sortRect;
function toHilbertCoordinates(maxCoordinate, x, y) {
var r = maxCoordinate;
var mask = (1 << r) - 1;
var hodd = 0;
var heven = x ^ y;
var notx = ~x & mask;
var noty = ~y & mask;
var tmp = notx ^ y;
var v0 = 0;
var v1 = 0;
for (var k = 1; k < r; k++) {
v1 = ((v1 & heven) | ((v0 ^ noty) & tmp)) >> 1;
v0 = ((v0 & (v1 ^ notx)) | (~v0 & (v1 ^ noty))) >> 1;
}
hodd = (~v0 & (v1 ^ x)) | (v0 & (v1 ^ noty));
return hilbertInterleaveBits(hodd, heven);
}
HilbertCurves.toHilbertCoordinates = toHilbertCoordinates;
function hilbertInterleaveBits(odd, even) {
var val = 0;
var max = Math.max(odd, even);
var n = 0;
while (max > 0) {
n++;
max >>= 1;
}
for (var i = 0; i < n; i++) {
var mask = 1 << i;
var a = (even & mask) > 0 ? (1 << (2 * i)) : 0;
var b = (odd & mask) > 0 ? (1 << (2 * i + 1)) : 0;
val += a + b;
}
return val;
}
})(HilbertCurves || (HilbertCurves = {}));
nRange = function(imin, nrange) {
var rng = Array.from(Array(nrange?nrange-imin:imin).keys());
return rng.map(function (i) {return i+(nrange?imin:0)});
}
Array.prototype.minBy = function (mapFunc) {
var arr = this.map(mapFunc);
return this[arr.indexOf(Math.min.apply(null, arr))];
};
Array.prototype.flatten = function () {
return this.reduce(function (p, c) {
return Array.isArray(c) ? p.concat(c.flatten()) : p.concat(c);
}, []);
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment