图形简化算法建议需要

Question

我有一个需要采取一个二维图形的n个点，并减少它的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？我会牺牲正确的解决方案的性能。

Answer 1

你可以在Douglas-Peucker简化版here和here上找到我的C++实现和文章。我还提供了Douglas-Peucker简化的修改版本，允许您指定生成的简化线的点数。它使用'彼得泰勒'提到的优先队列。虽然它的速度要慢很多，所以我不知道它是否会满足'是比较快的'的要求。

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

我希望这会有所帮助。

p.s .:我只记得一些事情，你也可以试试Visvalingam-Whyatt算法。总之： -compute与它直接邻居每个点的三角形区域 -sort这些领域 -remove面积最小 点-update其邻国的区域 -resort - 继续直到N个点，仍

Answer 2

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

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