2D细节层次(LOD)算法

Question

我一直在网上寻找一种算法,它可以让你创建2D多边形的细节层次(LOD)表示,但我找不到任何合适的参考.也许我使用的是错误的搜索词,但所有的搜索结果都是针对3D LOD算法的,我猜,这些算法不能(？)真正应用于2D.

我相信在3D图形的冲击之前,许多人会研究2D LOD算法.有什么线索或指示我可以获得更多信息吗？谢谢!

Answer 1

除了明显最愚蠢的算法（即从多边形中取出第 N 个顶点（将顶点数量减少 N））之外，这里还有一个受某些 3D 算法启发的想法。

\n\n

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

\n\n

现在在 2D 中，您可以将其翻译为“简化它们之间具有最小角度的线段。第一个 na\xc3\xafve 实现可能是：

\n\n

\n
1. 计算多边形的线段 Si 和 Si+1 之间的所有角度
\n
2. 取低于给定阈值的所有角度（或取 M 个最小角度）
\n
3. 简化我们在 2 中确定的段。（将 [Pi, Pi+1] 和 [Pi+1, Pi+2] 替换为 [Pi, Pi+2]）
\n
4. 从 1 开始重复，直到我们充分缩小了多边形
\n

\n\n

当然，这不是最优的，但它应该是质量和速度之间的良好权衡。您可以取两个线段的中点 (Pi+1) 和可能简化的线段 ([Pi, Pi+2]) 之间的最小距离，而不是角度

\n\n

编辑：

\n\n

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

\n\n

\n
1. 将原始多边形顶点视为 Catmull-Rom 样条线的控制点
\n
2. 在所需的点数处对该样条进行细分
\n

\n\n

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

\n