{
const context = DOM.context2d(width, height);
function drawTree(t) {
context.strokeRect(t.minX, t.minY, t.maxX - t.minX, t.maxY - t.minY);
context.lineWidth /= 1.5;
if (context.lineWidth > .08) if (t.children) t.children.forEach(drawTree);
context.lineWidth *= 1.5;
}
function draw(x, y) {
context.clearRect(0, 0, width, height);
context.lineWidth = .5;
if (debug_tree) {
context.strokeStyle = "orange";
drawTree(tree.data);
context.strokeStyle = "black";
}
context.lineWidth = .25;
context.beginPath();
if (lines.length <= 10000) {
for (const p of lines) {
context.moveTo(p.x1, p.y1);
context.lineTo(p.x2, p.y2);
}
}
context.strokeStyle = "steelblue";
context.stroke();
const { line, contact, distance, candidates } = searchOne(x, y);
if (debug_candidates) {
context.lineWidth = 1;
context.beginPath();
context.strokeStyle = "black";
for (const p of candidates) {
context.moveTo(p.x1, p.y1);
context.lineTo(p.x2, p.y2);
}
context.stroke();
}
context.lineWidth = 3;
context.strokeStyle = "red";
context.beginPath();
context.moveTo(line.x1, line.y1);
context.lineTo(line.x2, line.y2);
context.stroke();
context.strokeStyle = "black";
context.lineWidth = .5;
if (contact) {
context.beginPath();
context.moveTo(x + distance, y);
context.arc(x, y, distance, 0, 2 * Math.PI);
context.stroke();
context.beginPath();
context.moveTo(...contact);
context.arc(...contact, 3, 0, 2 * Math.PI);
context.fillStyle = "red";
context.fill();
}
}
draw(300, 200);
d3.select(context.canvas)
.style("cursor", "crosshair")
.on("mousemove click", function() {
draw(...d3.mouse(this));
});
return context.canvas;
}
knnLine = {
return function knn(tree, x, y, n, predicate, maxDistance) {
const queue = new Queue(undefined, (a, b) => a.dist - b.dist),
result = [];
let node = tree.data,
i,
child,
dist,
candidate;
result.candidates = [];
while (node) {
for (i = 0; i < node.children.length; i++) {
child = node.children[i];
dist = node.leaf
? result.candidates.push(child) &&
projectPointOnSegment(x, y, child.x1, child.y1, child.x2, child.y2)
.dist
: boxDist(x, y, child);
if (!maxDistance || dist <= maxDistance) {
queue.push({
node: Object.assign(child, { dist }),
isItem: node.leaf,
dist: dist
});
}
}
while (queue.length && queue.peek().isItem) {
candidate = queue.pop().node;
if (!predicate || predicate(candidate)) {
result.push(candidate);
}
if (n && result.length === n) return result;
}
node = queue.pop();
if (node) node = node.node;
}
return result;
};
// returns 0 if [x,y] is inside the box
function boxDist(x, y, box) {
return Math.hypot(
axisDist(x, box.minX, box.maxX),
axisDist(y, box.minY, box.maxY)
);
}
function axisDist(k, min, max) {
return k < min ? min - k : k <= max ? 0 : k - max;
}
}
// priority search
function searchOne(x, y) {
const r = knnLine(tree, x, y, 1),
{ candidates } = r,
p = r[0];
const d = projectPointOnSegment(x, y, p.x1, p.y1, p.x2, p.y2);
return { line: p, contact: d.contact, distance: d.dist, candidates };
}
{
const t = performance.now();
const o = searchOne(100, 100);
return { o, t: performance.now() - t };
}
function projectPointOnSegment(x, y, x1, y1, x2, y2) {
const vx = x - x1,
vy = y - y1,
dx = x2 - x1,
dy = y2 - y1,
dot = vx * dx + vy * dy,
l2 = dx * dx + dy * dy,
c = l2 && dot / l2,
s = c <= 0 ? [x1, y1] : c >= 1 ? [x2, y2] : [x1 + c * dx, y1 + c * dy];
return { dist: Math.hypot(x - s[0], y - s[1]), contact: s };
}
lines = Array.from({ length: 10000 }, () => {
const r = 20 + Math.random() * 100,
x1 = r + Math.random() ** 2 * (width * 0.8 - 2 * r),
y1 = r + Math.random() * (height * 0.9 - 2 * r),
a = Math.random() * 6.28,
x2 = x1 + (r - 2) * Math.cos(a),
y2 = y1 + (r - 2) * Math.sin(a);
return { x1, y1, x2, y2 };
})
height = width * 0.7
tree = {
const tree = new RBush();
tree.load(
lines.map(d => {
d.minX = Math.min(d.x1, d.x2);
d.minY = Math.min(d.y1, d.y2);
d.maxX = Math.max(d.x1, d.x2);
d.maxY = Math.max(d.y1, d.y2);
return d;
})
);
return tree;
}
RBush = require("rbush")
Queue = import("tinyqueue").then((d) => d.default)
d3 = require("d3-selection@1", "d3-array@2")
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.
