algorithm - 需要图形简化算法建议

Question

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

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

1) 必须保持线条的形状

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

3)比较快

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

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

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

Answer 1

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

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