Scripting: nearest oncurve point for a given coordinate
Guest last edited by gferreira
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
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
tvalue 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.
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
tso 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 :)
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_listmust be constructed in a way that the first entry is for
t = 0and 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_listis proportional to
t. Smaller increments of
tincrease the precision of the result, but the list takes longer to build.