HotPoints - 2D 折线顶点平滑的新方法

• 下载源代码 - 221.6 KB

引言

在本文中，我将介绍一种用于 2D 多段线顶点平滑的新方法，我将其命名为 HotPoints。 显然，有许多成熟的方法可以通过插值或逼近来获得平滑曲线，例如 NURBS、样条曲线、Cattmull-Rom、Chaikin 或 Bezier 曲线，或者一些滤波技术。 这种方法是一种逼近，在输出结果方面，它与 Chaikin 非常相似，但基于完全不同的逻辑。

在继续之前，我建议您查看这篇 CodeProject 文章，“2D 多段线顶点平滑”，作者为 veen_rp(*)。

方法

解释底层逻辑的最佳方法是使用逐步说明图。 我们开始吧。

如果我们以迭代循环重复这些步骤，至少 3 次，我们将获得一条漂亮的平滑曲线。 绝对的！该算法的质量非常令人满意。

正如您注意到的，主要问题或有趣的点是找到绿色点的坐标。 我们如何计算它们？

现在，让我们暂时回到大学时代，回顾一些几何主题，例如直线、圆、椭圆等。 请参见下图

实际上，Q 点可以在对角线上移动，但当 F 点和 Q 点垂直时，可以获得最佳结果。

因此，在进行了一些数学运算和消除后，我们最终可以使用以下公式计算 Q 点的笛卡尔坐标

      F := 1.0; // F: 0.0 .. 2.0

      dx := p2.X - p1.X;
      dy := p2.Y - p1.Y;

      // a: major axis, b: minor axis
      a := dx / 2.82843; // 2*2^0.5 = 2.82843
      b := dy / 2.82843;

      // O: mid/center point
      Ox := (P1.X + P2.X) / 2.0;
      Oy := (P1.Y + P2.Y) / 2.0;

      Q1.X := Ox - F * a / 1.41421; // sqrt(2) = 1.41421
      Q1.y := Oy - F * b / 1.41421;

      Q2.X := Ox + F * a / 1.41421;
      Q2.y := Oy + F * b / 1.41421;

Using the Code

让我们开始编写代码吧！

  ////////////////////////////////////////////
  // HotPoints approximation
  ////////////////////////////////////////////

  // Calculating hotpoints

  for i:=0 to nItera-1 do
  begin
    k := 0;
    for j:=0 to nPoints-1 do
    begin
      j0 := (j+0 + nPoints) mod nPoints; // circular form
      j1 := (j+1 + nPoints) mod nPoints;

      p1.X := trunc(pinn[j0].X + 0.5);
      p1.Y := trunc(pinn[j0].Y + 0.5);

      p2.X := trunc(pinn[j1].X + 0.5);
      p2.Y := trunc(pinn[j1].Y + 0.5);

      dx := p2.X - p1.X;
      dy := p2.Y - p1.Y;

      radiX := dx / 2.82843; // 2 * 2^0.5 = 2.82843
      radiY := dy / 2.82843; //

      Ox := (P1.X + P2.X) / 2.0;
      Oy := (P1.Y + P2.Y) / 2.0;

      Q1.X := Ox - F * radiX / 1.41421; // sqrt(2) = 1.41421
      Q1.y := Oy - F * radiY / 1.41421;
      pout[k] := Q1; k := k + 1;

      Q2.X := Ox + F * radiX / 1.41421;
      Q2.y := Oy + F * radiY / 1.41421;
      pout[k] := Q2; k := k + 1;
    end; // j

    nPoints := k;
    for k:=0 to nPoints-1 do pinn[k] := pout[k]; // !!!
  end; // iteration, i

  // Plotting the curve

  for k:=0 to nPoints-1 do
  begin
    X := trunc(pout[k].X + 0.5);
    Y := trunc(pout[k].Y + 0.5);
    if (k = 0) then
      imgDraw.Canvas.MoveTo(X, Y)
    else
      imgDraw.Canvas.LineTo(X, Y);
  end;

这是描述步骤的中间运行状态

比较

为了进行比较，请参阅 Chaikin 和 HotPoints 的结果。 它们看起来几乎相同。

追记：原始测试点借自上述(*)文章。

结论和关注点

在这个版本中，每次迭代，点的数量都会翻倍。 因此，请小心迭代次数超过 7/8 次。

另一方面，也许可以优化算法的实现，以避免浮点数，例如，实现整数版本。

参考文献

1. 细分曲线和曲面
2. “2D 多段线顶点平滑”

历史

• 2021 年 4 月 30 日：初始版本
• 2021 年 5 月 3 日：更新 - 版本 2