15

给定 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)，如何得到靠近原点的剩余两个控制点？

4

5 回答 5

11

你可能想看看这个页面

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

它在 C++ 中，但真的很容易移植到任何语言......通过控制点计算函数传递你的每个“边缘”，然后通过贝塞尔计算一个，你就拥有了。要在多边形上执行贝塞尔平滑，请使用最后一个点和第一个点传递最后一条边。

贝塞尔平滑

于 2013-03-03T15:46:51.463 回答
4

（三次）贝塞尔曲线是一种定义一般形式 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 定义的曲线）的距离平方和构造一个方程，计算 tha第一个导数并将其设置为零并求解 A、B、C 和 D 的结果系统。这通常会导致方程组的线性系统（抱歉，我需要一些时间来做数学，而且已经很长时间了因为我这样做了......）。但是，正如我所说，我认为对于您的问题，这不会产生独特的解决方案。

如果您在输入点上定义顺序，即您想使用单个贝塞尔曲线拟合多边形线，我认为唯一解决方案的自由度太多（但是，再次，我没有时间或者也许是证明这一点的技能......）

于 2011-10-12T14:57:39.793 回答
2

如果你想用尖点创建曲线，你的问题就很难了。我可以想到一种启发式方法来创建一组初始控制点。对于第一个控制点，当从到第一个锚点的距离排序时，尝试获取可用点的前 1/3。排序是必要的，否则，你可能会跳过。取 1/3 的点并进行线性最小二乘拟合，它具有线性时间复杂度。这为您提供了曲线需要起飞的方向。对最后 1/3 做同样的事情，你就有了“着陆”的方向。

使用这些线性解决方案创建指向远离锚点的向量，然后尝试使这些向量更长和更短，尽量减少误差。控制点将沿着锚点的那些向量。

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

于 2011-10-13T20:40:14.820 回答
1

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

于 2012-05-30T20:07:07.803 回答
1

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

于 2014-03-24T16:27:16.633 回答