立方贝塞尔曲线上的最近点到给定点 [英] Nearest point on cubic bezier curve to a given point

问题描述

我有一个定义为A，B，C，D的立方贝塞尔曲线。其中A是开始，B和C是控制点，D是结束。我知道如何找到位置的任意值t，其中0℃= T< = 1，和一般的概念，因为它仅仅使用呼叫导致在曲线的线性插值函数的屈指可数。 （可以轻松地在标题高级曲线下方在维基百科上可视化）

我现在正在寻找最接近空间某点的曲线上的点P. Google已经引导我进行多次讨论，但没有一个触发我的大脑里的神经元去哦！其实，说实话，他们都飞过我的头。

以下是Google带给我的一些地方：a。我的数学知识必须比我想要的更有限，

gamedev.net

stackoverflow.com（二次）

stackoverflow.com（关闭但我不明白）

其中包括在ActionScript中的实现，我似乎不能再次挖掘，我知道我发现它在这里的某个地方的回答/评论...

有没有人有知识和耐心帮助这个信息点击我的大脑？我正在考虑做足够接近的方法，并使用最接近的点在一条线上，只是迭代的曲线在非常小的步骤。这将很慢，精度会丢失。在我的特殊情况下，准确性不是一个关心的速度，但是，我觉得有一种方法有两个...

提前感谢。 p>

解决方案

正如cmaster所说，这导致五次多项式的求解找到六次多项式的最小值

如果是2D或3D，这并不重要。最小化函数是六次多项式

  f（t）= 0.5 * dot （t）-X），使得0≤t≤1
  

其中X是给定点和p（t）是多项式曲线， dot 表示欧几里德标量积。
最小化可以通过找到导数的所有根来实现。

  f'（t）= dot在时间间隔内部比较函数值（x，y）和函数值（x，x，y）根，并在时间间隔结束点
 
 
 
有也存在不使用的衍生物，主要用于那些比多项式更复杂的功能最小化的方法。例如，见
 
 
 
 Brent，RP（1973），最小化无衍生产品的算法，Englewood Cliffs，NJ：Prentice-Hall，ISBN 0-13-022335-2 
 
 
 
（其中包含关于导数和泰勒多项式的大量章节）。该方法或者其主要想法也可以在数值分析发现为黄金分割 。
 
I have a cubic-Bezier curve defined as A, B, C, D.  Where A is the start, B and C are control points, and D is the end.  I understand how to find the position at any value t, where 0 <= t <= 1, and that concept in general since it just uses a handful of calls to a linear interpolation function that result in the curve.  (Can be visualized easily here on wikipedia just below the heading Higher-order curves)

I am now looking to find a point on the curve that is closest to some point in space, P.  Google has led me to multiple discussions, but none of them trigger the neurons in my brain to go "ooh!"  Actually, to be quite honest they all fly right over my head.  My math knowledge must be a little more limited than I'd like, and falls to pieces when derivatives are mentioned.

Here are some of the places Google has led me:

gamedev.net

stackoverflow.com (quadratic)

stackoverflow.com (close but I don't understand it)

Among others including an implementation in ActionScript that I can't seem to dig up again, I know I found it in a answer/comment somewhere around here...

Does anyone have the knowledge and patience to help this information click into my brain?  I am considering doing the "close enough" approach and using the closest point on a line, and just iterating over the curve in very small steps.  This will be slow, and accuracy will be lost.  In my particular situation the accuracy is less of a concern than the speed, however, I feel there is a way to have both...

Thanks in advance.
解决方案
As cmaster says, this leads to the solution of a fifth degree polynomial to find the minimum of a sixth degree polynomial

It does not really matter if it is 2D or 3D. The function to minimize is the sixth degree polynomial
f(t)=0.5*dot(p(t)-X,p(t)-X) such that 0<=t<=1
where X is the given point and p(t) the polynomial curve, and dot denotes the euclidean scalar product.
Minimization can be achieved by finding all of the roots of the derivative 
f'(t)=dot(p'(t), p(t)-X)
inside the interval and comparing the function values of the roots and at the end points of the interval.

There also exist minimization methods that do not use derivatives, mainly intended for functions that are more complicated than polynomials. See for instance chapter 5 in

Brent, R. P. (1973), Algorithms for Minimization without Derivatives, Englewood Cliffs, NJ: Prentice-Hall, ISBN 0-13-022335-2

(which book nevertheless contains extensive sections on derivatives and Taylor polynomials). The method or its principal idea can also be found in "Numerical recipes" as "golden section search".

                        
这篇关于立方贝塞尔曲线上的最近点到给定点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！