如何使用贝塞尔曲线通过一组点绘制平滑的线？

Question

我需要通过一组顶点绘制平滑的线。这组顶点由用户在触摸屏上拖动手指生成，这组顶点通常相当大，并且顶点之间的距离相当小。但是，如果我简单地用直线连接每个顶点，则结果非常粗糙（不平滑）。

我发现解决此问题的方法是使用样条插值（和/或其他我不理解的东西）通过添加大量额外的顶点来平滑该线。这些方法效果很好，但由于顶点列表已经相当大，将其增加10倍左右会有显着的性能影响。

似乎可以使用贝塞尔曲线实现平滑处理而无需添加其他顶点。

下面是基于这里的解决方案的一些代码：

http://www.antigrain.com/research/bezier_interpolation/

当顶点之间的距离很大时，它的效果很好，但当顶点彼此靠近时，它的效果不是很好。

有没有更好的方法可以在大量顶点之间绘制平滑曲线，而不需要添加额外的顶点？

        Vector<PointF> gesture;
        protected void onDraw(Canvas canvas)
        {
            if(gesture.size() > 4 )
            {
                Path gesturePath = new Path();

                gesturePath.moveTo(gesture.get(0).x, gesture.get(0).y);
                gesturePath.lineTo(gesture.get(1).x, gesture.get(1).y);

                for (int i = 2; i < gesture.size() - 1; i++)
                {
                    float[] ctrl = getControlPoint(gesture.get(i), gesture.get(i - 1), gesture.get(i), gesture.get(i + 1));
                    gesturePath.cubicTo(ctrl[0], ctrl[1], ctrl[2], ctrl[3], gesture.get(i).x, gesture.get(i).y);
                }

                gesturePath.lineTo(gesture.get(gesture.size() - 1).x, gesture.get(gesture.size() - 1).y);
                canvas.drawPath(gesturePath, mPaint);
            }
        }
}


    private float[] getControlPoint(PointF p0, PointF p1, PointF p2, PointF p3)
    {
        float x0 = p0.x;
        float x1 = p1.x;
        float x2 = p2.x;
        float x3 = p3.x;
        float y0 = p0.y;
        float y1 = p1.y;
        float y2 = p2.y;
        float y3 = p3.y;

           double xc1 = (x0 + x1) / 2.0;
            double yc1 = (y0 + y1) / 2.0;
            double xc2 = (x1 + x2) / 2.0;
            double yc2 = (y1 + y2) / 2.0;
            double xc3 = (x2 + x3) / 2.0;
            double yc3 = (y2 + y3) / 2.0;

            double len1 = Math.sqrt((x1-x0) * (x1-x0) + (y1-y0) * (y1-y0));
            double len2 = Math.sqrt((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1));
            double len3 = Math.sqrt((x3-x2) * (x3-x2) + (y3-y2) * (y3-y2));

            double k1 = len1 / (len1 + len2);
            double k2 = len2 / (len2 + len3);

            double xm1 = xc1 + (xc2 - xc1) * k1;
            double ym1 = yc1 + (yc2 - yc1) * k1;

            double xm2 = xc2 + (xc3 - xc2) * k2;
            double ym2 = yc2 + (yc3 - yc2) * k2;

            // Resulting control points. Here smooth_value is mentioned
            // above coefficient K whose value should be in range [0...1].
            double k = .1;

            float ctrl1_x = (float) (xm1 + (xc2 - xm1) * k + x1 - xm1);
            float ctrl1_y = (float) (ym1 + (yc2 - ym1) * k + y1 - ym1);

            float ctrl2_x = (float) (xm2 + (xc2 - xm2) * k + x2 - xm2);
            float ctrl2_y = (float) (ym2 + (yc2 - ym2) * k + y2 - ym2);

            return new float[]{ctrl1_x, ctrl1_y, ctrl2_x, ctrl2_y};
    }

- ab11

---

定义“不太好用”。 - Oliver Charlesworth

看起来非常类似于只需连接每个顶点的渲染。相反，使用B样条插值插入一堆顶点效果很好。 - ab11

Answer 1

贝塞尔曲线不是为了通过提供的点而设计的！它们旨在形成受控制点影响的平滑曲线。此外，您不希望您的平滑曲线穿过所有数据点！

与其进行插值，您应该考虑过滤您的数据集：

对于这种情况，您需要一个数据序列，即按手指绘制手势的点数组的顺序：

您应该在维基百科上查找“滑动平均值”。您应该使用一个小的平均窗口（尝试5-10个点）。操作如下：（请查看维基百科以获取更详细的说明）

我在此处使用了10个点的平均窗口：首先计算点0-9的平均值，并将结果输出为结果点0，然后计算点1-10的平均值并输出结果1，以此类推。

要计算N个点之间的平均值：
avgX =（x0 + x1 .... xn）/ N
avgY =（y0 + y1 .... yn）/ N

最后，您可以用直线连接结果点。

如果您仍然需要在缺失点之间进行插值，则应使用分段立方样条。
一个三次样条经过所有3个提供的点。
您需要计算一系列样条。

但是首先尝试滑动平均值。这非常简单。

- AlexWien

Answer 2

这是用于什么？你为什么需要如此精确？我会认为你只需要在用户拖动手指每英寸存储大约4个顶点。考虑到这一点： 尝试使用每X个顶点中的一个来实际绘制之间的点，其中中间顶点用于指定曲线的加权点。

int interval = 10; //how many points to skip
gesture.moveTo(gesture.get(0).x, gesture.get(0).y);
for(int i =0; i +interval/2 < gesture.size(); i+=interval)
{
   Gesture ngp = gesture.get(i+interval/2);
   gesturePath.quadTo(ngp.x,ngp.y, gp.x,gp.y);
}

你需要调整这个代码才能让它真正运行，但是思路已经在那里了。

- you786

---

我尝试了两种不同的方法来减少顶点数量（跳过一定间隔和如果它们与前一个顶点的距离在一定范围内，则不将顶点添加到列表中），但两次使用我的帖子中的平滑算法结果都不好。我认为问题在于每个贝塞尔曲线都与使用的每个顶点相交，而正确的方法不一定会与顶点相交，如此链接所讨论的那样（但是，我对链接中的数学不够熟悉，无法实现这一点）：http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/INT-APP/CURVE-APP-global.html - ab11

Answer 3

很好的问题。你（错误的）结果是明显的，但你可以尝试将其应用于一个更小的数据集，也许通过用一个平均点来代替一组密集的点。在这种情况下，判断两个或多个点是否属于同一组的适当距离可以用时间来表示，而不是空间，因此你需要存储整个触摸事件（x，y和时间戳）。我之所以考虑这个问题，是因为我需要让用户通过触摸来绘制几何图元（矩形、线条和简单曲线）。

- Raffaele

---

我尝试了两种不同的方法来减少顶点数量（跳过一定间隔和如果它们与前一个顶点的距离在一定范围内，则不将顶点添加到列表中），但两次使用我的帖子中的平滑算法结果都不好。我认为问题在于每个贝塞尔曲线都与使用的每个顶点相交，而正确的方法不一定会相交顶点，如此链接所讨论的（但是，我对链接中的数学不够熟悉，无法实现这一点）：http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/INT-APP/CURVE-APP-global.html - ab11

实际上，我建议对每个组中的点进行平均处理，但这种方法无疑更为复杂。 - Raffaele