如何用 Python 实现 RDP 算法按容差 epsilon 简化折线点集并保持曲线形状【免费下载链接】PythonAll Algorithms implemented in Python项目地址: https://gitcode.com/GitHub_Trending/pyt/Python你手头有一串有序的二维点GPS 轨迹、扫描轮廓、折线图采样点想在点数显著减少的同时让折线的整体形状不被破坏。Python 仓库All Algorithms implemented in Python的geometry/目录下提供了一个 Ramer-Douglas-PeuckerRDP算法的纯标准库实现geometry/ramer_douglas_peucker.py。本文基于该文件及其文档字符串中的示例给出调用方式、行为判断和验证步骤。运行环境方面仓库 pyproject.toml 声明requires-python 3.14该模块只导入标准库的math没有第三方依赖。函数接口输入、epsilon 与返回保证核心函数签名为def ramer_douglas_peucker( pts: list[tuple[float, float]], epsilon: float, ) - list[tuple[float, float]]:文档字符串对参数的定义是pts按顺序排列的(x, y)点序列描述一条折线polyline必须是二维点epsilon被丢弃的点与简化后折线之间的最大允许距离必须非负返回值简化后的(x, y)点列表且pts的首点和末点始终保留。边界行为均来自该文件的文档字符串与实现空列表输入返回空列表点数少于 3 时原样返回实现中为if len(pts) 3: return list(pts)epsilon为负时抛出ValueError消息格式为epsilon must be non-negative, got {epsilon!r}。从仓库根目录可以直接导入使用from geometry.ramer_douglas_peucker import ramer_douglas_peucker用文档示例判断简化行为以下示例全部取自 geometry/ramer_douglas_peucker.py 的文档字符串是该仓库 doctest 会断言的输出# 文档示例中间点 (1.0, 0.1) 距端点连线的偏差在 epsilon0.5 之内被丢弃 ramer_douglas_peucker([(0.0, 0.0), (1.0, 0.1), (2.0, 0.0)], epsilon0.5) # [(0.0, 0.0), (2.0, 0.0)] # 文档示例中间点 (1.0, 1.0) 的偏差超过 epsilon0.5被保留 ramer_douglas_peucker([(0.0, 0.0), (1.0, 1.0), (2.0, 0.0)], epsilon0.5) # [(0.0, 0.0), (1.0, 1.0), (2.0, 0.0)] # 文档示例点数少于 3 时原样返回 ramer_douglas_peucker([(0.0, 0.0)], epsilon1.0) # [(0.0, 0.0)] # 文档示例负 epsilon 报错 ramer_douglas_peucker([(0.0, 0.0), (1.0, 0.5), (2.0, 0.0)], epsilon-1.0) # ValueError: epsilon must be non-negative, got -1.0这组示例覆盖了使用时的两个判断偏差小于等于 epsilon 的中间点会被丢弃超过 epsilon 的最远点会被保留并作为新的分段端点继续递归检查——这就是“按容差简化、保持形状”的具体含义。实现要点迭代栈与线段距离读 geometry/ramer_douglas_peucker.py 的主体循环时有两处直接影响行为的实现选择值得注意。第一处是距离度量。_perpendicular_distance返回点到线段的距离先把点在无限直线上的投影参数t钳制到[0, 1]投影落在段外时取到最近端点的距离。文档字符串明确解释RDP 需要这种度量因为直接使用无限直线距离会错误丢弃投影落在段端点之外的点t max(0.0, min(1.0, ((px - ax) * dx (py - ay) * dy) / seg_len_sq))第二处是迭代代替递归。主循环用显式栈保存待检查的索引区间(start, end)每轮找出区间内距端点连线最远的内部点若其距离大于 epsilon 则标记保留并把区间拆成两半压栈否则该区间内部点全部丢弃stack: list[tuple[int, int]] [(0, n - 1)] while stack: start, end stack.pop() if end - start 2: continue max_dist 0.0 max_index start for i in range(start 1, end): dist _perpendicular_distance(pts[i], pts[start], pts[end]) if dist max_dist: max_dist dist max_index i if max_dist epsilon: keep[max_index] True stack.append((start, max_index)) stack.append((max_index, end))源码注释说明了这样做的动机朴素的递归实现每层切片复制子列表每次调用 O(n)整体内存会到 O(n²)且长折线可能触碰 Python 递归深度限制按索引区间操作则避免了两点。模块头部文档字符串给出的复杂度为时间平均 O(n log n)、最坏 O(n²)空间 O(n)。验证方式运行内置 doctest该文件末尾通过if __name__ __main__调用doctest.testmod()所以两种验证命令都成立# 直接运行文件执行全部文档示例 python3 geometry/ramer_douglas_peucker.py # 带 -v 输出每个示例的执行情况这是 CONTRIBUTING.md 推荐的本地 doctest 命令形式 python3 -m doctest -v geometry/ramer_douglas_peucker.py成功条件是文档字符串中的所有示例空输入、少于 3 个点、中间点丢弃/保留、负 epsilon 的ValueError输出与预期一致。此外pyproject.toml 的[tool.pytest]配置了--doctest-modules用 pytest 跑仓库时这些 doctest 也会被收集执行CONTRIBUTING.md 说明这些 doctest 会随 CI 的自动化测试运行。限制与定位输入只支持二维(x, y)点文档与类型标注均按 2-D 描述没有三维版本文档字符串对 epsilon 的契约是“任何被丢弃的点距简化后折线不超过 epsilon”但函数本身不额外做数值校验容差的物理含义坐标单位由调用方自己保证README.md 声明仓库中的实现 “for learning purposes only”效率可能不及标准库或成熟几何库是否用于生产由使用者自行决定。目录导航中该条目列在 DIRECTORY.md 的 “Ramer Douglas Peucker” 一行指向同一文件可用于确认模块在仓库中的登记位置。【免费下载链接】PythonAll Algorithms implemented in Python项目地址: https://gitcode.com/GitHub_Trending/pyt/Python创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 如何用 Python 实现 RDP 算法按容差 epsilon 简化折线点集并保持曲线形状
如何用 Python 实现 RDP 算法按容差 epsilon 简化折线点集并保持曲线形状【免费下载链接】PythonAll Algorithms implemented in Python项目地址: https://gitcode.com/GitHub_Trending/pyt/Python你手头有一串有序的二维点GPS 轨迹、扫描轮廓、折线图采样点想在点数显著减少的同时让折线的整体形状不被破坏。Python 仓库All Algorithms implemented in Python的geometry/目录下提供了一个 Ramer-Douglas-PeuckerRDP算法的纯标准库实现geometry/ramer_douglas_peucker.py。本文基于该文件及其文档字符串中的示例给出调用方式、行为判断和验证步骤。运行环境方面仓库 pyproject.toml 声明requires-python 3.14该模块只导入标准库的math没有第三方依赖。函数接口输入、epsilon 与返回保证核心函数签名为def ramer_douglas_peucker( pts: list[tuple[float, float]], epsilon: float, ) - list[tuple[float, float]]:文档字符串对参数的定义是pts按顺序排列的(x, y)点序列描述一条折线polyline必须是二维点epsilon被丢弃的点与简化后折线之间的最大允许距离必须非负返回值简化后的(x, y)点列表且pts的首点和末点始终保留。边界行为均来自该文件的文档字符串与实现空列表输入返回空列表点数少于 3 时原样返回实现中为if len(pts) 3: return list(pts)epsilon为负时抛出ValueError消息格式为epsilon must be non-negative, got {epsilon!r}。从仓库根目录可以直接导入使用from geometry.ramer_douglas_peucker import ramer_douglas_peucker用文档示例判断简化行为以下示例全部取自 geometry/ramer_douglas_peucker.py 的文档字符串是该仓库 doctest 会断言的输出# 文档示例中间点 (1.0, 0.1) 距端点连线的偏差在 epsilon0.5 之内被丢弃 ramer_douglas_peucker([(0.0, 0.0), (1.0, 0.1), (2.0, 0.0)], epsilon0.5) # [(0.0, 0.0), (2.0, 0.0)] # 文档示例中间点 (1.0, 1.0) 的偏差超过 epsilon0.5被保留 ramer_douglas_peucker([(0.0, 0.0), (1.0, 1.0), (2.0, 0.0)], epsilon0.5) # [(0.0, 0.0), (1.0, 1.0), (2.0, 0.0)] # 文档示例点数少于 3 时原样返回 ramer_douglas_peucker([(0.0, 0.0)], epsilon1.0) # [(0.0, 0.0)] # 文档示例负 epsilon 报错 ramer_douglas_peucker([(0.0, 0.0), (1.0, 0.5), (2.0, 0.0)], epsilon-1.0) # ValueError: epsilon must be non-negative, got -1.0这组示例覆盖了使用时的两个判断偏差小于等于 epsilon 的中间点会被丢弃超过 epsilon 的最远点会被保留并作为新的分段端点继续递归检查——这就是“按容差简化、保持形状”的具体含义。实现要点迭代栈与线段距离读 geometry/ramer_douglas_peucker.py 的主体循环时有两处直接影响行为的实现选择值得注意。第一处是距离度量。_perpendicular_distance返回点到线段的距离先把点在无限直线上的投影参数t钳制到[0, 1]投影落在段外时取到最近端点的距离。文档字符串明确解释RDP 需要这种度量因为直接使用无限直线距离会错误丢弃投影落在段端点之外的点t max(0.0, min(1.0, ((px - ax) * dx (py - ay) * dy) / seg_len_sq))第二处是迭代代替递归。主循环用显式栈保存待检查的索引区间(start, end)每轮找出区间内距端点连线最远的内部点若其距离大于 epsilon 则标记保留并把区间拆成两半压栈否则该区间内部点全部丢弃stack: list[tuple[int, int]] [(0, n - 1)] while stack: start, end stack.pop() if end - start 2: continue max_dist 0.0 max_index start for i in range(start 1, end): dist _perpendicular_distance(pts[i], pts[start], pts[end]) if dist max_dist: max_dist dist max_index i if max_dist epsilon: keep[max_index] True stack.append((start, max_index)) stack.append((max_index, end))源码注释说明了这样做的动机朴素的递归实现每层切片复制子列表每次调用 O(n)整体内存会到 O(n²)且长折线可能触碰 Python 递归深度限制按索引区间操作则避免了两点。模块头部文档字符串给出的复杂度为时间平均 O(n log n)、最坏 O(n²)空间 O(n)。验证方式运行内置 doctest该文件末尾通过if __name__ __main__调用doctest.testmod()所以两种验证命令都成立# 直接运行文件执行全部文档示例 python3 geometry/ramer_douglas_peucker.py # 带 -v 输出每个示例的执行情况这是 CONTRIBUTING.md 推荐的本地 doctest 命令形式 python3 -m doctest -v geometry/ramer_douglas_peucker.py成功条件是文档字符串中的所有示例空输入、少于 3 个点、中间点丢弃/保留、负 epsilon 的ValueError输出与预期一致。此外pyproject.toml 的[tool.pytest]配置了--doctest-modules用 pytest 跑仓库时这些 doctest 也会被收集执行CONTRIBUTING.md 说明这些 doctest 会随 CI 的自动化测试运行。限制与定位输入只支持二维(x, y)点文档与类型标注均按 2-D 描述没有三维版本文档字符串对 epsilon 的契约是“任何被丢弃的点距简化后折线不超过 epsilon”但函数本身不额外做数值校验容差的物理含义坐标单位由调用方自己保证README.md 声明仓库中的实现 “for learning purposes only”效率可能不及标准库或成熟几何库是否用于生产由使用者自行决定。目录导航中该条目列在 DIRECTORY.md 的 “Ramer Douglas Peucker” 一行指向同一文件可用于确认模块在仓库中的登记位置。【免费下载链接】PythonAll Algorithms implemented in Python项目地址: https://gitcode.com/GitHub_Trending/pyt/Python创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考