c++ - 多边形顶点减少库保持几乎相同的形状

Question

我正在使用多边形裁剪库Clipper的 c++ 版本，我想减少多边形中的顶点数量，保持几乎相同的形状。

作为附加要求，我必须“仅向外”近似我的多边形：生成的简化多边形必须与原始多边形一致。

我想过：

• 凸包，它满足“仅向外”的条件，但它过于简化了我的多边形
• Ramer-Douglas-Peucker 算法，这很好，因为它让我选择错误但它不满足“仅向外”条件。

然后我看了一下psimpl 库，最接近我要求的算法似乎是Opheneim 算法，它

使用最小和最大距离容差来约束搜索区域

但最小距离不能为 0。

这个问题有什么可能的解决方案吗？你知道任何解决它的 c++ 库吗？

Answer 1

您可以尝试围绕多边形进行迭代并执行以下操作：

1. 如果顶点是凹的并且到线的距离，连接相邻顶点 < tolerance，则将其删除。

2. 如果顶点是凸的，则考虑前一段位于 line 上L1，进一步迭代，同时L1与包含下一段的线相交，在P多边形外的点和P到多边形 <tolerance的距离，以及段的起点到L1<的距离tolerance。当该迭代停止时（不是在第一次迭代时），删除中间点，插入交点（如果当前在多边形内，则为上一个，如果在边界上，则为当前）。

继续迭代多边形，同时进行简化。还要确保保留旧点以检查容差（例如，您可以枚举顶点，并在简化时删除索引，但在检查容差时，也要检查中间索引）

它不是超快速算法，但可以满足您的需求。