MicroCAN

03-29-2001, 09:03 PM

I am searching for an algorithm to find the distance between a point and a cubic bezier curve.

Can anybody help?

Can anybody help?

View Full Version : Cubic bezier curve picking

MicroCAN

03-29-2001, 09:03 PM

I am searching for an algorithm to find the distance between a point and a cubic bezier curve.

Can anybody help?

Can anybody help?

Relic

03-30-2001, 12:13 AM

From top of my head: I would tesselate the Bezier curve as small lines and calculate the orthogonal projection from the point to the line. If it hits the line, means the footpoint of the orthogonal projection is between the begin- and end-point of the line (factor lambda: 0 <= lambda <= 1 in vector equation), then store the distance.

Repeat for all line segments and find the minimum distance.

I don't have code and it doesn't sound very fast(?).

Repeat for all line segments and find the minimum distance.

I don't have code and it doesn't sound very fast(?).

martin_marinov

03-30-2001, 01:00 AM

Hi,

Since the cubic bezier curve is in fact a polynomial curve, you can easy find the derivatives of its coordinate functions - lets say the Bezier curve is c(t) = (x(t), y(t))so you can express easy its derivative - using the standart polynomial basis or the Bernstein basis. After finding it you recieve a function T(t) which gives you the tangent of c(t) in the point c(t). Let's say your point is P(x,y). Then using some equation solver you must find the solution(s) of the equation ( P - c(t))*T(t) = 0

(here * is scalar multiplication over the vectors space, note that this is the condition which says that the vector

(P - c(t)) is perpendicular to the tangent

T(t) )

The found t is the parameter value for the point c(t) - which is the "closest" point laying on c(t) to P(x,y). Note that t may be not unique - take for example a closed curve - it may have two points which satisfy the equation above. Note also that if t is not in [0..1], then the c(t) in not actully laying on the curve...

But if you just need to select the curve using OpenGL, then use selection buffer - it will not slow down and you will not need to do the all math above ( which is not so so simple anyway)

Hope this helps

Martin

Since the cubic bezier curve is in fact a polynomial curve, you can easy find the derivatives of its coordinate functions - lets say the Bezier curve is c(t) = (x(t), y(t))so you can express easy its derivative - using the standart polynomial basis or the Bernstein basis. After finding it you recieve a function T(t) which gives you the tangent of c(t) in the point c(t). Let's say your point is P(x,y). Then using some equation solver you must find the solution(s) of the equation ( P - c(t))*T(t) = 0

(here * is scalar multiplication over the vectors space, note that this is the condition which says that the vector

(P - c(t)) is perpendicular to the tangent

T(t) )

The found t is the parameter value for the point c(t) - which is the "closest" point laying on c(t) to P(x,y). Note that t may be not unique - take for example a closed curve - it may have two points which satisfy the equation above. Note also that if t is not in [0..1], then the c(t) in not actully laying on the curve...

But if you just need to select the curve using OpenGL, then use selection buffer - it will not slow down and you will not need to do the all math above ( which is not so so simple anyway)

Hope this helps

Martin

MicroCAN

03-30-2001, 01:31 AM

Thanks for the reply. I am working on a cubic bezier curve editor. I like to use the closest point for picking and for changing the curve. Splitting the curve, dragging the curve as is done in CorelDraw. The picking of the control points was easy and editing the curve with the tangential controls is already implemented.

Powered by vBulletin® Version 4.2.3 Copyright © 2016 vBulletin Solutions, Inc. All rights reserved.