Closest point on a cubic Bezier curve?

views:

337

answers:

+2 Q:

Closest point on a cubic Bezier curve?

How can I find the point B(t) along a cubic Bezier curve that is closest to an arbitrary point P in the plane?

Here is a good reference with an implementation in basic:

http://www.tinaja.com/glib/bezdist.pdf

drawnonward 2010-04-30 06:11:06

The link concerns the closest point on the curve to a point, but the OP asks for closest point on the curve to a plane.

Andreas Brinck 2010-04-30 06:46:19

I took 'in the plane' to imply a 2D curve, in which case it is the same thing. If it is a 3D curve, then I was not helpful at all.

drawnonward 2010-04-30 07:52:02

I'm indeed concerned with finding the closest point on a 2D curve. In other words, the curve and the input point both lie on the same plane.

Adrian Lopez 2010-04-30 14:22:18

After looking at the linked PDF, I think I'm looking for something more descriptive -- more like an academic paper. As it is, I'm not sure I understand what the algorithm being described really does.

Adrian Lopez 2010-04-30 16:27:44

Nothing about distance, but this is a fun page to read if you are just interested in bezier curves: http://www.redpicture.com/bezier/bezier-01.html

drawnonward 2010-04-30 18:57:39

Have a look at this page of The Algoritmist. You can see demo and source of algorithm.

alt text

Sorush Rabiee 2010-04-30 13:55:06

Thanks, but I wish to write my own code rather than use somebody else's and the link you provided unfortunately does not include a description of the algorithm used.

Adrian Lopez 2010-04-30 14:28:05

+1 A:

After lots of searching I found a paper that discusses a method for finding the closest point on a Bezier curve to a given point:

Improved Algebraic Algorithm On Point Projection For Bezier Curves, by Xiao-Diao Chen, Yin Zhou, Zhenyu Shu, Hua Su, and Jean-Claude Paul.

Furthermore, I found Wikipedia and MathWorld's descriptions of Sturm sequences useful in understanding the first part of the algoritm, as the paper itself isn't very clear in its own description.

Adrian Lopez 2010-05-01 17:09:00

+1 A:

Adrian:

The Graphic Gems (I) algorithm was used in the example, which is also provided in C. You can get the original algorithm from the GC book and roll your own as desired. My code works for a quad or cubic, the code supplied in the GC book is for a cubic.

hope that helps,

jim armstrong

Jim Armstrong 2010-06-22 12:17:28

ansaurus

tags:

views:

answers:

Closest point on a cubic Bezier curve?

related questions