如何获取与给定点最接近的立方贝塞尔曲线？

Question

给定n个点：

p0, p1, p2, ..., pn;

如何获得点c1、c2，以使由

p0、c1、c2、pn

定义的三次贝塞尔曲线最接近给定的点？

我试过最小二乘法。在阅读http://www.mathworks.com/matlabcentral/fileexchange/15542-cubic-bezier-least-square-fitting的pdf文档之后，我写出了这个方法。但是我找不到一个好的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），如何获得靠近原始点的另外两个控制点？

- EFanZh

---

你是在对给定的点拟合一个一次立方多项式吗？引入“控制点”c1和c2可以唯一确定一个立方多项式，该多项式适合于四个点p0、c1、c2、pn。现在，“最佳方法”需要一个接近度标准。假设你的数据由2D点组成，其中x坐标是独立值，y坐标是（功能上）依赖值，并且点p0,...,pn按（不同的）递增x坐标排列。你的曲线完全适合第一个和最后一个点，因此“最接近的曲线”可能最小化y值的平方误差或其他目标。 - hardmath

您可以使用伯恩斯坦基函数来计算新的控制点，具体方法请参考http://reference.wolfram.com/mathematica/ref/BezierCurve.html中的“Applications-interpolation”部分。 - Dr. belisarius

不要误解我的意思，但我认为你缺乏对此的基本理解。"Bezier" 不是一种曲线类型，就像 "spline" 也不是一种曲线类型（这么说）。它是一种构建曲线的方法，这些曲线“相互配合”并依赖于它们的边界条件。所以 @hardmath 所说的确有道理。 - Rook

控制点的顺序 {（0，256），（512，0），（0，0），（256，256）} 很重要。如果给出相同的点集但不同的顺序，则结果可能会有所不同。 - David

你能否发布更新后的代码，假设你已经改进了它？ - Thomas

Answer 1

我建议您查看此页面。

尽管作者写道：“这种方法是纯启发式和经验性的。从严格的数学建模角度来看，它可能会给出错误的结果。但在实践中，结果足够好，并且需要绝对最少的计算。”，它是一个非常好的实现。

它是用C++编写的，但是很容易移植到任何语言......将每个“边”通过控制点计算函数传递，然后通过贝塞尔计算函数进行计算，您就可以拥有它。

要对多边形执行贝塞尔平滑，请通过最后一条边传递您的最后一个和第一个点。

- Benoît Lahoz

Answer 2

一个（立方）贝塞尔曲线是一种定义一般形式为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。这通常会导致一组线性方程组（抱歉，我需要一些时间来完成这些数学计算，而且我已经很久没有做过了...）。但是，正如我所说的，我认为对于您的问题，这不会得出唯一的解决方案。

如果您为输入点定义一个顺序，即您想使用单个贝塞尔曲线拟合一个多边形线，我认为自由度太多了，无法得到唯一的解决方案（但是，再次说明，我没有时间或可能缺乏证明的技能...）

- MartinStettner

Answer 3

如果您想创建带有尖峰的曲线，那么这个问题非常困难。我可以想出一种启发式方法来创建一个初始的控制点集合。对于第一个控制点，请尝试选择可用点距离第一个锚点排序后前1/3的点。排序是必要的，否则您可能会到处跳跃。取这1/3的点并进行线性最小二乘拟合，它具有线性时间复杂度。这给出了曲线起始点的方向。使用相同的方法处理最后的1/3，即得到“落地”方向。

使用这些线性解决方案创建指向锚点的向量，然后尝试使这些向量变长或变短，以最小化误差。控制点将沿着这些向量从锚点延伸。

以下是其他一些想法（我只能发布两个链接！）： 物理论坛问题 贝塞尔曲线拟合论文

- Frank Hileman

Answer 4

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的范围内。

- Malcolm McLean

Answer 5

根据您的问题，我猜测您只是希望优化三次贝塞尔曲线的2个“内部”控制点上的拟合曲线。这不是一个容易解决的问题，因为贝塞尔曲线是以参数形式描述的。最明显的解决方案是使用最小二乘正交距离回归，但这很困难，因为您需要为每个要拟合的点在贝塞尔曲线上生成足点参数。如果这个问题需要特定的分析解决方案，并且您有一些数学教育，我建议阅读Peigl和Tiller的《NURBS Book》，并熟悉逼近理论和优化技术。如果没有，我会选择更加启发式的方法，因为这种类型的问题不太可能通过简单的答案来解决。

- mathematician1975