[LegionMammal978]

This library has a very interesting algorithm for computing the curve point closest to a given point, seemingly based on a root-finder that doesn't need any complex numbers. Does anyone know of any resources about such an algorithm?

[CyLith]

The library only solves up to cubic equations, and the comments have a link to the following page: https://momentsingraphics.de/CubicRoots.html

For general polynomials, it matters a great deal in what basis it is represented. The typical monomial basis is usually not the best from a numerical standpoint. I am aware of some modern methods such as this: https://arxiv.org/pdf/1611.02435

For polynomials expressed in e.g. a Bernstein basis, there are often much faster and stable tailored methods working solving for the eigenvalues of a companion matrix of a different form.

[LegionMammal978]

That doesn't sound right, nearest-point queries for cubic Béziers take at least a quintic solver, and this library uses a subdivision-based algorithm with Bernstein polynomials that is seemingly designed to work with any degree [0]. (Or at least, it doesn't have any code that complains when the degree is too large.)

[0] https://github.com/GraphiteEditor/Graphite/blob/master/libra...

[bjornsing]

Reference sounds interesting but I’m getting 404 there.

[LegionMammal978]

My apologies, it looks like it was switched over [0] to an external root-finder crate poly-cool [1] soon after I wrote my comment. (I should know better than to link to branches directly, but there weren't any useful tags on the repo, so I got lazy. For reference, I was trying to link to [2].)

Curiously, the poly-cool crate appears to use the monomial basis instead of the Bernstein basis that the old version was using.

[0] https://github.com/GraphiteEditor/Graphite/pull/3031

[1] https://crates.io/crates/poly-cool

[2] https://github.com/GraphiteEditor/Graphite/blob/beb1c6ae6489...

[bjornsing]

Interesting, thanks!