I somehow understood the question wrong and thought about it. N nearest points♪ I said, Mr. @AnT <script src="https://d3js.org/d3.v4.min.js"></script>
<style>body{margin:0}</style>
<script>
const voronoiRadius = 33;
const width = 600;
const height = 170;
const data = d3.range(333).map((d, i) => ({
x: Math.random() * width,
y: Math.random() * height,
id: i
}));
const container = d3.select('body');
const svg = container.append('svg')
.attr('width', width).attr('height', height);
const g = svg.append('g');
const circles = g.append('g').attr('class', 'circles');
const binding = circles.selectAll('.data-point').data(data, d => d.id);
binding.enter().append('circle')
.classed('data-point', true)
.attr('r', 1.5)
.attr('cx', d => d.x)
.attr('cy', d => d.y)
.attr('fill', 'blue');
const voronoiDiagram = d3.voronoi()
.x(d => d.x).y(d => d.y)
.size([width, height])(data);
g.append('circle')
.attr('class', 'highlight-circle')
.attr('r', 4)
.style('fill', 'none')
.style('display', 'none');
function highlight(d) {
if (!d) {
d3.select('.highlight-circle').style('display', 'none');
} else {
d3.select('.highlight-circle')
.style('display', '')
.style('stroke', 'red')
.attr('cx', d.x)
.attr('cy', d.y);
}
}
g.append('circle')
.attr('class', 'voronoi-radius-circle')
.attr('r', voronoiRadius)
.style('fill', 'none')
.style('stroke', 'tomato')
.style('stroke-dasharray', '3,2')
.style('display', 'none');
g.append('g').selectAll('path')
.data(voronoiDiagram.polygons())
.enter().append('path')
.style('stroke', 'red')
.style('fill', 'none')
.style('opacity', 0.2)
.attr('d', d => M${d.join('L')}Z);
container.on('mousemove', function () {
const [mx, my] = d3.mouse(this);
const site = voronoiDiagram.find(mx, my, voronoiRadius);
highlight(site && site.data);
d3.select('.voronoi-radius-circle')
.style('display', '')
.attr('cx', mx)
.attr('cy', my);
}).on('mouseleave', () => {
d3.select('.voronoi-radius-circle').style('display', 'none');
highlight(null)
});
</script>Trees can be used to find several pointsGot it. var svg = d3.select("svg"),
width = +svg.attr("width"),
height = +svg.attr("height"),
selected;
var random = Math.random,
data = d3.range(250).map(()=> [random() * width, random() * height]);
var quadtree = d3.quadtree()
.extent([[0, 0], [width, height]])
.addAll(data);
var brush = d3.brush()
.on("brush", brushed);
svg.selectAll(".node")
.data(nodes(quadtree))
.enter().append("rect")
.attr("class", "node")
.attr("x", function(d) { return d.x0; })
.attr("y", function(d) { return d.y0; })
.attr("width", function(d) { return d.y1 - d.y0; })
.attr("height", function(d) { return d.x1 - d.x0; });
var 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", 2);
svg.append("g")
.attr("class", "brush")
.call(brush)
.call(brush.move, [[100, 100], [200, 200]]);
function brushed() {
var extent = d3.event.selection;
point.each(function(d) { d.scanned = d.selected = false; });
search(quadtree, extent[0][0], extent[0][1], extent[1][0], extent[1][1]);
point.classed("point--scanned", function(d) { return d.scanned; });
point.classed("point--selected", function(d) { return d.selected; });
}
function search(quadtree, x0, y0, x3, y3) {
quadtree.visit(function(node, x1, y1, x2, y2) {
if (!node.length) {
do {
var d = node.data;
d.scanned = true;
d.selected = (d[0] >= x0) && (d[0] < x3) && (d[1] >= y0) && (d[1] < y3);
} while (node = node.next);
}
return x1 >= x3 || y1 >= y3 || x2 < x0 || y2 < y0;
});
}
function nodes(quadtree) {
var nodes = [];
quadtree.visit(function(node, x0, y0, x1, y1) {
node.x0 = x0, node.y0 = y0;
node.x1 = x1, node.y1 = y1;
nodes.push(node);
});
return nodes;
}body {
overflow:hidden;
}
.point {
fill: #000;
fill-opacity: 0.4;
}
.point--scanned {
fill: orange;
fill-opacity: 1;
stroke: orange;
stroke-width: 3px;
}
.point--selected {
fill: red;
fill-opacity: 1;
stroke: red;
stroke-width: 5px;
}
.node {
fill: none;
stroke: #ccc;
shape-rendering: crispEdges;
}<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/5.7.0/d3.min.js"></script>
<svg width="700" height="175"></svg>Here's an example that uses. /// kd-tree.js
function BPQ(capacity) {
this.capacity = capacity;
this.elements = [];
}
BPQ.prototype.isFull = function() {
return this.elements.length === this.capacity;
};
BPQ.prototype.isEmpty = function() {
return this.elements.length === 0;
};
BPQ.prototype.maxPriority = function() {
return this.elements[this.elements.length - 1].priority;
};
Object.defineProperty(BPQ.prototype, "values", {
get: function() { return this.elements.map(function(d) { return d.value; }); }
});
BPQ.prototype.add = function(value, priority) {
var q = this.elements,
d = { value: value, priority: priority };
if (this.isEmpty()) { q.push(d); }
else {
for (var i = 0; i < q.length; i++) {
if (priority < q[i].priority) {
q.splice(i, 0, d);
break;
}
else if ( (i == q.length-1) && !this.isFull() ) {
q.push(d);
}
}
}
this.elements = q.slice(0, this.capacity);
};
function Node(location, axis, subnodes, datum) {
this.location = location;
this.axis = axis;
this.subnodes = subnodes; // = children nodes = [left child, right child]
this.datum = datum;
};
Node.prototype.toArray = function() {
var array = [
this.location,
this.subnodes[0] ? this.subnodes[0].toArray() : null,
this.subnodes[0] ? this.subnodes[1].toArray() : null
];
array.axis = this.axis;
return array;
};
Node.prototype.flatten = function() {
var left = this.subnodes[0] ? this.subnodes[0].flatten() : null,
right = this.subnodes[1] ? this.subnodes[1].flatten() : null;
return left && right ? [this].concat(left, right) :
left ? [this].concat(left) :
right ? [this].concat(right) :
[this];
};
// k-NN search
Node.prototype.find = function(target, k) {
k = k || 1;
var queue = new BPQ(k),
scannedNodes = [];
search(this);
return {
nearestNodes: queue.values,
scannedNodes: scannedNodes,
maxDistance: queue.maxPriority()
};
// 1-NN algorithm outlined here:
// http://web.stanford.edu/class/cs106l/handouts/assignment-3-kdtree.pdf
function search(node) {
if (node === null) return;
scannedNodes.push(node);
queue.add(node, distance(node.location, target));
if (target[node.axis] < node.location[node.axis]) {
search(node.subnodes[0]);
var otherNode = node.subnodes[1];
} else {
search(node.subnodes[1]);
var otherNode = node.subnodes[0];
}
var delta = Math.abs(node.location[node.axis] - target[node.axis]);
if (!queue.isFull() || delta < queue.maxPriority()) {
search(otherNode);
}
}
};
Node.prototype.lines = function(extent) {
var x0 = extent[0][0],
y0 = extent[0][1],
x1 = extent[1][0],
y1 = extent[1][1],
x = this.location[0],
y = this.location[1];
if (this.axis == 0) {
var line = [[x, y0], [x, y1]];
var left = this.subnodes[0] ?
this.subnodes[0].lines([[x0, y0], [x, y1]]) : null;
var right = this.subnodes[1] ?
this.subnodes[1].lines([[x, y0], [x1, y1]]) : null;
}
else if (this.axis == 1) {
var line = [[x0, y], [x1, y]];
var left = this.subnodes[0] ?
this.subnodes[0].lines([[x0, y0], [x1, y]]) : null;
var right = this.subnodes[1] ?
this.subnodes[1].lines([[x0, y], [x1, y1]]) : null;
}
return left && right ? [line].concat(left, right) :
left ? [line].concat(left) :
right ? [line].concat(right) :
[line];
}
function KDTree() {
var x = function(d) { return d[0]; },
y = function(d) { return d[1]; };
function tree(data) {
var points = data.map(function(d) {
var point = [x(d), y(d)];
point.datum = d;
return point;
});
return treeify(points, 0);
}
tree.x = function(_) {
if (!arguments.length) return x;
x = _;
return tree;
};
tree.y = function(_) {
if (!arguments.length) return y;
y = _;
return tree;
};
return tree;
// Adapted from https://en.wikipedia.org/wiki/K-d_tree
function treeify(points, depth) {
try { var k = points[0].length; }
catch (e) { return null; }
var axis = depth % k;
points.sort(function(a, b) { return a[axis] - b[axis]; });
i_median = Math.floor(points.length / 2);
var point = points[i_median],
left_points = points.slice(0, i_median),
right_points = points.slice(i_median + 1);
return new Node(
point,
axis,
[treeify(left_points, depth + 1), treeify(right_points, depth + 1)],
point.datum
);
}
}
function min(array, accessor) {
return array
.map(function(d) { return accessor(d); })
.reduce(function(a, b) { return a < b ? a : b; });
}
function max(array, accessor) {
return array
.map(function(d) { return accessor(d); })
.reduce(function(a, b) { return a > b ? a : b; });
}
function get(key) { return function(d) { return d[key]; }; }
function distance(p0, p1) {
return Math.sqrt(Math.pow(p1[0] - p0[0], 2) + Math.pow(p1[1] - p0[1], 2));
}
/// example usage
var width = 700,
height = 175;
var svg = d3.select("body").append("svg")
.attr("width", width)
.attr("height", height);
var data = d3.range(2000)
.map(function() {
return {
x: width * Math.random(),
y: height * Math.random(),
value: Math.random() // just for testing purposes
};
});
var tree = KDTree()
.x(function(d) { return d.x; })
.y(function(d) { return d.y; })
(data);
svg.append("g")
.attr("class", "lines")
.selectAll(".line").data(tree.lines([[0,0], [width, height]]))
.enter()
.append("path")
.attr("class", "line")
.attr("d", d3.line());
var points = svg.append("g").attr("class", "points")
.selectAll(".point").data(tree.flatten())
.enter().append("circle")
.attr("class", "point")
.attr("cx", function(d) { return d.location[0]; })
.attr("cy", function(d) { return d.location[1]; })
.attr("r", 4);
var halo = svg.append("circle").attr("class", "halo");
update([width/3, height/2]);
svg.append("rect").attr("class", "event-canvas")
.attr("width", width)
.attr("height", height)
.attr("fill-opacity", 0)
.on("mousemove", function() { update(d3.mouse(this)); });
function update(target) {
var nearest = tree.find(target, 10);
points
.classed("scanned", function(d) { return nearest.scannedNodes.indexOf(d) !== -1; })
.classed("selected", function(d) { return nearest.nearestNodes.indexOf(d) !== -1; });
halo
.attr("cx", target[0])
.attr("cy", target[1])
.attr("r", nearest.maxDistance);
}body {
overflow: hidden;
}
.line {
fill: none;
stroke: #ccc;
}
.point {
fill: #999;
stroke: #fff;
}
.point.scanned {
fill: orange;
stroke: #999;
}
.point.selected {
fill: red;
stroke: #999;
}
.halo {
fill: none;
stroke: red;
}<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/5.7.0/d3.min.js"></script>