3

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

我正在寻找的算法的具体属性是：

1) 必须保持线条的形状

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

3）相对较快

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

我担心上面的要求 2。我不是这些算法的专家，不知道我是否可以指定输出点的确切数量。我使用的 Lang 的实现将 lookAhead、tolerance 和 Points 数组作为输入，所以我看不到如何规定输出中的点数。这是我当前需求的关键要求。可能是因为我们之前使用过Lang的具体实现，但是我在网上没有看到很多关于Lang的资料。或者，我们可以使用 Douglas-Peucker，但我再次不确定是否可以指定输出中的点数。

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

4

2 回答 2

2

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

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

于 2011-02-05T13:00:59.103 回答
1

你可以在这里和这里找到我的 C++ 实现和关于 Douglas-Peucker 简化的文章。我还提供了 Douglas-Peucker 简化的修改版本，它允许您指定生成的简化线的点数。它使用“Peter Taylor”提到的优先级队列。它虽然慢了很多，所以我不知道它是否能满足“相对较快”的要求。

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

我希望这有帮助。

ps：我刚刚记起来了，你也可以试试 Visvalingam-Whyatt 算法。简而言之： - 计算每个点及其直接邻居的三角形面积 - 对这些区域进行排序 - 删除面积最小的点 - 更新其邻居的面积 - 重新排序 - 继续直到剩下 n 个点

于 2011-02-07T16:12:14.397 回答