Scripting: nearest oncurve point for a given coordinate

Dear Robofonters,

I've just started testing this wonderful app for the first time in my life and I'm planning to rewrite my (at least for me) very useful plugin from the GlyphsApp: StemThickness.

For this purpose I need to find the nearest on-curve point for the coordinate of the cursor point. And I've found it:
(here: https://groups.google.com/forum/#!topic/robofab/YAG1RQO_mcc )

Right now I'm looking for something I would call "time of the on-curve point". This is the ratio needed for further calculation for my extension.

Following equation is the standard equation for the bezier curve.

I have given B (coordinates of the nearest on-curve point), A, B, C, D (curve's control points). I'm looking for t value:

B = (1 – t)^3*A + 3*(1 – t)^2 *t*B + 3*(1 – t) *t^2 *C + t^3 * D,
0 <= t <= 1, t=?

Do you guys know any fast method for finding t value of given on-curve point and bezeir curve's control points?

I hope that this message is quite clear :) I'm not the best at explaining math stuff at forums.

Cheers
Rafał

jens

I found a way to speed up the brute force approach though. If you can use external Python modules:

from scipy import spatial

tree = spatial.KDTree(t_list) # t_list is a list of pre-calculated point coordinate tuples on the cubic curve
distance, index = tree.query(pt) # pt is the given point coordinate tuple
t_for_pt = float(index) / (len(tree.data) - 1)

t_list must be constructed in a way that the first entry is for t = 0 and the last entry for t = 1. It doesn't matter how many points for increments of t you calculate, as long as the index in t_list is proportional to t. Smaller increments of t increase the precision of the result, but the list takes longer to build.

jens

I have looked for a solution to this myself, and actually ended up taking your numerical approach from the Glyphs plugin ;)

As I understand it, there may not be a solution to the equation if the given point is not exactly on the curve, which may already happen because floating point numbers are not exact. So you need to find t so that the distance of P(t) to the given point is minimized.

This stackexchange answer may be something, but I didn’t understand the stuff about inversions: https://math.stackexchange.com/a/535785

If you can make any sense of it, I am very interested :)