多折线和多边形简化算法

Question

我们有一些折线（点的列表，具有起始和结束点，不是循环的）和多边形（点的列表，循环的，没有所谓的端点）。

我们希望将每条折线映射到一条新的折线，每个多边形映射到一个新的多边形，以使总边数足够小。

假设原始边数为N，我们希望结果边数为M。 N远大于M。

折线需要保留它们的起始点和结束点，因此它们至少贡献1条边，比它们的顶点数少1。多边形仍然需要是多边形，因此它们至少贡献3条边，等于它们的顶点数。 M将至少足够满足此要求。

输出应尽可能接近输入。这将成为最小化某些度量以在真正的最优解的某些小容差内的优化问题。最初我将使用原始和结果的对称差异的面积（面积之间），但如果其他指标更易于完成，则愿意接受替代方案。

如果结果只包括原始顶点，则可以。适合会稍微差一些，但为了保持时间复杂性，可能是必要的。

由于我正在寻求算法，因此还可以看到实现。我可能需要为将要使用它的地方重新实现它，因此诸如语言或数据结构之类的细节不太重要。

至于近似度需要多好，大约可以从位图图像获取矢量图像。这里的实际用途是游戏工具，有一些特定游戏的奇怪细节，因此输出边数是固定的而不是容差。

很难找到这种事情的任何信息，因此即使没有提供完整的可行算法，一些指针也将非常感激。

- user4159038

---

折线简化算法 - user3386109

Answer 1

拉默-道格拉斯-派克算法（在评论中提到）确实很好，但它有一些缺点：

• 它需要输入开放式折线，对于封闭的多边形，必须修复任意点，这会降低最终质量或者强制测试许多点并降低性能。
• 简化折线的顶点是原始折线顶点的子集，其他选项未被考虑。这允许非常快速的实现，但再次降低了简化折线的精度。

另一种选择是采用众所周知的三角网格简化算法 使用二次误差度量进行表面简化 并将其适应于折线：

• 替换三角形平面上的距离为折线段所在直线的距离，
• 如果折线是二维的，则二次形式失去一个维度。

但是保留了大部分算法，包括根据预估的扭曲程度收缩折线的边缘收缩队列（最小堆）。

以下是这个算法应用的一个例子：

红色-原始折线，蓝色-简化折线，可以看到所有顶点都不在原始折线上，但是尽可能保留了一般形状，只用了很少的线段。

如果能看到实现就好了。

可以在MeshLib中找到实现，参见MRPolylineDecimate.h/.cpp。

- Fedor