5

我一直在网上寻找一种算法，该算法使您能够创建 2D 多边形的细节层次 (LOD) 表示，但找不到任何合适的参考。也许我使用了错误的搜索词，但所有搜索结果都是针对 3D LOD 算法的，我猜这不能（？）真正应用于 2D。

我敢肯定，在 3D 图形的冲击之前，很多人会研究 2D LOD 算法。任何线索或指示我可以在哪里获得更多信息？谢谢！

4

2 回答 2

4

除了从多边形中获取每个第 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) 的中点与可能简化的线段 ([Pi, Pi+2]) 之间的最小距离，而不是角度

编辑：

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

  1. 将原始多边形顶点视为 Catmull-Rom 样条的控制点
  2. 将此样条线细分为所需的点数

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

于 2010-12-16T13:14:39.113 回答
4

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

于 2010-12-16T14:00:39.223 回答