需要的图化简算法建议

Question

我需要获取一个包含n个点的2D图，并将其减少到r个点(其中r是一个小于n的特定数字)。例如，我可能有两个总点数略有不同的数据集，比如1021和1001，我想强制这两个数据集都有1000个点。我知道一些简化算法: Lang简化和Douglas-Peucker。我在之前的一个项目中使用过Lang，但要求略有不同。

我正在寻找的算法的特定属性是：

1)必须保持线条的形状

2)必须允许我将数据集减少到特定数量的点

3)相对较快

这篇文章讨论了不同算法的优点。我将发布第二条消息，以获取关于Java或Groovy实现的建议(为什么要重新发明轮子)。

我关心的是上面的要求2。我不是这些算法的专家，不知道我是否可以指定输出点的确切数量。我使用的Lang的实现将lookAhead、公差和点数组作为输入，所以我不知道如何指定输出中的点数。这是我当前需求的一个关键要求。也许这是由于我们使用的Lang的具体实现，但我在web上没有看到很多关于Lang的信息。或者，我们可以使用Douglas-Peucker，但同样，我不确定是否可以指定输出中的点数。

我应该补充说，我不是这些类型的算法或任何类型的数学专家的专家，所以我正在寻找纯粹的凡人类型的建议:)我如何满足上面的要求1和2？我会牺牲性能来换取正确的解决方案。

Answer 1

您可以在Douglas-Peucker simplification here和here上找到我的C++实现和文章。我还提供了Douglas-Peucker简化的修改版本，它允许您指定所得到的简化直线的点数。它使用了“Peter Taylor”提到的优先级队列。它的速度要慢得多，所以我不知道它是否能满足“相对较快”的要求。

我计划为Lang several (和其他几个)提供一个实现。目前，我没有看到任何简单的方法来调整Lang，以减少到一个固定的点数。如果您可以接受一个不那么严格的要求：“必须允许我将数据集减少到一个近似的点数”，那么您可以使用迭代方法。猜测lookahead的初始值:点数/期望点数。然后慢慢增加前视，直到大致达到所需的点数。

我希望这能帮到你。

附言:我想起来了，你也可以试试Visvalingam-Whyatt算法。简而言之:将每个点的三角形面积与其直接邻域相加，然后将这些区域与具有最小面积的点相加，直到剩余n个点为止。-sort -remove -update -resort -continue

Answer 2

我认为你可以很直接地适应Douglas-Pücker。调整递归算法，使其不是生成一个列表，而是生成一个反映递归调用结构的树。树的根将是单线近似P0- Pn；下一级将表示双线近似值P0- Pm -Pn，其中Pm是P0和Pn之间距离P0-Pn最远的点；下一级(如果已满)将表示四线近似值，依此类推。然后，您可以根据深度或插入点与父线的距离修剪树。

编辑:实际上，如果采用后一种方法，则不需要构建树。相反，您可以填充优先级队列，其中优先级由插入点到父线的距离指定。然后，当您完成时，队列会告诉您要删除哪些点(或保留哪些点，根据优先级的顺序)。