2D细节层次（LOD）算法

Question

我一直在搜索可以创建二维多边形的细节层次（LOD）表示的算法，但是找不到任何好的参考资料。也许我使用了错误的搜索词，但是所有的搜索结果都是针对三维细节层次算法的，我猜想这些算法不能够真正地应用于二维情况。

我相信，在三维图形出现之前，许多人都在研究二维细节层次算法。是否有任何线索或指向更多信息的方向？谢谢！

- tathagata

---

有趣的是，也许正在寻找形状简化、图像抽象甚至压缩？LOD的要求是什么？例如，图像会被缩小吗？是为了提高性能，节省内存还是模拟深度？ - Julian Young

我正在尝试提高现有（遗留）算法的性能。本质上，我希望得到一个合理的“收缩包装”多边形近似，其中保留了主要的外部特征，并将内部细节隐藏起来。建议关键词加一分。谢谢！ 关键词： 性能、算法、多边形、收缩包装。 - tathagata

Answer 1

除了一个最显然的愚蠢算法，即从多边形中取每第N个顶点（将顶点数量减少N），这里有一个受到一些3D算法启发的想法。通常，在3D中需要移除对整体积分贡献较小的面。为此，我们试图简化模型的“最平坦”区域。现在在2D中，您可以将其转化为“简化它们之间角度最小的段。首先天真的实现可能是：1.计算多边形的线段Si和Si+1之间的所有角度。2.取所有小于给定阈值的角度（或取M个最小角度）。3.简化我们在2中确定的线段。（用[Pi，Pi+1]和[Pi+1，Pi+2]替换[Pi，Pi+2]）4.从1重复。直到我们足够减少我们的多边形。当然，这不是最优的，但应该是质量和速度之间的良好权衡。您可以采用两个线段（Pi+1）的中点和潜在简化线段之间的最小距离而不是角度。编辑：如果我不需要太高的性能，则尝试的另一个算法是：1.将原始多边形顶点视为Catmull-Rom样条的控制点。2.在所需的点数处对此样条进行曲面细分。最后，我在http://motiondraw.com/md/as_samples/t/LineGeneralization/demo.html上为您找到了一些源代码，以及相关算法：http://www.geom.unimelb.edu.au/gisweb/LGmodule/LGSimplification.htm。

- Vincent Mimoun-Prat

---

感谢您的建议。我认为我可以结合您建议的算法和Juraj上面提出的算法来实现我想要的东西。+1。不幸的是，我不能将两个答案都标记为正确，所以我将这个标记为正确，但Juraj提出的“道格拉斯-普克算法”同样好。 - tathagata

是的，我之前不知道Ram Douglas Peucker算法，但我很喜欢它。它的好处在于，例如你可以轻松地在达到最大点数时停止。 - Vincent Mimoun-Prat

Answer 2

搜索Douglas-Peucker算法，该算法用于简化折线，但可以扩展以支持多边形。 这是我使用的算法。 如果需要，还可以使用拓扑稳定性扩展。

- Juraj Blaho

---

+1 让我知道这个酷算法。这可能有效，但我必须在我的上下文中检查它。这是我在问题中忘记提到的一件事，但我不知道如何用言语准确解释，可见我上面对主要问题的评论。 - tathagata