CODEWITHSUNDEEP
containspointbezier
Ky -
Ky -

Reputation: 32083

How can I tell if a point is on a quadratic Bézier curve within a given tolerance?

I'm writing a library for Bézier curves. I already can calculate the curve as a collection of connected points to a given resolution, but I now need to do the reverse; detect whether a given point is on the curve within a given tolerance (e.g. 0.0001). Is there a simple mathematical function that can do this?

Please phrase your answer in the form of a function that takes in three parameters: the x and y coordinates and a tolerance (distance from curve still considered "on" it), and which outputs a Boolean value. This will make it more generally useful to others. For example, such a function in Swift would have the signature func isOnCurve(x: Float, y: Float, tolerance: Float) -> Bool

Upvotes: 2

Views: 1548

Answers (3)

Mike 'Pomax' Kamermans
Mike 'Pomax' Kamermans

Reputation: 53578

You could exploit the "distance to curve" method described over at https://pomax.github.io/bezierinfo/#projections, but this will find a single t value for any coordinate. For "is this point on the curve?" checks, that's fine (multiple t values do not change the answer; 0 is off-curve, 1 is on-curve, 2 or more is still on-curve).

Sample the curve at a few (relatively close-spaced) values for t (which I assume for efficiency you already do in order to only compute draw coordinates once, rather than every time the curve needs to be drawn), and then with the closest t that yields, start walking the curve, reducing the distance until you've found the minimal distance (how you walk is up to you: you can do a coarse-to-fine walk, or start off fine, or determine how far to jump based on the curve tangent, etc).

Then your result is literally just return minDistance <= tolerance.

Upvotes: 3

kuribas
kuribas

Reputation: 11

You want to find the parameter on the curve which is closest to the point, then you can find the distance. If you have a bezier curve B(t), and a point P, then solve

(P-B(t))⋅B'(t) = 0.

For a quadratic bezier this gives a cubic equation which can be solved analytically. Alternatively you can use a iterative solver. The minimal distance is then ||P-B(t)||.

Upvotes: 0

fang
fang

Reputation: 3623

For a quadratic Bezier curve defined as

C(t) = P0(1-t)^2+2P1t(1-t)+P2t^2 = P0+2(P1-P0)t+(P0-2P1+P2)t^2,

for a given point Q to lie on C(t) there must exist a solution for t between 0 and 1 that satisfies

(P0-Q)+2(P1-P0)t+(P0-2P1+P2)t^2 = 0

Therefore, you can try to find the common real root for the following two equations

(P0x-2P1x+2P2x)t^2+2(P1x-P0x)t+(P0x-Qx) = 0
(P0y-2P1y+2P2y)t^2+2(P1y-P0y)t+(P0y-Qy) = 0

If such a common real root exist and it is between 0 and 1, it means point Q lies on the curve.

For cubic Bezier curve, you can follow this procedure in a similar way but you will have to find the roots for a cubic equation.

Upvotes: 0

Related Questions