贝塞尔样条和三次样条的插值

• 下载插值 - 30.36 KB

引言

用 GDI+ 画一个贝塞尔样条曲线很容易（调用 Graphics.DrawCurve(Points)），但是如何获取画出的曲线上任意一点？

我在谈论什么

请看截图所示的内容
一条由 7 个支持点构造的 贝塞尔样条曲线（棕色），将贝塞尔样条曲线细分为 6 个贝塞尔段。
19 个构造点，它们对曲线进行建模（橙色）。
“曲线指针”（红色）。它可以在贝塞尔样条曲线上移动，其位置通过插值贝塞尔样条曲线计算并显示。

贝塞尔样条曲线的构造方法

两个支持点之间的每个段都构造为贝塞尔曲线，有 4 个构造点
这两个支持点本身和另外两个点，它们负责确保贝塞尔到达支持点的斜率与离开支持点的贝塞尔的斜率相同。

现在对其进行插值

为了获得 X 位置的 Y 值，我分两步插值贝塞尔样条曲线
首先，我搜索包含 X 位置的贝塞尔段。这可以通过二分查找快速完成

Dim Indx = _Points.BinarySearch(New PointF(X, 0), Function(P1, P2) P1.X.CompareTo(P2.X))

(该搜索的比较仅比较 Point.X-Values。)
Indx 将是第一个 point.X > X 的点的索引的按位补码。

我将此数据传递给第二步，以 InterpolateSegment()

Protected Overrides Function InterpolateSegment( _
      ByVal X As Single, ByVal Indx As Integer) As PointF
   'Since for Beziers there's no Y = f(X) function available, I approximate X
   'by binary try and error.
   'note: Indx references the support-point *after* X
   Indx = Indx * 3 'now Indx references the last *construction-point* of the 
   '                   BezierSegment in Me.DrawPath, which is to interpolate
   Dim Pts = Me.DrawPath.PathPoints
   Dim BezierSegment = New PointF() { _
      Pts(Indx - 3), Pts(Indx - 2), Pts(Indx - 1), Pts(Indx)}
   'binary approximation
   Dim Range = New Single() {0, 0, 1}  'elsewhere known as: Bottom, Mid, Top
   Dim Dlt = -2.0F
   Dim Pt As PointF
   Do
      Range(If(Dlt < 0, 0, 2)) = Range(1)          'set Bottom or Top to Mid
      Range(1) = (Range(0) + Range(2)) / 2                    'recompute Mid
      Pt = PointOfFraction(Range(1), BezierSegment)                     'try
      Dlt = Pt.X - X        'for drawing an "error" smaller 0.5 is tolerable
   Loop Until Math.Abs(Dlt) < 0.5
   Return Pt
End Function

哎呀！我没有提到 DrawPath 吗？ 这是一个 GraphicsPath，它存储了贝塞尔样条曲线的所有构造点，我想将其绘制出来。非常有用的！构造点存储在“.PathPoints”属性中。

现在我们来讨论 Casteljau 算法，它计算贝塞尔曲线上的一个点。
我很幸运：注释已经足够了，所以我可以不用再多说了。

Private Shared Function PointOfFraction( _
         ByVal Fraction As Single, ByVal ptBeziers() As PointF) As PointF
   'Calculating a point on a BezierCurve bases on a given *Fraction* of the curve (half, 
   'third, else). For each two construction-points the proportionate between-point is 
   'computed, and is taken as new construction-point.
   'So in each loop there will be found one point less, until there's only one left
   'Strongly recommended: search "Casteljau" on Wikipedia. Surve to "Bezier-curve" and to
   '"Casteljau-algorithm" (which is implemented here)
   Dim Pts(ptBeziers.Length - 2) As PointF
   For I = 0 To ptBeziers.Length - 2   'first loop copies the points to a temporary array
      Pts(I) = PointBetween(ptBeziers(I), ptBeziers(I + 1), Fraction)
   Next
   For UBord = Pts.Length - 2 To 0 Step -1           'following loops overwrite the array
      For I = 0 To UBord
         Pts(I) = PointBetween(Pts(I), Pts(I + 1), Fraction)
      Next
   Next
   Return Pts(0)
End Function
    
Private Shared Function PointBetween( _
         ByVal Pt1 As PointF, ByVal Pt2 As PointF, ByVal Fraction As Single) As PointF
   'compute the to Fraction proportionate between-point between Pt1 and Pt2 
   Return Pt1.Add(Pt2.Subtract(Pt1).Mult(Fraction))      'Pt1 + (Pt2 - Pt1) * Fraction
End Function 

降维

将贝塞尔样条段插值为 Y = f(X) 函数在数学上是不正确的。
尽管我将支持点按“从左到右”排序，但一段可以采用在某些 X 位置显示多个 Y 值。的形式
我的“插值”会忽略此类，并仅返回找到的第一个 Y 值。
这种失败可以通过曲线的某些部分看出来，这些部分无法通过插值到达。

在数学上正确的是插值三次样条曲线。
仅当两个支持点设置在同一 X 位置（作为垂直线）时，它们在数学上才未定义。

多边形，三次样条曲线

虽然插值多边形是微不足道的，但对三次样条曲线来说却是 - 啊 - 并非微不足道的。没有 GDI+ 函数可以为您绘制它，因此您需要处理线性代数来求解线性方程组 - 额！- 我在没有真正理解的情况下完成了这项工作。为此

致谢

• Marco Roello 的三次样条曲线练习基于他的 文章

实现细节

该项目处理几个 ownerdraw 需求
可移动和高亮显示的点，多边形，贝塞尔样条曲线，三次样条曲线和一个标题

我将它们收集到一个小的类层次结构中

               ControlCaption
              / 
DrawObjectBase --DrawPoint
              \
               \         BezierSpline
                \       /
                 Polygon
                        \
                         CubicSpline

您可以看到：从程序上讲，我将样条曲线视为一个多边形，具有绘制和插值两个支持点之间线的不同方式。如果只有两个支持点，它们实际上会显示同一条直线。

历史

• 2007 年 12 月 30 日：提交文章，VB2008 prof 中的示例解决方案，Beta
• 2008 年 5 月 1 日：VB2005 版本添加到 zip 文件中