algorithm - Visvalingam-Whyatt 折线简化算法说明

Question

我正在尝试实现折线简化算法。原始文章可以在这里找到：http: //archive.is/Tzq2。它在概念上似乎很简单，但我不理解提供的示例算法（我认为它措辞不佳）伪代码，并希望有人能提供一些见解。从文章中，我了解到基本思想是

1. 计算每个点的有效面积（由一条线上三个连续点之间的三角形组成）并删除面积为0的
2. 从最小的区域开始，将该点的区域与阈值进行比较，如果该区域低于该阈值，则将其从折线中删除。
3. 移动到两个相邻的点并在它们发生变化时重新计算它们的面积
4. 回到 2，直到阈值以下的所有点区域都被移除

算法如下（从文章中逐字复制）：

• 计算每个点的有效面积 删除所有面积为零的点，并将它们存储在具有该面积的单独列表中
• 重复
  • 找到有效面积最小的点并将其称为当前点。如果其计算的面积小于最后一个要消除的点的面积，则改用后者的面积。（这样可以确保在不消除先前消除的点的情况下无法消除当前点。）
  • 从原始列表中删除当前点并将其与相关区域一起添加到新列表中，以便可以在运行时过滤该行。
  • 重新计算两个相邻点的有效面积（见图 1b）。
• 直到
  • 原线只包含2个点，即起点和终点。

我对“重复”下第一步中的“if”子句感到困惑……有人能澄清一下吗？

Answer 1

FWIW Mike Bostock 是 d3.js 的创建者，他为这个算法（Visvalingam's Algorithm）编写了一个紧凑的 JavaScript 实现。

• 源代码
• 演示
• 黑客新闻讨论

Answer 2

该算法的本质是按重要性对点进行排名。该点的意义近似于其有效面积。

假设您已经消除了 A 点，然后重新计算了 B 点的有效面积。新的面积可以大于或小于旧的面积。它可以小于 A 的有效区域。但是，该算法仍然认为 B 比 A 更重要。

该if子句的目的是确保 B 点在最终列表中比 A 点更重要，仅此而已。

Answer 3

我也对此感到困惑，回去再次阅读这篇文章，并且如果您在进行过程中删除点，则不需要它- 也就是如果您正在使用固定区域阈值进行一次性简化。afaict javascript 实现以这种方式工作，因此它实际上不需要“if”语句（但它无论如何都有它，哦，好吧）。

如果您要保留所有要点，则需要“if”语句。在这种情况下，您将存储每个点的“有效区域”，以便稍后您可以过滤它们，也许使用控制输出点数的交互式滑块。通过存储更大的有效区域，您可以保持正确的顺序。