Expose interpolation formulas in line()

[brmscheiner]

When using curves, it can be cumbersome to derive the actual value that a particular point on a path represents. This information is useful for tooltips, calculating integrals, and sampling data. While the documentation does a great job of citing references for which interpolation algorithms are being used, trusting users to implement them on their own introduces a variety of problems, including

• duplicate code
• ambiguity about which version of the cited algorithm d3 uses
• potential differences between d3's algorithm and the users
• inability to proceed without a math background

One solution is to use getPointAtLength(), but this is complicated, recursive, and computationally intensive. Since d3-shape implements these algorithms, why not share them? This could manifest itself in many ways, including

const xPointOfInterest = 7;

const lineGenerator = line()
  .curve(curveBasis)
  .x(d => d.x)
  .y(d => d.y);

const yValueAtX = lineGenerator(points, xPointOfInterest); // OR
const yValueAtX = lineGenerator.getValue(points, xPointOfInterest) // OR

const lineSolver = lineSolver()
  .curve(curveBasis)
  .data(points)

const yValueAtX = lineSolver(xPointOfInterest)

[andreasplesch]

I think the issue is that d3-shape does not fully implement the curve algorithms itself, it just translates them to Beziers. d3 takes advantage of the fact that svg natively understand Bezier curves. d3 has interpolation for splines which could be used, see https://github.com/d3/d3-interpolate/issues/49 In fact, some of the curves translate first from splines to Beziers which then would not be necessary.

[brmscheiner]

@andreasplesch even more reason to expose the underlying algorithm, right!

[andreasplesch]

Most algorithms do not define a line as a function y(x) but in effect as a parametrized, piecewise, spline/Bezier function pointXY(t). So a proposed lineAlgorithm() would return a function pointXY(t). A proposed lineSolverX() would still need to go through an expensive search along the line, to find t. In the end it would come out similar to just using SVG's getPointAtLength() with the generated SVG path. So I am not sure how much would be gained by having a line.lineAlgorithm.

Therefore, a d3.line.lineSolverX() would be probably just based on getPointAtLength(). This seems perhaps a bit out of place for d3 although it could be really useful. There is probably a way to extend d3.line, with external plugin-like code.

[andreasplesch]

https://talk.observablehq.com/t/obtain-interpolated-y-values-without-drawing-a-line/1796 for a related discussion. https://observablehq.com/d/c47dbd136d77b682 has a potential soluition, based on getPointAtLength() after all, which turn out to be not really that complicated or expensive. Recursion is not actually required, just iteration.

[brmscheiner]

@andreasplesch if getPointAtLength() is needed, i think that it would be ok to use. But I think you would end up with an approximation

But I don't understand what makes it expensive to find the solution for a piecewise bezier function if you already know all the pieces. Maybe there's something I'm missing?

In my mind an algorithm for finding f(x), where f is composed of known piecewise bezier functions could look like this

1. find the bezier function corresponding to a given x (let's call it B(t))
2. find the t corresponding to x (x minus the beginning of the piece)
3. compute B(t)

[andreasplesch]

The find t corresponding to x part requires a search, for example by bisection. Depending on the target accuracy this can be somewhat expensive.

[brmscheiner]

Why? If d3 generated the path, d3 should know the start and end x value for each segment of the path

[andreasplesch]

Yeah, but it does not know what t corresponds to a given x between the start and end points.

[mbostock]

I don’t have any plans to do evaluation of Bézier curves in this library. This library assumes you have an implementation of CanvasPathMethods (such as a Canvas context or a d3-path instance); it doesn’t evaluate the curves directly. I’d take a look at Bezier.js if you want something at that level of abstraction:

https://pomax.github.io/bezierjs/ https://pomax.github.io/bezierinfo/