二维细节水平（LOD）算法

Question

我一直在网络上寻找一种算法，使您能够创建2D多边形的细节层次（LOD）表示，但无法找到任何像样的参考。也许我使用了错误的搜索词，但是所有的搜索结果都是用于3D LOD算法的，我猜，它们不能（？）真的应用在2D中。

我相信在3D图形的冲击之前，很多人都会在2D LOD算法上工作。任何线索或指向我可以获取更多信息的地方？谢谢！

Answer 1

除了明显的dumbest算法，它将从多边形中获取每个第N个顶点（减少顶点数N），这里有一个灵感来自于某些3D算法的想法。

通常，在3D中，需要去除对整体体积贡献较小的面。为此，我们尝试简化模型的“最平坦”区域。段Si与Si + 1之间

1. 计算各个角度：

   现在，在2D，你可以把这种以“简化它们之间的最小角度片段的第一天真的实现可能。多边形

2. 取所有低于给定阈值的角度（或取最小的M个角度）
3. 简化我们在2中识别的片段（替换[Pi，Pi + 1]和[Pi + 1，Pi + 2 ] by [Pi，Pi + 2]）
4. 从1开始重复，直到我们已经充分减少了polyg

当然，这不是最优的，但它应该是质量和速度之间的良好交易。取而代之的是角的，可采取两个段（PI + 1）的中间点和潜在地简化段之间的最小距离（[P1，P1 + 2]）

编辑：

另一种算法予会尝试，如果我不需要太多的性能：

1. 考虑原来的多边形顶点作为的Catmull-Rom样条
2. Tesselate这个样点处的所需数量的控制点

最后，我发现了一些源代码，您链接：http://motiondraw.com/md/as_samples/t/LineGeneralization/demo.html，以及相关的算法：http://www.geom.unimelb.edu.au/gisweb/LGmodule/LGSimplification.htm

Answer 2

为Douglas-Peucker algorithm搜索是用来简化折线，而是可以扩展到支持多边形。这是我用过的。如果你需要的话，还有拓扑稳定的扩展。