Visvalingam-Whyatt折线简化算法澄清

Question

我正在尝试实现折线简化算法.原始文章可以在这里找到:http://archive.is/Tzq2.这似乎在概念简单,但我不明白的样本算法(我认为这是措辞很差)伪提供,希望有人能提供一些见解.从文章中我收集到的基本想法是

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

算法如下(从文章中逐字复制):

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

我对'REPEAT'下第一步中的'if'条款感到困惑......任何人都可以澄清一下吗？

Answer 1

FWIW d3.js的创建者Mike Bostock写了一个紧凑的javascript实现这个算法(Visvalingam的算法).

• 源代码
• 演示
• 浅谈黑客新闻

Answer 2

算法的本质是按重要性对点进行排序.该点的重要性由其有效面积近似.

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

该if条款的目的是确保B点在最终列表中比A更重要,这就是全部.