折线简化

Elmar de Koning

4.93/5 (97投票s)

2010 年 10 月 1 日

MPL

28分钟阅读

286550

12577

n 维 Douglas-Peucker 近似的通用 C++ 实现。

简介

折线简化是降低折线分辨率的过程。这是通过移除顶点和边来实现的，同时保持对原始曲线的良好近似。折线简化的一个应用领域是计算机图形学。当折线分辨率高于显示器的分辨率时，折线中的多个顶点和边很可能会映射到单个像素上。这意味着您正在花费资源来绘制一些不可见的东西。通过在绘制折线之前降低其分辨率，可以轻松避免这种资源浪费。

本文介绍了 psimpl，这是一个通用、易于使用的折线简化库，支持以下算法：

简化算法

N^th 点 - 一个朴素算法，只保留每 n^th 个点
点之间的距离 - 移除彼此过于靠近的连续点
垂直距离 - 根据点到由其左右邻点定义的线段的距离来移除点
Reumann-Witkam - 沿着折线移动一个条带，并移除落在条带外的点
Opheim - 类似于 Reumann-Witkam，但使用最小和最大容差来限制搜索区域
Lang - 类似于垂直距离例程，但不是只查看直接邻点，而是处理整个搜索区域
Douglas-Peucker - 一种经典的简化算法，能很好地近似原始线
Douglas-Peucker 算法的一个变体 - 速度较慢，但在较低分辨率下效果更好

误差算法

位置误差 - 每个点到其简化的原始折线的距离

psimpl 是一个轻量级的仅头文件 C++ 库。所有算法都使用模板实现，并提供一个类似 STL 的接口，该接口操作输入和输出迭代器。折线可以具有任何维度，并使用浮点数或有符号整数数据类型定义。

有关 psimpl 的更多信息，包括新闻和最新版本，请参见 http://psimpl.sf.net。

如果您决定将我的代码用于您的（商业）项目，请告诉我！我很想知道我的代码最终用在哪里，以及您为什么选择使用它！

'Polyline Simplification' by Dan Sunday at softSurfer

这是我工作的基础。他清晰地解释了顶点减少和Douglas-Peucker 近似的原理，并提供了 C++ 实现。但是，他的实现基于浮点数，并且仅限于定义为Point对象数组的 2D 折线。他还使用了递归，这可能导致堆栈溢出问题。

'A C++ implementation of Douglas-Peucker Line Approximation Algorithm' by Jonathan de Halleux at CodeProject

提出了 Douglas-Peucker 近似算法的一种 O(n log n) 优化实现。内部使用 2D 凸包算法来实现更好的性能。因此，仅支持 2D 折线。其接口虽然灵活，但由于其点、点容器、键容器和凸包模板而过于复杂。

'A C# Implementation of Douglas-Peucker Line Approximation Algorithm' by CraigSelbert at CodeProject

将 Jonathan de Halleux 的 C++ 实现移植到 C# 的简单版本。

N^th 点

N^th 点例程是一种朴素的 O(n) 折线简化算法。它只保留第一个、最后一个以及每n^th个点。所有其他点都被移除。该过程如下所示：

图示显示了一个由 8 个顶点组成的折线：{v1, v2 ... v8}。该折线使用 n = 3 进行简化。生成的简化由以下顶点组成：{v1, v4, v7, v8}。

该算法速度极快，但遗憾的是，它在保留线条的几何特征方面效果不佳。

接口

template <unsigned DIM, class ForwardIterator, class OutputIterator>
OutputIterator simplify_nth_point (
    ForwardIterator first,
    ForwardIterator last,
    unsigned n,
    OutputIterator result)

使用指定的 n 值，将n^th 点例程应用于范围 [first, last)。生成的简化折线被复制到输出范围 [result, result + m*DIM)，其中 m 是简化折线的顶点数。返回值是输出范围的末尾：result + m*DIM。

输入（类型）要求

DIM 不为 0，其中 DIM 表示折线的维度
ForwardIterator 的值类型可转换为 OutputIterator 的值类型
范围 [first, last) 包含维度为 DIM 的倍数的顶点坐标，例如：x, y, z, x, y, z, x, y, z，当 DIM = 3 时
范围 [first, last) 至少包含 2 个顶点
n 不为 0

如果未满足这些要求，则将整个输入范围 [first, last) 复制到输出范围 [result, result + (last - first))，或可能发生编译错误。

实现细节

没有什么比这更简单的算法了。循环用于将输入折线的第一个点和每个后续的n^th点复制到简化结果中。循环结束后，我确保最后一个点包含在简化中。

用法

unsigned n = 10;                 // reduce to 10%
std::vector <float> polyline;    // original polyline, assume not empty 
std::vector <float> result;      // resulting simplified polyline
 
// simplify the 2d polyline
psimpl::simplify_nth_point <2> (polyline.begin (), polyline.end (),
                                n, std::back_inserter (result));

径向距离

点之间的距离是一种蛮力 O(n) 折线简化算法。它将过于接近的连续顶点减少为一个顶点，称为关键点。生成的关键点构成简化折线。该过程如下所示：

第一个和最后一个顶点始终是简化的一部分，因此被标记为关键点。从第一个关键点（第一个顶点）开始，算法沿着折线行走。所有距离该关键点在指定距离容差内的连续顶点都被移除。遇到的第一个距离容差大于指定距离的顶点被标记为关键点。从这个新关键点开始，算法将再次开始行走并重复此过程，直到到达最后一个关键点（最后一个顶点）。

接口

template <unsigned DIM, class ForwardIterator, class OutputIterator>
OutputIterator simplify_radial_distance (
    ForwardIterator first,
    ForwardIterator last,
    typename std::iterator_traits <ForwardIterator>::value_type tol,
    OutputIterator result)

使用指定的径向距离容差 tol，将点之间的距离例程应用于范围 [first, last)。生成的简化折线被复制到输出范围 [result, result + m*DIM)，其中 m 是简化折线的顶点数。返回值是输出范围的末尾：result + m*DIM。

输入（类型）要求

DIM 不为 0，其中 DIM 表示折线的维度
ForwardIterator 的值类型可转换为 OutputIterator 的值类型
范围 [first, last) 包含维度为 DIM 的倍数的顶点坐标，例如：x, y, z, x, y, z, x, y, z，当 DIM = 3 时
范围 [first, last) 至少包含 2 个顶点
tol 不为 0

如果未满足这些要求，则将整个输入范围 [first, last) 复制到输出范围 [result, result + (last - first))，或可能发生编译错误。

实现细节

没什么特别的，只是一个遍历所有顶点的循环，计算点与点之间的距离。一旦找到关键点，它就会被复制到输出范围。

用法

float tolerance = 10.f;          // point-to-point distance tolerance
std::vector <float> polyline;    // original polyline, assume not empty 
std::vector <float> result;      // resulting simplified polyline
 
// simplify the 2d polyline
psimpl::simplify_radial_distance <2> (polyline.begin (), polyline.end (),
                                      tolerance, std::back_inserter (result));

请注意，结果容器不需要与折线容器匹配。例如，您可以使用 C 风格的 double 数组。

垂直距离

与使用点到点（径向）距离容差作为拒绝标准（参见点之间的距离）不同，O(n)垂直距离例程使用点到线（垂直）距离容差。它通过原始折线的前两个顶点定义一条线。对于每个后续顶点 vi，计算其到该线的垂直距离。当此距离超过指定容差时，在 vi-1 处找到一个新关键点。然后使用顶点 vi 和 vi+1 定义一条新线，过程重复。算法说明如下：

最初，处理前三个顶点，并计算第二个顶点到线段 S(vi-1, vi+1) 的垂直距离。在将此距离与容差进行比较后，第二个顶点被视为关键点（简化的一部分）。然后算法沿着折线上移一个顶点，并开始处理下一组三个顶点。这次，计算出的距离低于容差，因此中间顶点被移除。算法继续通过上移两个顶点来执行。

请注意，对于每个被移除的顶点 vi，下一个可能的移除候选是 vi+2。这意味着原始折线最多只能缩减 50%。需要多次迭代才能实现更高的顶点缩减率。

接口

template <unsigned DIM, class ForwardIterator, class OutputIterator>
OutputIterator simplify_perpendicular_distance (
    ForwardIterator first,
    ForwardIterator last,
    typename std::iterator_traits <ForwardIterator>::value_type tol,
    OutputIterator result)
 
template <unsigned DIM, class ForwardIterator, class OutputIterator>
OutputIterator simplify_perpendicular_distance (
    ForwardIterator first,
    ForwardIterator last,
    typename std::iterator_traits <ForwardIterator>::value_type tol,
    unsigned repeat,
    OutputIterator result)

使用指定的垂直距离容差 tol（重复 repeat 次），将垂直距离例程应用于范围 [first, last)。生成的简化折线被复制到输出范围 [result, result + m*DIM)，其中 m 是简化折线的顶点数。返回值是输出范围的末尾：result + m*DIM。

输入（类型）要求

DIM 不为 0，其中 DIM 表示折线的维度
ForwardIterator 的值类型可转换为 OutputIterator 的值类型
范围 [first, last) 包含维度为 DIM 的倍数的顶点坐标，例如：x, y, z, x, y, z, x, y, z，当 DIM = 3 时
范围 [first, last) 至少包含 2 个顶点
tol 不为 0
n 不为 0

如果未满足这些要求，则将整个输入范围 [first, last) 复制到输出范围 [result, result + (last - first))，或可能发生编译错误。

实现细节

主函数（不带 repeat 参数）是一个单循环，从处理前三个连续顶点开始。根据第二个或第三个顶点被视为简化（称为关键点）的一部分，算法沿着原始折线上移一个或两个顶点。一旦找到关键点，它就会被复制到输出迭代器。

第二个函数（接受 repeat 值作为输入）是主函数的包装器，包含三个不同的步骤：

第一次迭代：将范围 [first, last) 简化为纯 C 风格数组。
中间迭代：从纯 C 风格数组进行简化并复制到纯 C 风格数组。
最后一次迭代：从纯 C 风格数组简化到输出迭代器 result。

每次迭代后，都会检查简化是否有所改进。如果没有改进，则将当前结果直接复制到输出迭代器 result。请注意，最多可以创建两个临时副本：一个副本是输入范围，另一个是第一个中间简化结果。

用法

double tolerance = 10.0;         // point-to-segment distance tolerance
std::deque <double> polyline;    // original polyline, assume not empty 
std::deque <double> result;      // resulting simplified polyline
 
// simplify the 3d polyline - single pass
psimpl::simplify_perpendicular_distance <3> (polyline.begin (), polyline.end (),
                                             tolerance, std::back_inserter (result));
 
double tolerance = 10.0;         // point-to-segment distance tolerance
usinged repeat = 5;              // apply the routine 5 times
std::deque <double> polyline;    // original polyline, assume not empty 
std::deque <double> result;      // resulting simplified polyline
 
// simplify the 3d polyline - multi pass
psimpl::simplify_perpendicular_distance <3> (polyline.begin (), polyline.end (), tolerance,
                                             repeat, std::back_inserter (result));

Reumann-Witkam

与使用点到点（径向）距离容差作为拒绝标准（参见点之间的距离）不同，O(n)Reumann-Witkam例程使用点到线（垂直）距离容差。它通过原始折线的前两个顶点定义一条线。对于每个后续顶点 vi，计算其到该线的垂直距离。当此距离超过指定容差时，在 vi-1 处找到一个新关键点。然后使用顶点 vi 和 vi+1 来定义一条新线，过程重复。算法说明如下：

红色条带由指定的容差和通过折线前两个顶点的线构成。第三个顶点不在条带内，这意味着第二个顶点是关键点。使用通过第二个和第三个顶点组成的线定义一个新条带。仍然包含在该条带内的最后一个顶点被视为下一个关键点。所有其他包含的顶点都被移除。此过程重复进行，直到构造出一个包含原始折线最后一个顶点的条带。

接口

template <unsigned DIM, class ForwardIterator, class OutputIterator>
OutputIterator simplify_reumann_witkam (
    ForwardIterator first,
    ForwardIterator last,
    typename std::iterator_traits <ForwardIterator>::value_type tol,
    OutputIterator result)

使用指定的垂直距离容差 tol，将Reumann-Witkam例程应用于范围 [first, last)。生成的简化折线被复制到输出范围 [result, result + m*DIM)，其中 m 是简化折线的顶点数。返回值是输出范围的末尾：result + m*DIM。

输入（类型）要求

DIM 不为 0，其中 DIM 表示折线的维度
ForwardIterator 的值类型可转换为 OutputIterator 的值类型
范围 [first, last) 包含维度为 DIM 的倍数的顶点坐标，例如：x, y, z, x, y, z, x, y, z，当 DIM = 3 时
范围 [first, last) 至少包含 2 个顶点
tol 不为 0

如果未满足这些要求，则将整个输入范围 [first, last) 复制到输出范围 [result, result + (last - first))，或可能发生编译错误。

实现细节

没什么特别的，只是一个遍历所有顶点的循环，计算它们到当前条带的距离。一旦找到关键点，它就会被复制到输出范围，并且当前条带会更新。

用法

float tolerance = 10.f;          // point-to-line perpendicular distance tolerance
std::vector <float> polyline;    // original polyline, assume not empty 
std::vector <double> result;     // resulting simplified polyline
 
// simplify the 4d polyline
psimpl::simplify_reumann_witkam <4> (polyline.begin (), polyline.end (),
                                     tolerance, std::back_inserter (result));

这个例子表明输入和输出迭代器的值类型不必相同。

Opheim

O(n)Opheim例程与Reumann-Witkam例程非常相似，可以看作是Reumann-Witkam例程的约束版本。Opheim同时使用最小和最大距离容差来限制搜索区域。对于每个后续顶点 vi，计算其到当前关键点 vkey（最初是 v0）的径向距离。用于定义射线 R（vkey, vi）的最后一个距离最小容差内的点。如果不存在这样的 vi，则射线定义为 R(vkey, vkey+1)。对于 vi 之后的每个后续顶点 vj，计算其到射线 R 的垂直距离。当此距离超过最小容差时，或当 vj 与 vkey 之间的径向距离超过最大容差时，在 vj-1 处找到一个新关键点。找到新关键点后，过程重复。

上图说明了Opheim简化过程。注意搜索区域是如何由最小和最大容差约束的。结果是，在第二步中，只移除了一个点。使用无限或无约束搜索区域的Reumann-Witkam例程将移除两个点。

接口

template <unsigned DIM, class InputIterator, class OutputIterator>
OutputIterator simplify_opheim (
    ForwardIterator first,
    ForwardIterator last,
    typename std::iterator_traits <ForwardIterator>::value_type minTol,
    typename std::iterator_traits <ForwardIterator>::value_type maxTol,
    OutputIterator result)

使用指定的距离容差 minTol 和 maxTol，将Opheim例程应用于范围 [first, last)。生成的简化折线被复制到输出范围 [result, result + m*DIM)，其中 m 是简化折线的顶点数。返回值是输出范围的末尾：result + m*DIM。

输入（类型）要求

DIM 不为 0，其中 DIM 表示折线的维度
ForwardIterator 的值类型可转换为 OutputIterator 的值类型
范围 [first, last) 包含维度为 DIM 的倍数的顶点坐标，例如：x, y, z, x, y, z, x, y, z，当 DIM = 3 时
范围 [first, last) 至少包含 2 个顶点
minTol 不为 0
maxTol 不为 0

如果未满足这些要求，则将整个输入范围 [first, last) 复制到输出范围 [result, result + (last - first))，或可能发生编译错误。

实现细节

我发现，所有提及或讨论Opheim算法的文章都未能解释如何定义控制搜索区域方向的射线。据我所知，有三种可能的方法可以确定射线 R(vkey, vi)，其中 vkey 是当前关键点。

Reumann-Witkam方式：i = key+1
第一个超出点：key < i 且 vi 是第一个超出最小径向距离容差的点
最后一个在内点：key < i 且 vi 是最后一个在最小径向距离容差内的点；如果不存在这样的 vi，则回退到Reumann-Witkam方式

我使用位置误差统计数据比较了这三种方法，发现“第一个超出点”方法在大多数情况下比“Reumann-Witkam”方法产生的结果略好。此外，“最后一个在内点”和“第一个超出点”方法之间似乎没有实际区别。我最终选择了“最后一个在内点”方法，因为它更适合我已经实现过的循环。

用法

float minimum = 10.f;            // minimum distance tolerance
float maximum = 100.f;           // maximum distance tolerance
std::vector <double> polyline;   // original polyline, assume not empty 
std::vector <double> result;     // resulting simplified polyline
 
// simplify the 4d polyline
psimpl::simplify_opheim <4> (polyline.begin (), polyline.end (),
                             minimum, maximum, std::back_inserter (result));

Lang

Lang简化算法定义了一个固定大小的搜索区域。该搜索区域的第一个和最后一个点构成一个线段。该线段用于计算到每个中间点的垂直距离。如果任何计算出的距离大于指定容差，则通过排除其最后一个点来缩小搜索区域。此过程将继续进行，直到所有计算出的距离都低于指定容差，或者没有更多中间点。所有中间点都被移除，并从旧搜索区域的最后一个点开始定义一个新的搜索区域。该过程如下所示：

搜索区域是通过 look_ahead 值 4 构建的。对于每个中间顶点，计算其到线段 S (v0, v4) 的垂直距离。由于至少有一个距离大于容差，因此搜索区域减少了一个顶点。在重新计算到 S (v0, v3) 的距离后，所有中间顶点都落在容差范围内。搜索区域的最后一个顶点 v3 定义了一个新的关键点。此过程通过更新搜索区域并定义新线段 S (v3, v7) 来重复。

接口

template <unsigned DIM, class BidirectionalIterator, class OutputIterator>
OutputIterator simplify_lang (
    BidirectionalIterator first,
    BidirectionalIterator last,
    typename std::iterator_traits <BidirectionalIterator>::value_type tol,
    unsigned look_ahead,
    OutputIterator result)

使用指定的垂直距离容差和前瞻值，将Lang简化算法应用于范围 [first, last)。生成的简化折线被复制到输出范围 [result, result + m*DIM)，其中 m 是简化折线的顶点数。返回值是输出范围的末尾：result + m*DIM。

输入（类型）要求

DIM 不为 0，其中 DIM 表示折线的维度
BidirectionalIterator 的值类型可转换为 OutputIterator 的值类型
范围 [first, last) 包含维度为 DIM 的倍数的顶点坐标，例如：x, y, z, x, y, z, x, y, z，当 DIM = 3 时
范围 [first, last) 至少包含 2 个顶点
tol 不为 0。
look_ahead 不为 0。

如果未满足这些要求，则将整个输入范围 [first, last) 复制到输出范围 [result, result + (last - first))，或可能发生编译错误。

实现细节

Lang简化算法要求其输入迭代器模拟双向迭代器的概念。原因是搜索区域 S (vi, vi+n) 可能需要缩小到 S (vi, vi+(n-1))。最简单的方法是递减指向 vi+n 的迭代器。虽然可以通过仅对前向迭代器递增 vi 的副本 n-1 次来完成，但这需要额外的簿记。它还使代码复杂化，因为我们只想对前向迭代器采用这种方法。

用法

float tolerance = 10.f;       // point-to-segment distance tolerance
unsigned look_ahead = 7;      // search region size
std::vector <float> polyline; // original polyline, assume not empty
std::vector <double> result;  // resulting simplified polyline

// simplify the 5d polyline
psimpl::simplify_lang <5> (
    polyline.begin (), polyline.end (),
    tolerance, look_ahead,
    std::back_inserter (result));

使用 look_ahead 值 7 意味着生成的简化将始终包含原始点数的至少 1/7 或 14%。look_ahead 值约束了简化。

Douglas-Peucker

Douglas-Peucker算法使用点到边距离容差。该算法从一个粗略的简化开始，该简化是由连接原始折线第一个和最后一个顶点的单个边组成的。然后计算所有中间顶点到该边的距离。距离该边最远且计算距离大于指定容差的点将被标记为关键点并添加到简化中。此过程将递归地应用于当前简化中的每个边，直到原始折线的所有顶点都与简化结果在容差范围内。该过程如下所示：

最初，简化由一条边组成。在第一步中，第四个顶点被标记为关键点，并相应地调整了简化。在第二步中，处理当前简化的第一条边。到该边的最大顶点距离低于容差阈值，并且没有添加新的关键点。在第三步中，为当前简化的第二条边找到一个关键点。此边在关键点处被分割，并更新了简化。此过程继续进行，直到找不到更多关键点。请注意，在每一步中，只处理当前简化的一个边。

此算法的最坏情况运行时间为 O(nm)，平均为 O(n log m)，其中 m 是简化折线的大小。因此，这是一个与输出相关的算法，当 m 很小时，它会非常快。为了使其速度更快，点之间的距离例程被用作预处理步骤。

接口

template <unsigned DIM, class ForwardIterator, class OutputIterator>
OutputIterator simplify_douglas_peucker (
    ForwardIterator first,
    ForwardIterator last,
    typename std::iterator_traits <ForwardIterator>::value_type tol,
    OutputIterator result)

使用指定的容差 tol，将点之间的距离例程后跟Douglas-Peucker近似应用于范围 [first, last)。生成的简化折线被复制到输出范围 [result, result + m*DIM)，其中 m 是简化折线的顶点数。返回值是输出范围的末尾：result + m*DIM。

输入（类型）要求

DIM 不为 0，其中 DIM 表示折线的维度
ForwardIterator 的值类型可转换为 OutputIterator 的值类型
范围 [first, last) 包含维度为 DIM 的倍数的顶点坐标，例如：x, y, z, x, y, z, x, y, z，当 DIM = 3 时
范围 [first, last) 至少包含 2 个顶点
tol 不为 0。

如果未满足这些要求，则将整个输入范围 [first, last) 复制到输出范围 [result, result + (last - first))，或可能发生编译错误。

实现细节

最初，我的重点是限制算法的内存使用。因此，所有算法都返回一个 std::vector<bool>，而不是使用输出迭代器。每个顶点一个布尔值，用于确定该顶点是否为关键点，因此是简化的一部分。此关键点标记列表可用作另一个算法的输入，允许按顺序运行不同的算法。一个单独的函数可以选择性地将所有关键点复制到某个输出范围。

这种方法有效，但存在一些严重的缺点：

代码速度慢，尤其对于非随机访问迭代器
代码因所有簿记而变得过于复杂
使用代码时，我总是需要简化的实际副本，而不是一堆关键点标记

我做的第一个改变是每个算法的接口。与其返回关键点标记，不如使用输出迭代器将简化结果复制到输出范围。第二个改变是将点之间的距离预处理步骤产生的中间结果存储在纯 C 风格数组中。该数组随后在Douglas-Peucker近似过程中使用。这种方法的优点远远超过了内存使用量的增加。

将点之间的距离例程作为预处理步骤变得微不足道；我只需要创建一个数组并为其指定一个输出迭代器
代码更少 - 缺乏针对不同迭代器类别的特定代码，以及更少的簿记
代码更快 - 处理 C 风格数组和值类型指针通常比使用迭代器更快，尤其是在处理非随机访问迭代器时
更简洁的接口

算法本身是一个简单的循环。初始边被添加到 std::stack。只要堆栈不为空，就会弹出并处理一条边。计算其关键点和到关键点的距离。如果计算出的距离大于容差，则将关键点添加到简化中。边被分割，两个子边被添加到堆栈中。当顶点添加到简化中时，它只被标记为关键点。算法完成后，所有标记的顶点（关键点）将被复制到输出范围。

用法

double tolerance = 10;                           // point-to-edge distance tolerance
std::deque <double> polyline;                    // original polyline, assume not empty 
double* result = new double [polyline.size ()];  // make sure the result array 
                                                 // is large enough
// simplify the 3d polyline
psimpl::simplify_douglas_peucker <3> (polyline.begin (), polyline.end (),
                                      tolerance, result);

此示例表明输入和输出容器不必相同。

Douglas-Peucker (变体)

此算法是原始实现的一个变体。其主要区别在于：

使用点数容差而不是点到边距离容差。这允许您指定简化折线中的顶点数。使用原始实现，您永远无法确定有多少个顶点会保留下来。
不是一次处理一条边（随机选择），而是同时考虑当前简化折线的所有边。这些边中的每一个都可能定义一个新关键点。在所有这些可能的关键点中，选择具有最高点到边距离的点作为新关键点。

始终根据所有可能关键点选择下一个关键点的直接结果是，简化结果的质量更高。尤其是在使用非常低的点数容差时，这一点更为明显。缺点是我们不能使用点之间的距离例程作为预处理步骤来加速算法。

接口

template <unsigned DIM, class ForwardIterator, class OutputIterator>
OutputIterator simplify_douglas_peucker_n (
    ForwardIterator first,
    ForwardIterator last,
    unsigned count,
    OutputIterator result)

使用 Douglas-Peucker 近似的变体应用于范围 [first, last)。生成的简化折线包含 count 个顶点，并被复制到输出范围 [result, result + count)。返回值是输出范围的末尾：result + count。

输入（类型）要求

DIM 不为 0，其中 DIM 表示折线的维度
ForwardIterator 的值类型可转换为 OutputIterator 的值类型
范围 [first, last) 包含维度为 DIM 的倍数的顶点坐标，例如：x, y, z, x, y, z, x, y, z，当 DIM = 3 时
范围 [first, last) 包含至少 count 个顶点
count 至少为 2

如果未满足这些要求，则将整个输入范围 [first, last) 复制到输出范围 [result, result + (last - first))，或可能发生编译错误。

实现细节

此变体的实现与原始实现仅有少量差异。主要区别在于没有预处理步骤，以及处理当前简化边的方式。

对于添加到当前简化的每条边，都会计算其关键点。此关键点以及边及其到该边的距离都存储在 std::priority_queue 中。此队列可确保其顶部元素包含具有最大点边距离的关键点。只要简化不包含所需的点数，就会从队列中弹出顶部元素，并将其关键点添加到简化中。相应的边被分割，两个子边被处理并存储在队列中。

出于性能原因，输入折线会被复制到纯 C 风格数组中。请注意，对于原始实现，此复制在点之间的距离预处理步骤中自动完成。

用法

unsigned tolerance = 25;          // point count tolerance
std::list <long long> polyline;   // original polyline, assume not empty 
std::vector <double> result;      // resulting simplified polyline
 
// simplify the 4d polyline to 25 points
psimpl::simplify_douglas_peucker_n <4> (polyline.begin (), polyline.end (),
                                        tolerance, std::back_inserter (result));

此示例演示了使用带有有符号整数数据类型的非随机访问容器。

位置误差

简化折线会引入形状失真。简化的程度越高，失真的量也越大。衡量简化引起的误差的一种方法是查看原始线和简化线之间的位置差异。

对于每个原始点，位置误差计算为该点与简化中的相应线段之间的垂直距离。性能更好的简化算法始终产生较低的位置误差。

接口

template <unsigned DIM, class ForwardIterator, class OutputIterator>
OutputIterator compute_positional_errors2 (
    ForwardIterator original_first,
    ForwardIterator original_last,
    ForwardIterator simplified_first,
    ForwardIterator simplified_last,
    OutputIterator result,
    bool* valid)

对于范围 [original_first, original_last) 中的每个点，计算其到简化 [simplified_first, simplified_last) 的**平方**距离。每个位置误差都被复制到输出范围 [result, result + (original_last - original_first))。请注意，原始和简化折线都必须使用相同的 value_type 定义。

template <unsigned DIM, class ForwardIterator>
math::Statistics compute_positional_error_statistics (
    ForwardIterator original_first,
    ForwardIterator original_last,
    ForwardIterator simplified_first,
    ForwardIterator simplified_last,
    bool* valid)

计算范围 [original_first, original_last) 与其简化范围 [simplified_first, simplified_last) 之间的位置误差的统计数据（均值、最大值、总和、标准差）。所有统计数据都存储为 doubles。

输入（类型）要求

DIM 不为 0，其中 DIM 表示折线的维度
ForwardIterator 的值类型可转换为 OutputIterator 的值类型（仅适用于compute_positional_errors2）
ForwardIterator 的值类型可转换为 double（仅适用于compute_positional_error_statistics）
范围 [original_first, original_last) 和 [simplified_first, simplified_last) 包含维度为 DIM 的倍数的顶点坐标，例如：x, y, z, x, y, z, x, y, z，当 DIM = 3 时
范围 [original_first, original_last) 和 [simplified_first, simplified_last) 至少包含 2 个顶点
范围 [simplified_first, simplified_last) 表示范围 [original_first, original_last) 的简化，这意味着简化中的每个点都具有与原始折线中某个点完全相同的坐标。

如果未满足这些要求，则将 valid 标志设置为 false，或可能发生编译错误。

实现细节

该算法使用两个嵌套循环实现。外层循环处理简化中的每个线段。内层循环处理原始折线中的每个点，计算到当前线段的垂直距离。内层循环在点精确匹配线段端点坐标时结束。

当外层循环完成处理简化中的所有线段后，简化折线中的最后一个点应与原始折线中最后一个处理的点精确匹配。只有当此条件满足时，计算出的位置误差才被视为有效。这意味着我只能在计算并复制误差到输出范围后才能知道结果是否有效。因此，我需要一种方法来告知调用者。一种选择是抛出异常。但是，我设计 psimpl 不抛出任何异常（参见“关于代码”部分）。相反，我选择了可选的布尔值 valid。

用法

std::vector <double> original;      // original polyline, assume not empty
std::vector <double> simplified;    // simplified polyline, assume not empty
std::vector <double> errors;        // calculated errors
bool valid = false;                 // indicates if the calculated errors are valid

// compute the squared positional error for each point of the original 2d polyline
psimpl::compute_positional_errors2 <2> (original.begin (), original.end (),
                                        simplified.begin (), simplified.end (),
                                        std::back_inserter (errors), &valid);

// compute positional error statistics for all points of the original 2d polyline
psimpl::math::Statistics stats =
    psimpl::compute_positional_error_statistics <2> (original.begin (), original.end (),
                                                     simplified.begin (), simplified.end (),
                                                     &valid);

关于代码

如前所述，所有算法的实现都包含在头文件 psimpl.h 中。该文件结构如下：

namespace psimpl

namespace util

class scoped_array <T>

namespace math

struct Statistics
function equal <unsigned, InputIterator>
function make_vector <unsigned, InputIterator, OutputIterator>
function dot <unsigned, InputIterator>
function interpolate <unsigned, InputIterator, OutputIterator>
function point_distance2 <unsigned, InputIterator1, InputIterator2>
function line_distance2 <unsigned, InputIterator>
function segment_distance2 <unsigned, InputIterator>
function ray_distance2 <unsigned, InputIterator>
function compute_statistics <InputIterator>

class PolylineSimplification <unsigned, InputIterator, OutputIterator>

function NthPoint
function RadialDistance
function PerpendicularDistance
function ReumannWitkam
function Opheim
function Lang
function DouglasPeucker
function DouglasPeuckerAlt
function ComputePositionalErrors2
function ComputePositionalErrorStatistics
class DPHelper

function simplify_nth_point <unsigned, ForwardIterator, OutputIterator>
function simplify_radial_distance <unsigned, ForwardIterator, OutputIterator>
function simplify_perpendicular_distance <unsigned, ForwardIterator, OutputIterator>
function simplify_reumann_witkam <unsigned, ForwardIterator, OutputIterator>
function simplify_opheim <unsigned, ForwardIterator, OutputIterator>
function simplify_lang <unsigned, BidirectionalIterator, OutputIterator>
function simplify_douglas_peucker <unsigned, ForwardIterator, OutputIterator>
function simplify_douglas_peucker_n <unsigned, ForwardIterator, OutputIterator>
function compute_positional_errors2 <unsigned, ForwardIterator, OutputIterator>
function compute_positional_error_statistics <unsigned, ForwardIterator>

所有代码都包含在根命名空间 psimpl 中。util::scoped_array 类，类似于 boost::scoped_array，是一个用于保存动态分配数组的智能指针。math 是一个包含与计算各种几何实体之间平方距离相关的所有函数的命名空间。PolylineSimplification 类提供了每个简化算法的实现。它只包含操作 InputIterator 和 OutputIterator 类型的成员函数。对于Douglas-Peucker例程，使用了内部类 DPHelper。这个辅助类封装了所有操作值类型指针的代码。顶级函数是为了方便，因为它们为其对应的 PolylineSimplification 成员函数提供了模板类型推导。

psimpl 本身不抛出异常。原因是我认为异常处理在 C++ 应用程序中相当罕见。与 .NET 世界不同，许多开发人员根本不使用它，甚至很少考虑它。

关于演示应用程序

演示应用程序允许您试验不同的简化算法。它可以生成各种类型容器的伪随机 2D 折线，最多可达 10,000,000 个顶点。生成的折线的边界框始终为 n x n/2，其中 n 是生成折线的顶点数。使用此事实来指定适当的距离容差。可以通过可视化和使用计算出的位置误差统计数据来比较各种算法。这些统计数据仅在所选容器的 value_type 为 double 时可用。

内部，生成的折线和简化后的折线始终存储在 QVector<double> 中。在简化之前，将其转换为选定的容器类型。之后，此临时容器将被销毁。通常，您不会注意到这一点，但似乎创建和销毁 std::list(10.000.000) 可能需要相当长的时间。生成的性能测量不包括这些转换步骤。我选择这种方法是因为它允许我快速添加新的容器类型。

请注意，整个应用程序是单线程的（抱歉我太懒了），这意味着它在长时间运行的简化过程中可能会出现“未响应”的情况。

演示应用程序是使用Qt 4.7.3、Qt Creator 2.1.0和Visual Studio 2008 Express制作的。包含完整的源代码。

即将发布的版本

我将在未来某个时候添加的算法（排名不分先后）：

随机点例程
Jenks 简化
Lang 简化
Visvalingam-Whyatt 简化
Zhao-Saalfeld 简化
计算因简化引起的面积误差

其他我想要研究的东西：

将Douglas-Peucker拆分为两个算法：一个标准实现和一个使用点之间的距离预处理步骤的实现
一个独立版本的 psimpl，它操作点容器而不是坐标容器
用于计算原始折线数据类型与简化数据类型不同的情况下的位置误差

历史记录

28-09-2010

初始版本

23-10-2010

将许可证从 CPOL 更改为 MPL
相应地更新了源代码和演示包，并添加了关于许可证的小节

26-10-2010

澄清了输入（类型）要求，并更改了算法在无效输入下的行为

01-12-2010

添加了 N^th 点、垂直距离和 Reumann-Witkam 例程
将所有与距离计算相关的函数移至 math 命名空间；重构

10-12-2010

修复了垂直距离例程中的一个错误

27-02-2011

添加了 Opheim 简化，以及用于计算简化引起的位置误差的函数
将 simplify_douglas_peucker_alt 重命名为 simplify_douglas_peucker_n

18-06-2011

添加了 Lang 简化
修复了使用整数时的除零错误
修复了在无效输入下返回了错误输出迭代器的一个错误
修复了 douglas_peucker_n 中可能返回错误数量点的错误
修复了 compute_positional_errors2 中要求输出和输入迭代器类型相同的错误；修复了 compute_positional_error_statistics 中在可疑输入下可能返回无效统计数据的错误；记录了每个算法的输入迭代器要求
对大多数算法进行了杂项重构

折线简化

目录

简介

相关文章

Nth 点

接口

输入（类型）要求

实现细节

用法

径向距离

接口

输入（类型）要求

实现细节

用法

垂直距离

接口

输入（类型）要求

实现细节

用法

Reumann-Witkam

接口

输入（类型）要求

实现细节

用法

Opheim

接口

输入（类型）要求

实现细节

用法

Lang

接口

输入（类型）要求

实现细节

用法

Douglas-Peucker

接口

输入（类型）要求

实现细节

用法

Douglas-Peucker (变体)

接口

输入（类型）要求

实现细节

用法

位置误差

接口

输入（类型）要求

实现细节

用法

关于代码

关于演示应用程序

即将发布的版本

历史记录

N^th 点