How to find a point (if any) on quadratic Bezier with a given tangent direction?

Question

I'm currently working on a python library to extract pen strokes from TrueType fonts - Here I'm defining a stroke as a midline running between a test point and its reflected point. I'm using the term reflected point to refer to the closest point on the opposite side of the 'ink' region which under normal circumstances (apart from say at a serif stem) would also have a tangent in the opposite direction to the test point.

I'm working in python using fontTools and a bezier library that I rolled from the processing code described at http://pomax.github.io/bezierinfo/#extremities .

Where I'm stuck stuck at the moment is on how to find the point on a quadratic bezier curve that has a given tangent, my mathematics skills are pretty rudimentary on a good day with a clear head [which it is not rite now] so I was hoping someone with a sharper mind could point out a birds eye overview on how to achieve this.

At the moment the only thing I can think of is to approach it numerically with something similar to the Newton-Raphson root finding algorithm but evaluating the 1st derivative against the target direction values. I am hoping however there is a symbolic solution as this needs to be run on every other curve for each curve in the glyphs contours.

Answer 1

Using the notation given in http://pomax.github.io/bezierinfo/#extremities, a quadratic Bezier curve is given by:

B(t) = P1*(1-t)**2 + 2*P2*(1-t)*t + P3*t**2

Therefore, (by taking the derivative of B with respect to t) the tangent to the curve is given by

B'(t) = -2*P1*(1-t) + 2*P2*(1-2*t) + 2*P3*t
      = 2*(P1 - 2*P2 + P3)*t + 2*(-P1 + P2)

Given some tangent direction V, solve

B'(t) = V

for t. If there is a solution, t = ts, then the point on the Bezier curve which has tangent direction V is given by B(ts).

---

We essentially want to know if two vectors (B'(t) and V) are parallel or anti-parallel. There is a trick to doing that.

Two vectors, X and Y, are perpendicular if their dot product is zero. If X = (a,b) and Y = (c,d) then the dot product of X and Y is given by

a*c + b*d

So, X and Y are parallel if X and Y_perp are perpendicular, where Y_perp is a vector perpendicular to Y.

In 2-dimensions, if in coordinates Y = (a,b) then Y_perp = (-b, a). (There are two perpendicular vectors possible, but this one will do.) Notice that -- using the formula above -- the dot product of Y and Y_perp is

a*(-b) + b*(a) = 0

So indeed, this jibes with the claim that perpendicular vectors have a dot product equal to 0.

Now, to solve our problem: Let

B'(t) = (a*t+b, c*t+d)
V = (e, f)

Then B'(t) is parallel (or anti-parallel) to V if or when B'(t) is perpendicular to V_perp, which occurs when

dot product((a*t+b, c*t+d), (-f, e)) = 0
-(a*t+b)*f + (c*t+d)*e = 0

We know a, b, c, d, e and f. Solve for t. If t lies between 0 and 1, then B(t) is part of the Bezier curve segment between P1 and P3.

Answer 2

Thanks to @ubutbu for pointing out the solution for me, figured I would post a working implementation in case someone googles upon this question with a need in the future:

def findParallelT(P, V):
    """finds the t value along a quadratic Bezier such that its tangent (1st derivative) is parallel with the direction vector V.
        P : a 3x2 matrix containing the control points of B(t).
        V : a pair of values representing the direction of interest (magnitude is ignored).
        returns 0.0 <= t <= 1.0 or None
        Note the result may be in the same direction or flipped 180 degrees from V"""
    #refer to answer given by 'unutbu' on the stackoverflow question:
    #http://stackoverflow.com/questions/20825173/how-to-find-a-point-if-any-on-quadratic-bezier-with-a-given-tangent-direction
    #for explanation.
    # also the 'Rearrange It' app at http://www.wolframalpha.com/widgets/view.jsp?id=4be4308d0f9d17d1da68eea39de9b2ce was invaluable.
    assert len(P)==3 and len(P[0])==2 and len(P[1])==2 and len(P[2])==2
    assert len(V)==2
    P1=P[0]
    P2=P[1]
    P3=P[2]

    # B(t) = P1 * (1-t)**2 + 2*P2*(1-t)*t + P3*t**2
    # B'(t) = 2 * (1-t) * (P2 - P1) + 2*t*(P3-P2)
    # B'(t) = (a*t + b, c*t + d), V = (e, f)
    a = -2 * (P2[0] - P1[0]) + 2 * (P3[0]-P2[0])
    b = 2 * (P2[0] - P1[0])
    c = -2 * (P2[1] - P1[1]) + 2 * (P3[1]-P2[1])
    d = 2 * (P2[1] - P1[1])
    e = V[0]
    f = V[1]

    # -(a*t+b)*f + (c*t+d)*e = 0 for parallel... t = (d*e - b*f) / (a*f - c*e)
    num = float(d * e - b * f)
    den = float(a * f - c * e)
    if den == 0:
        return None
    else:
        t = num / den
    return t if 0.0 <= t <= 1.0 else None

if __name__ == "__main__":
    assert findParallelT([[0.0,0.0], [0.0,25.0], [25.0,25.0]], [25.0,25.0]) == 0.5
    assert findParallelT([[0.0,0.0], [0.0,25.0], [25.0,25.0]], [25.0,-25.0]) == None
    assert findParallelT([[200.0,200.0], [10.0, 20.0], [300.0, 0.0]], [10.0,0.0]) == None
    assert findParallelT([[407.5, 376.5],[321.0,463.0],[321.0,586.0]], [-246.0,0.0] ) == None
    assert findParallelT([[617.0, 882.0],[740.0, 882.0], [826.5, 795.5]], [-245.0,0.0]) == 0.0

Answer 3

shadertoy.com has a search function and "bezier" gets you to analytic solutions for calculation (over 2 domains)

• The shortest distance of any planar point to a planar quadratic-bezier, by calculating 2 roots of a cubic function (quadratic Bezier will only have 2 real roots) (euclidean distance increases exponent of polynomial by +1).
• 3 points on the Bezier that equate to the 3 local extrema of the cubic function, one for each root of the quadratic.
• • so you just calculate which of the 3 points is closest.