Closest point on Bezier spline - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T12:47:31Z http://mathoverflow.net/feeds/question/8983 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/8983/closest-point-on-bezier-spline Closest point on Bezier spline David Rutten 2009-12-15T13:00:43Z 2009-12-15T15:44:29Z <p>Given a two-dimensional cubic bezier spline defined by 4 control-points as described <a href="http://en.wikipedia.org/wiki/B%C3%A9zier%5Fcurve#Cubic%5FB.C3.A9zier%5Fcurves" rel="nofollow">here</a>, is there a way to solve analytically the parameter along the curve (0.0 to 1.0 parameter domain) which is closest to an arbitrary point in space?</p> <p><strong>B</strong>(<em>t</em>) = (1-<em>t</em>)<sup>3</sup> <strong>P</strong><sub>0</sub> + 3(1-<em>t</em>)<sup>2</sup> <em>t</em><strong>P</strong><sub>1</sub> + 3(1-<em>t</em>) <em>t</em><sup>2</sup><strong>P</strong><sub>2</sub> + <em>t</em><sup>3</sup><strong>P</strong><sub>3</sub>, <em>t</em> E [0,1]</p> <p>where <strong>P</strong><sub>0</sub>, <strong>P</strong><sub>1</sub>, <strong>P</strong><sub>2</sub> and <strong>P</strong><sub>3</sub> are the 4 control-points of the curve.</p> <p>I can solve it pretty reliably and quickly with a divide-and-conquer algorithm, but it makes me feel dirty...</p> <p>-- David Rutten</p> http://mathoverflow.net/questions/8983/closest-point-on-bezier-spline/8997#8997 Answer by Greg Kuperberg for Closest point on Bezier spline Greg Kuperberg 2009-12-15T15:44:29Z 2009-12-15T15:44:29Z <p>If you have a Bezier curve \$(x(t),y(t))\$, the closest point to the origin (say) is given by the minimum of \$f(t) = x(t)^2 + y(t)^2\$. By calculus, this minimum is either at the endpoints or when the derivative vanishes, \$f'(t) = 0\$. This latter condition is evidently a quintic polynomial. Now, there is no exact formula in radicals for solving the quintic. However, there is a really nifty new iterative algorithm based on the symmetry group of the icosahedron <a href="http://math.dartmouth.edu/~doyle/docs/icos/icos.pdf" rel="nofollow">due to Doyle and McMullen</a>. They make the point that you use a dynamical iteration anyway to find radicals via Newton's method; if you think of a quintic equation as a generalized radical, then it has an iteration that it just as robust numerically as finding radicals with Newton's method.</p> <p>Contrary to what lhf said, Cardano's formula for the cubic polynomial is perfectly stable numerically. You just need arithmetic with complex numbers even if, indeed exactly when, all three roots are real.</p> <p>There is also a more ordinary approach to finding real roots of a quintic polynomial. (Like Cardano's formula, the Doyle-McMullen solution requires complex numbers and finds the complex roots equally easily.) Namely, you can use a cutoff procedure to switch from divide-and-conquer to Newton's method. For example, if your quintic \$q(x)\$ on a unit interval \$[0,1]\$ is \$40-100x+x^5\$, then it is clearly close enough to linear that Newton's method will work; you don't need divide-and-conquer. So if you have cut down the solution space to any interval, you can change the interval to \$[0,1]\$ (or maybe better \$[-1,1]\$), and then in the new variable decide whether the norms of the coefficients guarantee that Newton's method will converge. This method should only make you feel "a little dirty", because for general high-degree polynomials it's a competitive numerical algorithm. (Higher than quintic, maybe; Doyle-McMullen is really pretty good.)</p> <p>See also <a href="http://mathoverflow.net/questions/5760/can-grobner-bases-be-used-to-compute-solutions-to-large-real-world-problems" rel="nofollow">this related MO question</a> on the multivariate situation, which you would encounter for bicubic patches in 3D. The multivariate situation is pretty much the same: You have a choice between polynomial algebra and divide-and-conquer plus Newton's method. The higher the dimension, the more justification there is for the latter over the former.</p>