Public
Edited
May 22, 2021
1 fork
14 stars
chart = {
// collapses a quadtree into a list of nodes, adding their depth
function retrieveNodesAndDepth(quadtree) {
const nodes = [];
let maxdepth = 0;
quadtree.root().depth = 0; // root node depth
quadtree.visit((node, x1, y1, x2, y2) => {
node.x1 = x1;
node.y1 = y1;
node.x2 = x2;
node.y2 = y2;
nodes.push(node);
for (var i=0; i < node.length; i++) {
if (node[i]) {
node[i].depth = node.depth+1;
maxdepth = (node[i].depth > maxdepth) ? node[i].depth : maxdepth;
}
}
return false;
});
return {"nodes": nodes, "depth": maxdepth};
}
// draw the selection in the quadtree visualisation
function drawSelection(quadtree) {
const pt = d3.select("#pt");
const x = pt.attr('cx'), y = pt.attr('cy');
//get nearest neighbuors
quadtree.root().mindist = 0;
const bestqueue = new Array(quadtree.root()); // start with the root node of the quadtree
const resultqueue = [];
const scannedqueue = []; // only needed to visualise the work of the quadtree
knearest(bestqueue, resultqueue, x, y, k, scannedqueue);
resultqueue.forEach((d) => d.data.selected=true);
scannedqueue.forEach((d) => d.length ? d.scanned=true : d.data.scanned = true);
// paint
point.classed("scanned", (d) => d.scanned);
point.classed("selected", (d) => d.selected);
rect.style('fill', (d) => d.scanned ? color(d.depth) : 'none');
rect.classed('scanned', (d) => d.scanned);
// clean up data
resultqueue.forEach((d) => d.data.selected=false);
scannedqueue.forEach((d) => d.length ? d.scanned=false : d.data.scanned = false);
}
const div = DOM.element("div");
d3.select(div).append("style").text(`
.point {
fill: #999;
stroke: #fff;
}
.point.scanned {
fill: orange;
stroke: #000;
}
.point.selected {
fill: red;
}
.node {
fill: none;
stroke: none;
}
.node.scanned {
stroke: #333;
}
`);
const height = width;
const data = d3.range(n).map(_ => [Math.random() * width, Math.random() * height]);
const quadtree = d3.quadtree()
.extent([[-1, -1], [width + 1, height + 1]])
.addAll(data);
const {nodes, depth} = retrieveNodesAndDepth(quadtree);
const color = d3.scaleLinear()
.domain([0, depth]) // max depth of quadtree
.range(["#fff", "#555"]);
const svg = d3.select(div).append("svg")
.attr("width", width)
.attr("height", height)
.on("mouseover", (e) => {
var xy = d3.pointer(e);
svg.selectAll("#pt")
.attr("cx", xy[0])
.attr("cy", xy[1]);
drawSelection(quadtree);
});
const rect = svg.selectAll(".node")
.data(nodes)
.enter().append("rect")
.attr("class", "node")
.attr("x", function(d) { return d.x1; })
.attr("y", function(d) { return d.y1; })
.attr("width", function(d) { return d.x2 - d.x1; })
.attr("height", function(d) { return d.y2 - d.y1; });
const point = svg.selectAll(".point")
.data(data)
.enter().append("circle")
.attr("class", "point")
.attr("cx", function(d) { return d[0]; })
.attr("cy", function(d) { return d[1]; })
.attr("r", 3);
svg.append("circle")
.attr("id", "pt")
.attr("r", 3)
.attr("cx", width/2)
.attr("cy", height/2)
.style("fill", "black");
return div;
}
/**
* Calculate euclidean distance of two points with coordinates: (x1, y1) and (x2, y2).
* To increase speed the result is not square rooted.
* @param {Number} x1 x coordinate of point 1
* @param {Number} y1 y coordinate of point 1
* @param {Number} x2 x coordinate of point 2
* @param {Number} y2 y coordinate of point 2
* @return {Number} The distance between both points
*/
function euclidDistance(x1, y1, x2, y2){
return Math.pow(x1-x2, 2) + Math.pow(y1-y2, 2);
}
/**
* Calculate minimum distance between searchpoint and rectangle
* This function is matched to speed optimisation of euclidDistance and resulting distances
* are therefor returned to the power of 2.
*
* @param {Number} x x coordinate of reference point
* @param {Number} y y coordinate of reference point
* @param {Number} x1 x coordinate of lower bound of the rectangle
* @param {Number} y1 y coordinate of lower bound of the rectangle
* @param {Number} x2 x coordinate of upper bound of the rectangle
* @param {Number} y2 y coordinate of upper bound edge of the rectangle
* @return {Number} The minimum distance between point and rectangle
*/
function mindist(x, y, x1, y1, x2, y2){
var dx1 = x - x1, dx2 = x - x2,
dy1 = y - y1, dy2 = y - y2;
if (dx1*dx2 < 0) { // x is between x1 and x2
if (dy1*dy2 < 0) { // (x,y) is inside the rectangle
return 0; // return 0 as point is in rect
}
return Math.min(Math.pow(Math.abs(dy1),2),Math.pow(Math.abs(dy2),2));
}
if (dy1*dy2 < 0) { // y is between y1 and y2
// we don't have to test for being inside the rectangle, it's already tested.
return Math.min(Math.pow(Math.abs(dx1),2),Math.pow(Math.abs(dx2),2));
}
return Math.min( Math.min(euclidDistance(x,y,x1,y1),euclidDistance(x,y,x2,y2)), Math.min(euclidDistance(x,y,x1,y2),euclidDistance(x,y,x2,y1)) );
}
/**
* Recursive nearest neighbour search, expecting a quadtree,
* returning the k nearest points to a reference point.
*
* @param {Array} bestqueue Queue containing all nodes to be visited for the search
* @param {Array} resultqueue Queue containing the resulting k nearest neighbours
* @param {Number} x x coordinate of reference point
* @param {Number} y y coordinate of reference point
* @param {Number} k k number of neares neighbours to be found
* @param {Array} scannedqueue Queue containing the scanned nodes and leaves: can be undefined,
* as it is only needed for the visualisation of the algorithm.
*/
function knearest(bestqueue, resultqueue, x, y, k, scannedqueue) {
bestqueue.sort(function(a, b){ // sort children according to their mindist/dist to searchpoint
[a, b].forEach(function(val){
if(val.mindist == undefined){ // add minidst to nodes if not there already
if (scannedqueue) scannedqueue.push(val); // feed the scannedqueue if it is given
if(!val.length){ // is leaf
val.mindist = euclidDistance(x, y, val.data[0], val.data[1]);
}else{
val.mindist = mindist(x, y, val.x1, val.y1, val.x2, val.y2);
}
}
});
return b.mindist - a.mindist;
});
for (var i=bestqueue.length-1; i>=0; i--){ // add nearest leafs if any
var elem = bestqueue[i];
if(!elem.length){ // is leaf
bestqueue.pop();
resultqueue.push(elem);
if(resultqueue.length >=k || bestqueue.length == 0){ // return if k neighbors found or no points left
return;
}
}else{
break;
}
}
var visited = bestqueue.pop();
for (var i=0; i<visited.length; i++) { // add child quadrants to queue
if(visited[i]) {
visited[i].mindist = undefined; // reset before adding it to the queue
bestqueue.push(visited[i]);
}
}
knearest(bestqueue, resultqueue, x, y, k, scannedqueue); // recursion
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
