Visvalingam-Whyatt折线简化算法澄清

Question

我正在尝试实现一种折线简化算法。原始文章可以在此处找到: http://archive.is/Tzq2。这个算法的基本思想是:

1. 计算每个点之间的三角形面积，若面积为0则删除该点。
2. 从面积最小的点开始，比较其面积与阈值的大小，如果小于阈值，则将其从折线中删除。
3. 移动到相邻的两个点并重新计算它们的面积。
4. 回到步骤2，直到所有面积都小于阈值的点都被删除。

以下是该算法的伪代码（从文章中复制）:

• 计算每个点的有效面积。 删除所有面积为零的点，并将其存储在单独的列表中。
• REPEAT
  • 找到具有最小有效面积的点并将其称为当前点。如果它的计算面积小于上一个被消除的点的面积，请使用后者的面积。 (这样确保不能删除当前点而未删除先前已删除的点。)
  • 从原始列表中删除当前点，并将其与其关联的面积一起添加到新列表中，以便在运行时对该线进行过滤。
  • 重新计算相邻两个点的有效面积 (参见图1b)。
• UNTIL
  • 原始线路仅由2个点组成，即起点和终点。

我对“REPEAT”下第一步中的“if”子句感到困惑... 有人能解释一下吗？

- Prismatic

---

为什么这句话让我感觉像是《生活大爆炸》的一个剧集标题呢？ - John Dibling

因为你看电视的时间太多了 :) - Prismatic

文章链接已损坏。 - BenjaminGolder

对我来说运行良好。也许是一个间歇性的问题。参考文章标题为“通过重复消除最小区域进行线条概括”，作者为© Visvalingam， M.和Whyatt，J.D。（1992年）。 - Prismatic

以下是有关编程的内容的翻译，仅返回翻译后的文本：文章链接（此处和其他地方发布的一些链接已失效）：http://archive.is/Tzq2 - Kit

Answer 1

值得一提的是，d3.js 的创作者 Mike Bostock 写了一个紧凑的 JavaScript 实现这个算法（维斯瓦林汉姆算法）。

• 源代码
• 演示
• Hacker News 上的讨论

- Herb Caudill

---

这段代码中三角形面积计算有一个bug，应该改为：function area(t) { return Math.abs((t[0][0] - t[1][0]) * (t[2][1] - t[1][1]) - (t[0][1] - t[1][1]) * (t[2][0] - t[1][0])); }。这会导致海岸线的错误简化（显示的结果比实际更糟糕）。此外，由于它是迭代的，所以最大面积节省在这个实现中是无用的。 - xryl669

提议的表达式是一个常数零，因为它从自身中减去了 (t[0][0] - t[1][0]) * (t[2][1] - t[1][1])。 - user368683

Answer 2

该算法的本质是通过排名点的重要性来评估。点的重要性由其有效面积近似计算。

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

if子句的目的是确保在最终列表中点B比点A更重要，就这样。

- n. m.

---

这很有道理。通过使B比A更重要，您确保在最后正确地过滤出点。 - Prismatic

Answer 3

我也曾经感到困惑，回去重新阅读了文章，据我所知，如果您在进行一次性简化并使用固定面积阈值，则不需要它。据我所知，javascript实现的方式就是这样，因此它实际上不需要'if'语句（但是它仍然有，哎）。如果您要保留所有点，则需要'if'语句。在这种情况下，您将每个点的“有效面积”存储在其中，以便稍后可以过滤它们，可能使用交互式滑块来控制输出点的数量。通过存储较大的有效面积，您可以保留正确的顺序。

- John Alex