Skip to main content
100%

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 description

With 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)
}

Similar vizzes