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

道格拉斯-普克算法

是什么

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

应用场景

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

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

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

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

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

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

核心思想

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

一、初始化

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

二、递归处理

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

三、终止条件

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

代码

    /// <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

相关文章:

  • Android Room 框架公共模块源码深度剖析(四)
  • linux环境安装qnn_sdk 采坑记录
  • 事件驱动架构(EDA):微服务世界的未来趋势
  • LeetCode[206]反转链表
  • MySQL连接较慢原因分析及解决措施
  • C++基础 [五] - String的模拟实现
  • FlinkCDC 达梦数据库实时同步详解
  • java,poi,提取ppt文件中的文字内容
  • LLaMA-Factory微调sft Qwen2.5-VL-7B-Instruct
  • 【etcd】
  • 【通义千问】蓝耘智算 | 智启未来:蓝耘MaaS×通义QwQ-32B引领AI开发生产力
  • 本地部署DeepSeek-R1(Dify升级最新版本、新增插件功能)
  • 【嵌入式硬件】三款DCDC调试笔记
  • 【地图 Map】——8
  • C++进阶——AVL树的实现
  • FPGA中级项目3——IP核之时钟管理单元
  • [Linux]进程控制
  • 视频孪生技术赋能桥梁智慧化检测管理与数字化建设
  • android 后台下载任务,断点续传
  • 【数据分析】.loc和.iloc的应用2