5

我有一系列(x0,y0)... (xn,yn)单调点，x并希望使用贝塞尔曲线通过这些点绘制“最佳”曲线。这条曲线不应该太“锯齿”（例如类似于连接点），也不能太弯曲（绝对不能“倒退”）。我已经创建了一个原型，但想知道是否有客观的“最佳解决方案”。

我需要找到所有段的控制点xi,y1 x(i+1)y(i+1)。我目前对细分的方法（端点除外）x(i), x(i+1)是：

  • 找到向量x(i-1)...x(i+1)，对其进行归一化和缩放factor * len(i,i+1)以给出前导控制点的向量
  • 找到向量x(i+2)...x(i)，对其进行归一化和缩放factor * len(i,i+1)以给出尾随控制点的向量。

我尝试过 factor=0.1（太锯齿）、0.33（太弯曲）和 0.20 - 差不多。但是有没有更好的方法（比如说）使二阶和三阶导数尽可能平滑。（我假设这样的算法是在图形包中实现的）？

如果需要，我可以发布伪/代码。这是三个图像（0.1/0.2/0.33）。控制点用直线表示：黑色（尾随）和红色（前导）

使用因子=0.1

使用因子=0.2

使用因子=0.33

这是当前代码。它的目的是在没有-ing的情况下Y针对X(monotonic X) 进行绘图。close我已经建立了自己的用于创建 SVG 的库（首选输出）；此代码为每个曲线段（control1、xcontrol2、end）创建三倍的x,yin 。coordArray开始由最后一次操作（移动或曲线）假设。它是 Java，但应该易于解释（CurvePrimitive映射到三次，"d"是 SVG 中完整路径的字符串表示形式）。

        List<SVGPathPrimitive> primitiveList = new ArrayList<SVGPathPrimitive>();
    primitiveList.add(new MovePrimitive(real2Array.get(0)));
    for(int i = 0; i < real2Array.size()-1; i++) {
        // create path 12
        Real2 p0 = (i == 0) ? null : real2Array.get(i-1);
        Real2 p1 = real2Array.get(i);
        Real2 p2 = real2Array.get(i+1);
        Real2 p3 = (i == real2Array.size()-2) ? null : real2Array.get(i+2);
        Real2Array coordArray = plotSegment(factor, p0, p1, p2, p3);
        SVGPathPrimitive primitive = new CurvePrimitive(coordArray);
        primitiveList.add(primitive);
    }
    String d = SVGPath.constructDString(primitiveList);
    SVGPath path1 = new SVGPath(d);
    svg.appendChild(path1);


/**
 * 
 * @param factor to scale control points by
 * @param p0 previous point (null at start)
 * @param p1 start of segment
 * @param p2 end of segment
 * @param p3 following point (null at end)
 * @return
 */
private Real2Array plotSegment(double factor, Real2 p0, Real2 p1, Real2 p2, Real2 p3) {
    // create p1-p2 curve
    double len12 = p1.getDistance(p2) * factor;
    Vector2 vStart = (p0 == null) ? new Vector2(p2.subtract(p1)) : new Vector2(p2.subtract(p0));
    vStart = new Vector2(vStart.getUnitVector().multiplyBy(len12));
    Vector2 vEnd = (p3 == null) ?  new Vector2(p2.subtract(p1)) : new Vector2(p3.subtract(p1));
    vEnd = new Vector2(vEnd.getUnitVector().multiplyBy(len12));
    Real2Array coordArray = new Real2Array();
    Real2 controlStart = p1.plus(vStart);
    coordArray.add(controlStart);
    Real2 controlEnd = p2.subtract(vEnd);
    coordArray.add(controlEnd);
    coordArray.add(p2);
    // plot controls
    SVGLine line12 = new SVGLine(p1, controlStart); 
    line12.setStroke("red");
    svg.appendChild(line12);
    SVGLine line21 = new SVGLine(p2, controlEnd); 
    svg.appendChild(line21);
    return coordArray;
}
4

2 回答 2

3

贝塞尔曲线需要数据点，以及每个点的斜率和曲率。在图形程序中，斜率由控制线的斜率设置，曲率由长度可视化。

当您没有用户输入这样的控制线时，您需要估计每个点的梯度和曲率。维基百科页面http://en.wikipedia.org/wiki/Cubic_Hermite_spline，特别是“插入数据集”部分有一个直接采用这些值的公式。

通常，从点估计这些值是使用有限差分完成的 - 因此您可以使用任一侧的点的值来帮助估计。这里唯一的选择是如何处理只有一个相邻点的端点：您可以将曲率设置为零，或者如果曲线是周期性的，您可以“环绕”并使用最后一个点的值。

我引用的维基百科页面也有其他方案，但大多数其他人介绍了一些其他“免费参数”，您需要找到一种设置方式，因此在没有更多信息来帮助您决定如何设置其他参数的情况下，我' d 选择简单的方案，看看你是否喜欢结果。

如果维基百科的文章不够清楚，请告诉我，我会敲一些代码。

需要注意的另一点：您追求的是什么“类型”的贝塞尔插值？大多数图形程序在二维上进行三次贝塞尔曲线（即您可以绘制圆形曲线），但您的示例图像看起来可能是一维函数近似值（因为每个 x 只有一个 y 值）。我引用的页面上并没有真正提到图形程序类型曲线。将斜率和曲率的估计转换为http://en.wikipedia.org/wiki/B%C3%A9zier_curve (Cubic Bezier) 上所示形式的控制向量所涉及的数学需要一些工作，但想法是相似的。

下面是一个可能方案的图片和算法，假设您唯一的输入是三个点 P1、P2、P3

贝塞尔插值方案

构造一条线 (C1,P1,C2)，使得 (P3,P1,C1) 和 (P2,P1,C2) 的角度相等。以类似的方式构建其他深灰色线条。这些深灰色线的交点（标记为 C1、C2 和 C3）成为控制点，与 Bezier Curve 维基百科网站上的图像具有相同的意义。所以每条红色曲线，例如 (P3,P1)，都是由点 (P3, C1, P1) 定义的二次贝塞尔曲线。红色曲线的构造与维基百科网站上给出的相同。

但是，我注意到 Bezier Curve 维基百科页面上的控制向量似乎与您使用的控制向量类型不匹配，因此您可能必须弄清楚如何将这两种方法等同起来。

于 2013-01-18T11:54:39.667 回答
1

我尝试使用二次样条而不是三次样条来简化控制点的选择（您只需选择每个点的梯度作为相邻间隔的平均梯度的加权平均值，然后在数据处绘制曲线的切线点并粘贴这些切线相交的控制点），但我找不到设置端点梯度的合理策略。所以我选择了拉格朗日拟合：

function lagrange(points) { //points is  [ [x1,y1], [x2,y2], ... ]
//  See: http://www.codecogs.com/library/maths/approximation/interpolation/lagrange.php
  var j,n = points.length;
  var p = [];
  for (j=0;j<n;j++) {
    p[j] = function (x,j) { //have to pass j cos JS is lame at currying
      var k, res = 1;
      for (k=0;k<n;k++)
        res*=( k==j ? points[j][1] : ((x-points[k][0])/(points[j][0]-points[k][0])) );
      return res; 
    }
  }
  return function(x) {
    var i, res = 0;
    for (i=0;i<n;i++)
      res += p[i](x,i);
    return res;
  }
}

有了这个，我只需制作大量样本并用直线将它们连接起来。

如果您的数据（如我的数据）包含真实世界的测量值，这仍然是错误的。这些会受到随机误差的影响，如果您使用强制曲线精确地击中它们的技术，那么您可能会在点之间获得愚蠢的山谷和山丘。在这种情况下，您应该问自己数据应该适合什么多项式的顺序，并且……嗯……这就是我要弄清楚的。

于 2014-01-17T16:11:32.033 回答