canvas-interaction-sorted
✓ Published0🌍 Public
11wheel
Last edited Jul 22, 2019
Created on Jul 20, 2019
A viewer displays a million randomly generated points sorted by x-coordinate, with a circle highlighting the point closest to the cursor. Moving the mouse triggers a search that uses a binary search to find a starting index, then expands outward to compare neighboring points until a minimum distance is confirmed. The tooltip reports the time in milliseconds and the number of comparisons made. The visualization is built with a custom d3.js environment, mixing Canvas for drawing points and SVG for the highlight circle.
AI-generated descriptionWith data sorted along the x axis, we can find the closest point even faster.
var [px, py] = d3.mouse(this)
var index = bisect.left(data, px)
var minPoint = null
var minDist = Infinity
var lxDist = 0
var rxDist = 0
var i = 0
while (lxDist < minDist && rxDist < minDist){
lxDist = checkPoint(data[index - i])
rxDist = checkPoint(data[index + i])
i++
}
function checkPoint(d){
if (!d) return Infinity
var dx = d.px - px
var dy = d.py - py
var dist = Math.sqrt(dx*dx + dy*dy)
if (dist < minDist){
minDist = dist
minPoint = d
}
return Math.abs(px - d.px)
}