Comment by _ls7m | Hacker News Reader

Comment by _ls7m | Hacker News Reader

Parent Full thread

This does look like where they are generating the mouseover/highlight regions for the multi-line graphs. And the highlight regions for the scatterplot are being done here https://github.com/mozilla/metrics-graphics/blob/master/js/m...

For both they are using D3's built-in voronoi function which will generate the appropriate interaction regions when given a list of points. These polygonal regions surround the given points and fill the graph, acting as large unmissable mouseover targets instead of the tiny points. It's really useful. https://github.com/mbostock/d3/wiki/Voronoi-Geom

More on voronoi tessalation http://en.wikipedia.org/wiki/Voronoi_diagram

It would be interesting to see the performance characteristics between

    1) building a Voronoi tessellation from the given points
    2) at each mouse movement perform point-in-polygon queries on all polygons until found
    3) rebuild Voronoi as data changes

or

    1) at each mouse movement calculate distance-to-point for each point
    2) select the shortest

Not sure if I'm misreading your step 2 description for the first strategy, but one of the great things about using this type of mouseover region is that each polygon is already tied to a single point - so there's no need to do any query for contained points on mouseover. The lookup time for contained points is constant.

How do go from cursor coordinates to a polygon? Once you've done that, finding the the associated point in the scatter plot should be constant, but mapping from cursor to polygons in faster than linear time seems non-trivial.

k-d trees sound closer to what you'd want to do cursor coordinates to scatter plot point lookups.

Hi - author here. Yes, we use Voronoi + clipPaths to make these kinds of rollovers possible.

Reply on news.ycombinator.com