当前位置：首页 > article >正文

道格拉斯-普克算法

article 2025/3/18 8:10:19

是什么

是一种用于简化曲线或折线的算法。它通过减少构成曲线的点的数量，同时尽可能保留曲线的形状，从而实现数据的压缩和简化。该算法在计算机图形学、地理信息系统（GIS）和地图绘制等领域中广泛应用。

应用场景

在渲染轨迹时，原始的轨迹点本来就已经很密集了，再经过平滑插值之后，密集程度更是翻倍。

在下图中可见，直线的中间区域，没有什么信息量的地方，却有大量的三角面被不必要地渲染。

因此，我想把这条轨迹的特征提取出来，只保留直线的开头和结尾的特征点，丢掉中间没用的点。

可以使用道格拉斯-普克算法。

源数据有100多个点，处理之后只保留了14个关键特征点。

数据量大大减少，筛选掉了不必要的细节。

核心思想

递归地选择关键点，丢弃对曲线形状影响较小的点。

一、初始化

选择曲线的起点和终点作为初始关键点。
将这两点之间的所有点作为候选点。

二、递归处理

对于两个关键点之间的所有候选点，计算每个候选点到这两个关键点连线的所在直线的距离。
找到距离最远的点，如果其距离大于预设的阈值（ε），则将曲线分成两段，该点作为前一段的第二个关键点和后一段的第一个关键点，并递归地对这两段子曲线重复上述过程。
如果所有点的距离都小于阈值，则丢弃这些点，保留当前的关键点。

三、终止条件

当所有子曲线都处理完毕，且没有新的关键点被添加时，算法结束。

代码

    /// <summary>
    /// 使用道格拉斯-普克算法简化轨迹
    /// </summary>
    /// <param name="points">轨迹点的集合</param>
    /// <param name="epsilon">移除距离线段一定距离的点，单位：像素</param>
    /// <returns></returns>
    public static List<Vector2> Simplify(List<Vector2> points, float epsilon = 20)
    {
        if (points.Count < 3) return points;

        // 找到离首尾连线最远的点
        float maxDistance = 0;
        int index = 0;
        LineSegment segment = new LineSegment(points[0], points[points.Count - 1]);

        for (int i = 1; i < points.Count - 1; i++)
        {
            float distance = segment.DistanceToPoint(points[i]);
            if (distance > maxDistance)
            {
                maxDistance = distance;
                index = i;
            }
        }

        // 递归处理子分段
        if (maxDistance > epsilon)
        {
            List<Vector2> firstPart = Simplify(points.GetRange(0, index + 1), epsilon);
            List<Vector2> secondPart = Simplify(points.GetRange(index, points.Count - index), epsilon);

            return firstPart.Take(firstPart.Count - 1)
                .Concat(secondPart)
                .ToList();
        }
        else
        {
            // 直接保留首尾点
            return new List<Vector2> { points[0], points[points.Count - 1] };
        }
    }

    // 线段结构体辅助计算
    private struct LineSegment
    {
        public readonly Vector2 Start;
        public readonly Vector2 End;

        public LineSegment(Vector2 start, Vector2 end)
        {
            Start = start;
            End = end;
        }

        // 计算点到线段的垂直距离
        public float DistanceToPoint(Vector2 point)
        {
            float lengthSqr = (End - Start).sqrMagnitude;
            if (lengthSqr == 0) return Vector2.Distance(point, Start);

            float t = Vector2.Dot(point - Start, End - Start) / lengthSqr;
            t = Mathf.Clamp01(t);
            Vector2 projection = Start + t * (End - Start);
            return Vector2.Distance(point, projection);
        }
    }

注：epsilon需要通过多次测试，寻找出一个合适的值。阈值越大，线条越简单。

查看全文

http://www.kler.cn/a/589495.html