[charts] Store voronoi graph in the data space not the rendering one

[alexfauquette]

Currently, the voronoi is computed in the rendering space. Which means each time a user zoom, the scale is updated and we need to compute back the voronoi graph.

Instead we should compute in the data space and call the scale.invert() to map mouse coordinates to data values.

Search keywords:

[bernardobelchior]

I was taking a look at this issue and a couple of questions came up.

The goal seems to be avoiding re-creating the Delaunay class on zoom. To do that, we'd need to call delaunay.find() with the original coordinates, rather than with pixels. However, from a user point of view, we want to obtain the point that is closest to the current pointer position, which must be measured in pixels. As such, if we want to create a Delaunay class with the original coordinates instead of pixels, then we will need to create one Delaunay per combination of X axis and Y axis. This is required because we will need to transform the pointer position in pixels into the original coordinates, and that transformation depends on the scales of the X and Y axes.

From there, for each X, Y axes combination, we'll find the closest point using delaunay.find(). Next, we need to check which of these points is closest in pixels, so we'll need to apply the respective X and Y scales to each of the closest points and find the one that is closest to the current pointer position.

Finally, we check if the closest point, in pixels, is within the Voronoi max radius as we do now.

Does this sound good? Do you see any potential for improvement? I don't love that we're creating a new Delaunay per X,Y axes combination, but I can't think of another solution that is correct.

---

Another point is the type of scales.

It seems we support a set of D3 scales. Band scales are part of this set, but they don't have an invert function. However, there seems to be a way of implementing an invert-like function for band scales.

Nevertheless, this raises a couple of questions:

1. Is there a use case for ChartsVoronoiHandler other than scatter charts? I couldn't see any usage in the codebase;
2. If there isn't, does it even make sense to have a scatter chart with a band scale? (Not sure what the implications of the answer to this question would be, to be honest)

[alexfauquette]

I was surprised I took such a weird decision as doing all the compûtation in the px dimensions and not the value, but not having to handle those edge cases of band, points (but also Date) scale migth be the reasons.

From the various points you mentioned, I end up thinking about the following issue: If we have multiple y-axis and zoom on one of them, the result will need to be updated.

Since it looks complex, we might reconsider the goal. We could investigate following points

• Estimate the cost of doing voronoid computation on large dataset (what append on 1k-10k points ? how does it scale with the number of point (Nlog(N) in theory but better to test))
• when does it run. I assume each zoom update ruens the voronoid

Depending on those results, maybe the solution is not to revert the space of commputation, but block the voronoid update while the zoom is active. Having an update when zoom end instead of one at each step coudl already be an improvement.

[bernardobelchior]

when does it run. I assume each zoom update ruens the voronoid

Yeah, I just checked. We're creating an instance of the Delauney class and iterating every point of every series on every zoom and pan action.