Douglas-Peucker 线近似算法的 C++ 实现

• DPHull_src.zip - 13.6 Kb
• DPHull_exe.zip - 31.9 Kb
• DPHull_demo.zip - 295 Kb
• DPHull 文档 (压缩 HTML) - 82.9 Kb

引言

在进行数学模拟或工程问题处理时，处理包含数千个点的曲线是很常见的。通常，显示所有点是没用的，因为屏幕精度是有限的，许多点将显示在同一个像素上。因此，您会白白消耗大量资源！

本文介绍了一种基于 Douglas-Peucker 算法（参见 [1]）的快速二维线近似算法，该算法在地图绘制界广为人知。它通过选择最少的关键点，围绕曲线计算一个经过容差因子缩放的包络。该算法具有多项优点：

• 速度快！对于一个包含 n 个点的曲线，近似的计算时间与 nlog_2(n) 成正比。
• 您不需要对曲线有先验知识。
• 压缩率可以通过容差参数轻松调整。

该类已集成到一个绘图库：Plot Graphic Library。

Douglas-Peucker (DP) 线简化算法

DP 线简化算法最初由 [1] 提出。John Hershberger 和 Jack Snoeyink 在 [2] 中以 C 语言实现了一个名为 DPSimp 的软件包。

DPsimp 是 John Hershberger 和 Jack Snoeyink 实现的 Douglas-Peucker 线简化算法。他们分析了 Douglas 和 Peucker 报告的线简化算法，并表明其最坏情况下的复杂度与输入点的数量 n 成二次方关系。该算法基于路径包络，利用问题的几何结构，实现了运行时间与 nlog_2(n) 成正比的最坏情况复杂度，这是 Douglas 算法的最佳情况。

该算法基于路径包络的递归构建，如下图所示。他们完成了所有艰苦的工作（用 C 语言编写了基础代码），我将其移植到了 C++ 模板。

对 DPSimp 的修改

DPSimp 在 DP 方法中使用了递归调用。当算法深入递归时，这可能导致堆栈溢出。为避免此问题，已向该类添加了一个内部堆栈，以模拟递归函数调用而不发生堆栈溢出。

概念与类设计

令 points 表示原始曲线的所有点，keys 表示为近似而保留的原始曲线中的点。

思路是用户提供一个 points 的容器，称为 PointContainer，以及一个 keys 的容器，称为 KeyContainer，而这些容器之间的链接将是线简化类，称为 LineApproximator。

如何在不限制于特定容器的情况下构建类层次结构？事实上，一个用户可能将他们的 points 存储在 vector< pair<T,T>> 中，而另一个用户可能将其存储在两个单独的 vector<T> 中。当然，同样的论点也适用于 KeyContainer。

一个可能的答案是模板化。将 PointContainer 和 KeyContainer 作为 LineApproximator 的模板参数，可以在不指定容器的情况下构建近似类，因为类是在编译时构建的（我们可以为这些容器编写接口，但实际上，我太懒了：）。

有了这个想法，以下是容器的规范：

PointContainer

设

• Point 是一个结构、模板或类，其成员 x,y 的类型为 T。
• PointRef 是一个结构、模板或类，其成员 x,y 的类型为 T&。

PointContainer 的行为类似于 Point 的向量。

• 具有 clear(), size() 和 resize() 方法。
• 具有随机访问迭代器。
• const_iterator 指向类似于 Point 的结构。
• iterator 指向类似于 PointRef 的结构。
• operator[] const 返回一个 Point。
• operator[] 返回一个 PointRef。

一个简单的有效 PointContainer 示例是：

vector<Point>

然而，已经开发了一个混合容器来处理 x 和 y 存储在单独容器中的情况（见下文）。

KeyContainer

KeyContainer 的行为类似于 PointContainer::const_iterator 的列表。

• 具有 size(), clear() 方法。
• 支持 push_back 方法。

一个简单的有效 KeyContainer 示例是：

vector<PointContainer::const_iterator>

同样，提供了一个混合容器来处理需要将 keys 输出到单独容器的情况。

模板

所有类都是模板化的，以支持该算法的 float 和 double 版本。

模板 TDPHull 是 DP 算法的用户接口。然而，它依赖于下面详述的一系列子类：

名称	描述	用途
TLine<T, TPointContainer, TKeyContainer>	二维线模板。	点和键。
TLineApproximator<T, TPointContainer, TKeyContainer>	二维线近似器基类。	近似算法的默认接口。
TDPHull<T, TPointContainer, TKeyContainer>	实现 Douglas-Peukler 算法。	用户前端。
TPathHull<T, TPointContainer, TKeyContainer>	路径包络。	TDPHull<T> 内部。
TPoint<T>	T 的一对：x, y。	二维点 TLineApproximator<T> 的模板。
TPointRef<T>	T& 的一对：x, y。	二维点 TLineApproximator<T> 的模板。
SHomog	二维齐次点，T x,y,w。	TLineApproximator<T> 的内部结构。

如何使用 TDPHull？

在以下示例中，我们采用以下表示法：

using namespace hull; // all classes are in the hull namespace,
using namespace std; // using some STL containers

// defining the point container
typedef vector<TPoint<float>> VectorPointContainer; 
// defining the key container
typedef vector<MyPointContainer::const_iterator> ListKeyContainer; 
// defining the line approximation class
typedef TDPHull<float, VectorPointContainer, ListKeyContainer> CDPHullF; 
CDPHullF dp; // a DPHull object, note that you can also work with doubles

近似方法会抛出异常，因此您应该始终将它们包含在 try-catch 语句中。

规范化

默认情况下，数据点在近似之前会被归一化。这是为了减少梯度计算中的数值误差。当数据比例不合适时会发生这种情况：使用非常接近的大数字会导致严重损失有效数字。

但是，如果您对数据有信心，可以通过使用 SetNormalization 来禁用它。

处理点和键

获取对点容器的引用并修改它。

// getting reference to container,
TDPHull<float>::PointContainer& pc = dp.GetPoints(); 
for (UINT i=0;i<pc.size();i++)
{
    pc[i].x=...;
    pc[i].y=...;
}

如果您正在使用归一化（默认行为），请不要忘记在修改数据后重新计算数据的边界框。

dp.ComputeBoundingBox();

近似调优

您可以通过多种方式控制压缩率：

• 设置容差。

  // Setting tolerance of approximation
  dp.SetTol(0.5);

• 设置压缩率，可接受的压缩阈值。

  // dp will find the tolerance corresponding to 10 % of
  // the original points, with 5% of possible error.
  try
  {
      dp.ShrinkNorm(0.1,0.05);
  }
  catch(TCHAR* str)
  {
      // catch and process errors throw by dp
      // example: output to cerr
      cerr<<str<<endl;
  }
  

  该方法使用二分法加速收敛。

• 设置所需的点数，可接受的点数阈值。

  // dp will find the tolerance corresponding to 100
  // in the approximated curve, with 5 points of possible error.
  try
  {
      dp.Shrink(100,5);
  }
  catch(TCHAR* str)
  {
      // catch and process errors throw by dp
      ...
  }

简化。

这项工作的最简单部分。

try
{
    dp.Simplify();
}
catch(TCHAR* str)
{
    // catch and process errors throw by dp
    ...
}

或者使用 ShrinkNorm, Shrink 方法。

访问近似曲线。

键存储为 PointContainer::const_iterator。您可以使用 GetKeys 访问键容器。

// getting conts reference to keys
const TDPHull<float>::KeyContainer& kc = dp.GetKeys(); 
TDPHull<float>::KeyContainer::const_iterator it; // iterator for keys
for (it = kc.begin(); it != kc.end(); it++)
{
    // it is an const_iterator pointing to a PointContainer::const_iterator
    xi=(*it)->x; 
    yi=(*it)->y;
}

实现自己的算法。

您需要做的就是继承一个类 TLineApproximator 并重写 ComputeKeys 函数。

混合容器。

您可以实现自己的 points 和 keys 容器，只要它们满足要求即可。

x,y 的单独容器。

x,y 存储在单独的容器中，而且这些容器的类型可能不同，这种情况并不少见。为了解决这个问题，编写了两个包装器模板：TPointDoubleContainer 和 TKeyDoubleContainer，它们充当近似算法和容器之间的接口。

CVectorX vX;    // the vector of x coordinates
CVectorY vY;    // the vector of y coordinates

// defining the hydrid container
typedef TPointDoubleContainer<float, CVectorX, 
                   CVectorY> HybridPointContainer; 

// a list of key x coordinates
CListX lKeyX;    
// a vector of key y coordinates, any container
// that has push_back will do the job :)
CVectorY vKeyY;    
// defining the hydrid container
typedef TKeyDoubleContainer<float, CListX, CVectorY> HybridKeyContainer; 

// creating approximator
TDPHull< float, HybridPointContainer, HydridKeyContainer> dp; 
// attaching point containers
dp.GetPoints().SetContainers( &vX, &vY);    
// attaching key containers
dp.GetKeys().SetContainers( &lKeyX, &vKeyY);    
// dp is now ready to work

使用演示

演示展示了使用不同算法对曲线进行实时近似。

• 您可以使用工具栏按钮来停止/开始动画，
• 您可以使用滚动条调整收缩率，
• 您可以使用菜单 File->Load Data Set 加载您自己的数据。文件必须每行包含一个 x,y 对。

在您的项目中进行使用

将以下文件插入您的项目中即可完成。

LineApproximator.h,DPHull.h, PathHull.h

已知问题

• 原始曲线不得自相交。这意味着起点和终点必须不同，不能是闭合曲线！
• 病态数据集和堆栈溢出：已解决。问题是由于递归导致堆栈溢出。现在已解决。

更新历史

• 04-03-2003
  • 通过添加内部函数调用堆栈摆脱了 DP 递归。因此，堆栈溢出问题已解决！！！
  • 将从 Effective STL 学到的东西应用到类中：使用算法、函数对象等。
  • 将 class T 更改为 typename T。
  • 使用 boost::close_at_tolerance 进行更好的浮点数比较。
• 15-11-2002
  • 越来越多的模板化。
  • 检测曲线何时闭合。
  • 混合容器。
  • 修复了 compute limits 中的错误。
  • 添加了大量的 ASSERT，因此 Debug 版本比 Release 版本慢很多。
• 7-11-2002
  • 修复了 SLimits 结构中的一个错误（GetCenterY）。
  • TPathHull 使用迭代器而不是 SPoint* 工作。
  • 添加了异常来处理错误。
  • 修复了 TDPHull::ComputeKeys 中的一个错误。曾使用了 pc.end() 而不是 pc.end()--。
• 6-11-2002
  • 添加了基类 TLineApproximator。
  • 添加了 S.Rog 提出的算法：请参阅 TKeyFramer, TGlobalKeyFramer, TDispKeyFramer, TVectKeyFramer。
  • 更新了演示。
• 3-11-2002
  • 添加了数据归一化以获得更好的数值行为。避免了算法在使用病态数据时崩溃。此问题由 Corey W. 提交。
  • 模板化版本。
  • 放弃了宏，并以更面向对象的方式重写。

参考文献

1. D. H. Douglas and T. K. Peucker. Algorithms for the reduction of the number of points required to represent a line or its caricature. The Canadian Cartographer, 10(2):112--122, 1973。
2. J. Hershberger and J. Snoeyink. Speeding up the Douglas-Peucker line simplification algorithm. In Proc. 5th Intl. Symp. Spatial Data Handling. IGU Commission on GIS, pages 134--143, 1992. (主页)。