如何获得最接近给定点的三次贝塞尔曲线？

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),如何让两个控制点靠近原点？

Answer 1

您可能需要查看此页面:http://www.antigrain.com/research/bezier_interpolation/index.html

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

它是用C++编写的,但很容易移植到任何语言......通过控制点计算功能传递每个"边缘",然后通过bezier计算,然后你就可以了.要在多边形上执行bezier平滑,请使用最后一个和第一个点传递最后一个边.

Answer 2

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

使用这些线性解决方案创建指向远离锚点的向量，然后尝试使这些向量更长或更短，尝试最小化误差。控制点将沿着来自锚点的那些向量。

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