如何获得最接近给定点的三次贝塞尔曲线？
给定 n 个点：
p0, p1, p2, ..., pn；
如何获得点 c1、c2，以便由
p0、c1、c2、pn
定义的三次贝塞尔曲线最接近给定点？
我尝试了最小二乘法。我在阅读 http://www.mathworks 中的 pdf 文档后写了这篇文章。 com/matlabcentral/fileexchange/15542-cubic-bezier-least-square-fitting。但我找不到好的 t(i) 函数。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows;
namespace BezierFitting
{
class CubicBezierFittingCalculator
{
private List<Point> data;
public CubicBezierFittingCalculator(List<Point> data)
{
this.data = data;
}
private double t(int i)
{
return (double)(i - 1) / (data.Count - 1);
// double s = 0.0, d = 0.0;
//
// for (int j = 1; j < data.Count; j++)
// {
// if (j < i)
// {
// s += (data[j] - data[j - 1]).Length;
// }
// d += (data[j] - data[j - 1]).Length;
// }
// return s / d;
}
public void Calc(ref Point p1, ref Point p2)
{
double n = data.Count;
Vector p0 = (Vector)data.First();
Vector p3 = (Vector)data.Last();
double a1 = 0.0, a2 = 0.0, a12 = 0.0;
Vector c1 = new Vector(0.0, 0.0), c2 = new Vector(0.0, 0.0);
for (int i = 1; i <= n; i++)
{
double ti = t(i), qi = 1 - ti;
double ti2 = ti * ti, qi2 = qi * qi;
double ti3 = ti * ti2, qi3 = qi * qi2;
double ti4 = ti * ti3, qi4 = qi * qi3;
a1 += ti2 * qi4;
a2 += ti4 * qi2;
a12 += ti3 * qi3;
Vector pi = (Vector)data[i - 1];
Vector m = pi - qi3 * p0 - ti3 * p3;
c1 += ti * qi2 * m;
c2 += ti2 * qi * m;
}
a1 *= 9.0;
a2 *= 9.0;
a12 *= 9.0;
c1 *= 3.0;
c2 *= 3.0;
double d = a1 * a2 - a12 * a12;
p1 = (Point)((a2 * c1 - a12 * c2) / d);
p2 = (Point)((a1 * c2 - a12 * c1) / d);
}
}
}
获得最接近给定点的三次贝塞尔曲线的最佳方法是什么？
例如，这里有 30 个点：
22, 245
26, 240
39, 242
51, 231
127, 189
136, 185
140, 174
147, 171
163, 162
169, 155
179, 107
181, 147
189, 168
193, 187
196, 75
199, 76
200, 185
201, 68
204, 73
205, 68
208, 123
213, 118
216, 210
216, 211
218, 68
226, 65
227, 110
228, 102
229, 87
252, 247
这些点分布在由四个点控制的三次贝塞尔曲线周围：
P0 (0, 256)、P1 (512, 0)、P2 (0, 0)、P3 (256, 256) 。
假设曲线是从(0, 256)到(256, 256)，如何得到靠近原点的剩余两个控制点？
Given n points:
p0, p1, p2, ..., pn;
How can I get the point c1, c2 so that the cubic bezier curve defined by
p0, c1, c2, pn
closest to the given points?
I tried least square method. I wrote this after I read the pdf document in http://www.mathworks.com/matlabcentral/fileexchange/15542-cubic-bezier-least-square-fitting. But I can't find a good t(i) function.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows;
namespace BezierFitting
{
class CubicBezierFittingCalculator
{
private List<Point> data;
public CubicBezierFittingCalculator(List<Point> data)
{
this.data = data;
}
private double t(int i)
{
return (double)(i - 1) / (data.Count - 1);
// double s = 0.0, d = 0.0;
//
// for (int j = 1; j < data.Count; j++)
// {
// if (j < i)
// {
// s += (data[j] - data[j - 1]).Length;
// }
// d += (data[j] - data[j - 1]).Length;
// }
// return s / d;
}
public void Calc(ref Point p1, ref Point p2)
{
double n = data.Count;
Vector p0 = (Vector)data.First();
Vector p3 = (Vector)data.Last();
double a1 = 0.0, a2 = 0.0, a12 = 0.0;
Vector c1 = new Vector(0.0, 0.0), c2 = new Vector(0.0, 0.0);
for (int i = 1; i <= n; i++)
{
double ti = t(i), qi = 1 - ti;
double ti2 = ti * ti, qi2 = qi * qi;
double ti3 = ti * ti2, qi3 = qi * qi2;
double ti4 = ti * ti3, qi4 = qi * qi3;
a1 += ti2 * qi4;
a2 += ti4 * qi2;
a12 += ti3 * qi3;
Vector pi = (Vector)data[i - 1];
Vector m = pi - qi3 * p0 - ti3 * p3;
c1 += ti * qi2 * m;
c2 += ti2 * qi * m;
}
a1 *= 9.0;
a2 *= 9.0;
a12 *= 9.0;
c1 *= 3.0;
c2 *= 3.0;
double d = a1 * a2 - a12 * a12;
p1 = (Point)((a2 * c1 - a12 * c2) / d);
p2 = (Point)((a1 * c2 - a12 * c1) / d);
}
}
}
What's the best way to get a cubic bezier curve closest to given points?
For example, here are 30 points:
22, 245
26, 240
39, 242
51, 231
127, 189
136, 185
140, 174
147, 171
163, 162
169, 155
179, 107
181, 147
189, 168
193, 187
196, 75
199, 76
200, 185
201, 68
204, 73
205, 68
208, 123
213, 118
216, 210
216, 211
218, 68
226, 65
227, 110
228, 102
229, 87
252, 247
Those points are distributed around the the cubic bezier curve controled by four points:
P0 (0, 256), P1 (512, 0), P2 (0, 0), P3 (256, 256).
Suppose the curve is from (0, 256) to (256, 256), how to get rest two control points close to the origional points?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
您可能想看看 此页面
这是一个非常好的实现，尽管正如作者所写：“这种方法是纯粹的启发式方法，从严格的数学建模的角度来看，它可能会给出错误的结果，但实际上结果足够好，并且需要绝对最少的计算。“
它是用 C++ 编写的，但很容易移植到任何语言......
将你的每条“边缘”传递给控制点计算函数，然后通过贝塞尔曲线计算函数，你就得到了它。
要对多边形执行贝塞尔曲线平滑，请通过最后一个点和第一个点传递最后一条边。
You might want to have a look at this page
It's a very good implementation, though as the author writes : "This method is pure heuristic and empiric. It probably gives a wrong result from the point of view of strict mathematical modeling. But in practice the result is good enough and it requires absolute minimum of calculations. "
It's in C++ but is really easily portable to any language...
Pass each of your "edges" through the control points calculation function, then through the bezier calculation one, and you have it.
To perform bezier smooth on a polygon, pass a last edge with your last and first point.
（三次）贝塞尔曲线是一种定义三次参数样条的方法，其一般形式为 P=A*t^3+B*t^2+C*t+D，其中 P、A、B、C 和 D 是 (二维（即矢量）权重。使用伯恩斯坦多项式，您可以计算给定四个控制点 P0、P1、P2 和 P3 的权重 A、B、C 和 D，正如几乎所有矢量绘图程序中已知的那样。
由于您只有四个控制点，但想要拟合任意数量的任意点，因此我怀疑没有唯一的解决方案。例如，给定输入 (0,0)、(1,0)、(1,1) 和 (0,1)，对于每个“最佳”解决方案（无论它是什么），您可以通过镜像来构建等效解决方案沿主对角线绘制样条线。
解决此类问题有一个通用方法，即为所有点到通用贝塞尔曲线（即由变量 A、B 定义的曲线）的距离平方和构建一个方程， C 和 D），计算第一个导数并将其设置为零，并求解 A、B、C 和 D 的结果系统。这通常会导致线性方程组（抱歉，这需要我一些时间来进行数学计算） ，它是自从我这样做以来已经很长时间了......）。但是，正如我所说，我认为对于您的问题，这不会产生独特的解决方案。
如果您在输入点上定义顺序，即您想使用单个贝塞尔曲线来拟合多边形线，我认为对于唯一的解决方案来说，自由度太多（但是，再次，我没有时间或者技能来证明这一点......）
A (cubic) bezier curve is a way to define a cubic parametric spline of the general form P=A*t^3+B*t^2+C*t+D where P,A,B,C and D are (two-dimensional, i.e. vectorial) weights. Using Bernstein polynoms, you can calculate the weights A,B,C and D given four control points P0, P1, P2 and P3 as known from practically all vector drawing programs.
Since you only have four control points but want to fit an arbitrary number of arbitrary points, I suspect that there's no unique solution. For instance, given inputs (0,0),(1,0),(1,1) and (0,1), for every "optimal" solution (whatever it be), you could construct an aequivalent solution by mirroring the spline along the main diagonal.
There is a general approach for this kind of problems which is to construct an equation for the sum of squares of the distances for all points to a generic bezier curve (i.e. a curve defined by variables A,B,C and D), calculate tha first devirative and set it to zero and solve the resulting system for A,B,C and D. This usually leads to a linear system of equations (sorry, it would take me some time to do the maths, and it's been a long time since I did this ...). But, as I said, I think that for your problem, this wouldn't result in a unique solution.
If you define an order on the input points, i.e. you want to fit a polygon line using a single bezier curve, I think that there are too many degrees of freedom for a unique solution (but, again, I don't have the time or maybe the skills to prove that ...)
如果你想创建带有尖点的曲线，你的问题就非常困难。我可以想到一种启发式方法来创建一组初始控制点。对于第一个控制点，当按照到第一个锚点的距离排序时，尝试采用可用点的前 1/3。排序是必要的，否则你可能会跳来跳去。取 1/3 的点并进行线性最小二乘拟合，其时间复杂度为线性。这为您提供了曲线起飞所需的方向。对最后 1/3 做同样的事情，你就得到了“着陆”方向。
使用这些线性解决方案创建指向远离锚点的向量，然后尝试使这些向量更长或更短，尝试最小化误差。控制点将沿着来自锚点的那些向量。
这里有一些其他想法（我只能发布两个链接！）：
物理论坛问题
贝塞尔曲线拟合论文
Your problem is very hard if you want to create curves with cusps. I can think of a heuristic to create an initial set of control points. For the first control point, try taking the first 1/3 of the points you have available, when sorted from the distance to the first anchor point. The sorting is necessary, otherwise, you may be jumping all over. Take that 1/3 of your points and do a linear least squares fit, which is has linear time complexity. That gives you the direction your curve needs to take off. Do the same thing with the last 1/3, and you have the "landing" direction.
Use those linear solutions to create vectors pointing away from the anchor points, then try making those vectors longer and shorter, trying to minimize the error. The control points would be along those vectors from the anchor points.
Here are some other ideas (I can only post two links!):
physics forum question
bezier curve fitting thesis
从你的问题来看，我假设你只是希望优化三次贝塞尔曲线的 2 个“内部”控制点的曲线拟合。这不是一个容易解决的问题，因为贝塞尔曲线是参数化描述的。最明显的解决方案是使用最小二乘正交距离回归，但这很困难，因为您需要为您希望拟合的每个点在贝塞尔曲线上生成脚点参数。如果这个问题需要特定的解析解，并且您受过一些数学教育，我建议您阅读 Peigl 和 Tiller 撰写的“The NURBS Book”，并熟悉近似理论和优化技术。如果没有，我会采用更具启发式的方法，因为此类问题不太可能通过此处的简单答案来解决。
Judging by your question, I am assuming that you just wish to optimise the curve fit over the 2 'inner' control points of the cubic bezier. This is not an easy problem to solve as the bezier curve is described parametrically. The most obvious solution would be to use least-squares orthogonal distance regression but this is difficult as you will need to generate footpoint parameters onto the Bezier curve for each point you wish to fit. If this problem requires a specific anayltic solution and you have some mathematical education I would recommend reading "The NURBS Book" by Peigl and Tiller and becoming familiar with approximation theory and optimisation techniques. If not, I would go for a more heuristic type of approach as this type of problem is unlikely to be solved with a simple answer here.
Khan 函数使用 t[i] 的两个版本，其中 t[i] 表示近似曲线上与输入点 p[i] 最接近的点的猜测。第一个简单地使用统一的 t[i] = i/(N-1)，第二个使用弦长。虽然我找不到 Khan 函数，但我认为这只是计算 p[i] 到 p[i+1] 的线性距离，将 t[0] 设置为 0，t[1] 设置为 p[0] 到 p 的距离[1]、t[2] 到 t[1] + p[1] 到 p[2] 的距离，依此类推。除以最后一个值，将所有内容置于 0-1 范围内。
Khan's function uses two versions of t[i], where t[i] represents the guess for closest point on the approximation curve to input point p[i]. The first simply uses uniform t[i] = i/(N-1), the second uses chord length. Whilst I couldn't find Khan's function, I think this simply calculates the linear distance p[i] to p[i+1], set t[0] to 0, t[1] to the distance p[0] to p[1], t[2] to t[1] + distance p[1] to p[2], and so on. The divide by the last value to put everything in the range 0-1.