为给定坐标的贝塞尔曲线找到合适的参数值

Question

我正在从事一个涉及贝塞尔曲线的项目，但我无法找到 [0, 1] 范围内对应于贝塞尔曲线上特定位置的值 t。我设置了一个测试，我将 t 的增量值（特别是增量为 0.001 到 1）放入贝塞尔曲线的 x 和 y 参数方程中，然后减去它值与真实值，如果它在 x 和 y 的小阈值内，我找到了一个合适的 t。不幸的是，t 似乎没有与所需坐标相对应的单个值。这意味着循环实际上在 for 循环中的条件没有成功的情况下完成。

应该在曲线上的坐标是(75, -2.26384401)。我把我的代码放在下面，它显示了控制点的坐标以及真实的 x 和 y 坐标。任何帮助将不胜感激。谢谢！

int _tmain(int argc, _TCHAR* argv[])
{
float P0[2] = { 55, -11.105 };
float P1[2] = { 72.569, -11.105 };
float P2[2] = { 50.217, 1.396 };
float P3[2] = { 100, 1.396 };

float t = 1.0F;
float int_t = t / 1000; // intervals
float x;
float y;
float tx = 75.0000000F; // where it should be in x
float ty = -2.26384401F; // where it should be in y
float epsilon = 0.01;
float final_t;

for (float i = 0; i < t; i += int_t)
{
    final_t = i;
    x = powf(1.0F - i, 3.0F)*P0[0] + 3.0F*powf(1.0F - i, 2.0F)*i*P1[0] + 
        3.0F*(1.0F - i)*powf(i, 2.0F)*P2[0] + powf(i, 3.0F)*P3[0]; // x(t)

    y = powf(1.0F - i, 3.0F)*P0[1] + 3.0F*powf(1.0F - i, 2.0F)*i*P1[1] + 
        3.0F*(1.0F - i)*powf(i, 2.0F)*P2[1] + powf(i, 3.0F)*P3[1]; // y(t)

    // for my testing
    cout << "---------------------------------" << endl;
    cout << "i = " << i << endl;
    cout << "x = " << x << endl;
    cout << "y = " << y << endl;
    cout << "---------------------------------" << endl;

    if ((fabsf(x - tx) <= epsilon) && (fabsf(y - ty) <= epsilon))
        break;
}
cout << endl;
cout << "x = " << x << endl;
cout << "y = " << y << endl;
cout << "t = " << final_t << endl;

return 0;
}

Answer 1

简单的方法是使用三次求解器。

现在求解 x 和 y。如果该点确实在曲线上，您将获得相同的 t 值。可能有点偏差，所以把 ts 换回去，取最近的一个。

系数是

  DX = m_P0.x;
  CX = 3.0f * ( m_P1.x - m_P0.x );
  BX = ( 3.0f * m_P2.x ) - ( 6.0f * m_P1.x ) + ( 3.0f * m_P0.x );
  AX = m_P3.x - ( 3.0f * m_P2.x ) + ( 3.0f * m_P1.x ) - m_P0.x;

对 y 做同样的事情。

现在解立方AXt^3 + BXt^2 + CXt + DX - px = 0 求出三个 t 的根。对 y 做同样的事情，并找到 t 的三个根。

现在我们有 6 个根。有些可能很复杂，所以忽略。所以可能在区间 0 - epsilon、1 + epsilon 之外（允许有一点倾斜）所以忽略。如果点 px, py 恰好在曲线上，则两个 t 值将在 0-1 上且相同，这就是您的答案。实际上，这一点会有点偏离。因此，将所有（最多 6 个）t 值替换回贝塞尔曲线并得到 x、y。至少一对 x,y 应该非常接近 px, py，除了可能非常接近尖点的点。

如果你有两个接近点并且 px py 在它们之间的间隔上，你可以进一步完善你的答案。

Answer 2

你的问题是输入点 Pt(tx,ty) 根本不在 BEZIER (P0,P1,P2,P3) 曲线上。因此，到曲线的距离总是 比你的小 epsilon 大得多 ，无论你发现 t 有多接近......

这是它的样子：

BEZIER 曲线呈灰色。绿色 X 是输入 (tx,ty) 点，红色 + 是在曲线 t=0.753

上找到的最近点

这里是 C++/VCL 代码，我用：

//---------------------------------------------------------------------------
#include <math.h>
#include "approx.h"
double P0[2] = { 55, -11.105 };
double P1[2] = { 72.569, -11.105 };
double P2[2] = { 50.217, 1.396 };
double P3[2] = { 100, 1.396 };

double Pt[2] = { 75.0000000,-2.26384401 };
//---------------------------------------------------------------------------
void BEZIER_getxy(double *p0,double *p1,double *p2,double *p3,double &x,double &y,double  t) // return x,y of point on BEZIER curve for t
    {
    double a0,a1,a2,a3,tt,ttt;
    tt=t*t; ttt=tt*t;
    a0=                                    (    p0[0]);
    a1=                        (3.0*p1[0])-(3.0*p0[0]);
    a2=            (3.0*p2[0])-(6.0*p1[0])+(3.0*p0[0]);
    a3=(    p3[0])-(3.0*p2[0])+(3.0*p1[0])-(    p0[0]);
    x=a0+(a1*t)+(a2*tt)+(a3*ttt);
    a0=                                    (    p0[1]);
    a1=                        (3.0*p1[1])-(3.0*p0[1]);
    a2=            (3.0*p2[1])-(6.0*p1[1])+(3.0*p0[1]);
    a3=(    p3[1])-(3.0*p2[1])+(3.0*p1[1])-(    p0[1]);
    y=a0+(a1*t)+(a2*tt)+(a3*ttt);
    }
//---------------------------------------------------------------------------
void BEZIER_gett (double *p0,double *p1,double *p2,double *p3,double  x,double  y,double &t) // return t which is closest to (x,y)
    {
    double e,xx,yy;
    approx at;
    for (at.init(0.0,1.0,0.1,3,&e);!at.done;at.step())  // search t
        {
        BEZIER_getxy(p0,p1,p2,p3,xx,yy,at.a);
        xx-=x; xx*=xx;
        yy-=y; yy*=yy;
        e=xx+yy; // error is distance between points ^ 2
        }
    t=at.aa;
    }
//---------------------------------------------------------------------------
void BEZIER_draw (double *p0,double *p1,double *p2,double *p3,TCanvas *can,double x0,double y0,double zoom) // just render curve with VCL/GDI
    {
    int e;
    double x,y,t;
    BEZIER_getxy(p0,p1,p2,p3,x,y,0.0);
    x=x0+(x*zoom);
    y=y0-(y*zoom);
    can->MoveTo(x,y);
    for (e=1,t=0.0;e;t+=0.02)
        {
        if (t>=1.0) { e=0; t=1.0; }
        BEZIER_getxy(p0,p1,p2,p3,x,y,t);
        x=x0+(x*zoom);
        y=y0-(y*zoom);
        can->LineTo(x,y);
        }
    }
//---------------------------------------------------------------------------
void TMain::draw() // this is just my window redraw routine
    {
    if (!_redraw) return;

    // clear buffer
    bmp->Canvas->Brush->Color=clBlack;
    bmp->Canvas->FillRect(TRect(0,0,xs,ys));
    double x0=-40.0,y0=170.0,zoom=3.0;  // view
    double x,y,w=10,t;

    // whole BEZIER curve (Gray curve)
    bmp->Canvas->Pen->Color=clDkGray;
    BEZIER_draw(P0,P1,P2,P3,bmp->Canvas,x0,y0,zoom);

    // input point Pt (Green X)
    bmp->Canvas->Pen->Color=0x0000FF00;
    x=x0+(Pt[0]*zoom);
    y=y0-(Pt[1]*zoom);
    bmp->Canvas->MoveTo(x-w,y-w);
    bmp->Canvas->LineTo(x+w,y+w);
    bmp->Canvas->MoveTo(x+w,y-w);
    bmp->Canvas->LineTo(x-w,y+w);

    // closest point (Red +)
    bmp->Canvas->Pen->Color=clRed;
    BEZIER_gett (P0,P1,P2,P3,Pt[0],Pt[1],t);
    BEZIER_getxy(P0,P1,P2,P3,x,y,t);
    x=x0+(x*zoom);
    y=y0-(y*zoom);
    bmp->Canvas->MoveTo(x-w,y);
    bmp->Canvas->LineTo(x+w,y);
    bmp->Canvas->MoveTo(x,y-w);
    bmp->Canvas->LineTo(x,y+w);

    Caption=t;

    // render backbuffer
    Main->Canvas->Draw(0,0,bmp);
    _redraw=false;
    }
//---------------------------------------------------------------------------

因为我懒得调试你的代码，所以我使用了 BEZIER 三次求解器我的 approx class 来自这个相关的 质量保证:

在搜索本身中，我为 t=<0.0,1.0> 设置了搜索参数，步骤 0.1 和 3 递归导致 0.1/10^(3-1) 最终精度为 t，即0.001 作为您的 int_t 步骤，但解决方案是在 30 步骤而不是您的 1000

要补救您的代码，只需记住 x,y,t 到 tx,ty 的最小距离，而不仅仅是 distance<=epsilon

的距离

为给定坐标的贝塞尔曲线找到合适的参数值

Finding the proper parametric value for a bezier curve given a coordinate

algorithm

math

graphics

bezier