用多段三次贝塞尔曲线和距离以及曲率约束逼近数据

2 回答

• 5

  我找到了满足我的criterea的解决方案 . 解决方案是首先找到近似于最小二乘意义的点的B样条，然后将该样条转换为多段贝塞尔曲线 . B样条确实具有以下优点：与贝塞尔曲线相比，它们不会通过控制点提供一种指定近似曲线的所需"smoothness"的方法 . 生成这样的样条线所需的功能在FITPACK库中实现，scipy为其提供了python绑定 . 让我假设我将我的数据读入列表 x 和 y ，然后我可以这样做：

  import matplotlib.pyplot as plt
  import numpy as np
  from scipy import interpolate
  tck,u = interpolate.splprep([x,y],s=3)
  unew = np.arange(0,1.01,0.01)
  out = interpolate.splev(unew,tck)
  plt.figure()
  plt.plot(x,y,out[0],out[1])
  plt.show()
  

  结果如下所示：

  

  如果我希望曲线更平滑，那么我可以将 s 参数增加到 splprep . 如果我希望近似值更接近数据，我可以减少 s 参数，以减少平滑度 . 通过以编程方式查看多个 s 参数，我可以找到符合给定要求的良好参数 .

  但问题是如何将该结果转换为贝塞尔曲线 . Zachary Pincus的答案在this email . 我将在这里复制他的解决方案，以完整回答我的问题：

  def b_spline_to_bezier_series(tck, per = False):
    """Convert a parametric b-spline into a sequence of Bezier curves of the same degree.
  
    Inputs:
      tck : (t,c,k) tuple of b-spline knots, coefficients, and degree returned by splprep.
      per : if tck was created as a periodic spline, per *must* be true, else per *must* be false.
  
    Output:
      A list of Bezier curves of degree k that is equivalent to the input spline. 
      Each Bezier curve is an array of shape (k+1,d) where d is the dimension of the
      space; thus the curve includes the starting point, the k-1 internal control 
      points, and the endpoint, where each point is of d dimensions.
    """
    from fitpack import insert
    from numpy import asarray, unique, split, sum
    t,c,k = tck
    t = asarray(t)
    try:
      c[0][0]
    except:
      # I can't figure out a simple way to convert nonparametric splines to 
      # parametric splines. Oh well.
      raise TypeError("Only parametric b-splines are supported.")
    new_tck = tck
    if per:
      # ignore the leading and trailing k knots that exist to enforce periodicity 
      knots_to_consider = unique(t[k:-k])
    else:
      # the first and last k+1 knots are identical in the non-periodic case, so
      # no need to consider them when increasing the knot multiplicities below
      knots_to_consider = unique(t[k+1:-k-1])
    # For each unique knot, bring it's multiplicity up to the next multiple of k+1
    # This removes all continuity constraints between each of the original knots, 
    # creating a set of independent Bezier curves.
    desired_multiplicity = k+1
    for x in knots_to_consider:
      current_multiplicity = sum(t == x)
      remainder = current_multiplicity%desired_multiplicity
      if remainder != 0:
        # add enough knots to bring the current multiplicity up to the desired multiplicity
        number_to_insert = desired_multiplicity - remainder
        new_tck = insert(x, new_tck, number_to_insert, per)
    tt,cc,kk = new_tck
    # strip off the last k+1 knots, as they are redundant after knot insertion
    bezier_points = numpy.transpose(cc)[:-desired_multiplicity]
    if per:
      # again, ignore the leading and trailing k knots
      bezier_points = bezier_points[k:-k]
    # group the points into the desired bezier curves
    return split(bezier_points, len(bezier_points) / desired_multiplicity, axis = 0)
  

  所以B-Splines，FITPACK，numpy和scipy救了我的一天:)

  回复于 2024-05-05T11:31:39+08:00
• 7

  • polygonize data

  找到点的顺序，这样你就可以找到彼此最近的点，并尝试连接“按线” . 避免回到原点

  • compute derivation along path

  它是“线”的方向变化，你达到局部最小值或最大值就有你的控制点......这样做是为了减少输入数据（只留下控制点） .

  • curve

  现在使用这些点作为控制点 . 我强烈建议单独使用 x 和 y 的插值多项式，例如：

  x=a0+a1*t+a2*t*t+a3*t*t*t
  y=b0+b1*t+b2*t*t+b3*t*t*t
  

  其中 a0..a3 的计算方式如下：

  d1=0.5*(p2.x-p0.x);
  d2=0.5*(p3.x-p1.x);
  a0=p1.x;
  a1=d1;
  a2=(3.0*(p2.x-p1.x))-(2.0*d1)-d2;
  a3=d1+d2+(2.0*(-p2.x+p1.x));
  

  • b0 .. b3 以相同的方式计算，但当然使用y坐标

  • p0..p3 是三次插值曲线的控制点

  • t =<0.0,1.0> 是从 p1 到 p2 的曲线参数

  这确保了位置和第一次推导是连续的（c1），你也可以使用BEZIER，但它不会像这样好 .

  [edit1] too sharp edges is a BIG problem

  要解决此问题，您可以在获取控制点之前从数据集中删除点 . 我现在可以想到两种方法：选择对你更好的方法

  • remove points from dataset with too high first derivation

  dx/dl 或 dy/dl 其中 x,y 是坐标， l 是曲线长度（沿其路径） . 从曲线推导精确计算曲率半径是棘手的

  • remove points from dataset that leads to too small curvature radius

  计算相邻线段（黑线）中点的交点 . 像图像上的垂直轴（红线）它的距离和连接点（蓝线）是曲率半径 . 当曲率半径小时，你的极限移除那个点......

  

  现在，如果你真的只需要BEZIER立方体，那么你可以将我的插值立方体转换为BEZIER立方体，如下所示：

  //  ---------------------------------------------------------------------------
  //  x=cx[0]+(t*cx[1])+(tt*cx[2])+(ttt*cx[3]); // cubic x=f(t), t = <0,1>
  //  ---------------------------------------------------------------------------
  //  cubic matrix                           bz4 = it4
  //  ---------------------------------------------------------------------------
  //  cx[0]=                            (    x0) =                    (    X1)
  //  cx[1]=                   (3.0*x1)-(3.0*x0) =           (0.5*X2)         -(0.5*X0)
  //  cx[2]=          (3.0*x2)-(6.0*x1)+(3.0*x0) = -(0.5*X3)+(2.0*X2)-(2.5*X1)+(    X0)
  //  cx[3]= (    x3)-(3.0*x2)+(3.0*x1)-(    x0) =  (0.5*X3)-(1.5*X2)+(1.5*X1)-(0.5*X0)
  //  ---------------------------------------------------------------------------
      const double m=1.0/6.0;
      double x0,y0,x1,y1,x2,y2,x3,y3;
      x0 = X1;           y0 = Y1;
      x1 = X1-(X0-X2)*m; y1 = Y1-(Y0-Y2)*m;
      x2 = X2+(X1-X3)*m; y2 = Y2+(Y1-Y3)*m;
      x3 = X2;           y3 = Y2;
  

  如果您需要反向转换，请参阅：

  • Bezier curve with control points within the curve

  回复于 2024-05-05T11:31:39+08:00