graphics - 最小化多边形顶点

Question

什么是减少多边形顶点数量而不改变多边形外观的好算法？

输入：一个多边形，表示为一个点列表，具有太多顶点：例如，来自鼠标的原始输入。

输出：一个顶点少得多的多边形，看起来仍然很像原始多边​​形：例如，可用于碰撞检测的多边形（不一定是凸的）。

编辑：对此的解决方案类似于在图表上找到最佳拟合的多段线。在我的算法书中，它被称为分段最小二乘法。

Edit2：Douglas Peucker 算法是我真正想要的。

Answer 1

编辑：哦，看，简化多边形

你提到了碰撞检测。您可以非常简单地计算围绕它的边界凸包。

如果您关心凹面区域，您可以通过获取多边形的质心并选择一个开始点来计算凹壳。从起点围绕质心旋转，找到要保留的每个顶点，并将其指定为边界外壳中的下一个顶点。算法的复杂性在于您如何确定要保留哪些顶点，但我相信您已经想到了这一点。您可以根据它们相对于质心的位置将所有顶点放入存储桶中。当一个桶的顶点数超过任意数量时，您可以拆分它。然后将该桶中顶点的平均值作为要在边界外壳中使用的顶点。或者，忘记水桶，当你在质心周围移动时，只有当它与最后一个点的距离超过给定距离时才选择一个点。

实际上，您可能只使用多边形中的所有顶点作为“点云”并计算围绕它的凹壳。我会寻找算法链接。最坏的情况是完全凸多边形。

另一种选择是从边界矩形开始。对于矩形上的每个顶点，找到该点到多边形的距离。对于最远的顶点，将其拆分为另外两个顶点并将它们移动一些。重复直到满足一定比例的顶点或区域。我得再考虑一下这个细节。

如果您关心实际上看起来相似的多边形，即使在自相交多边形的情况下，也需要另一种方法，但听起来没有必要，因为您询问了碰撞检测。

This post has some details about the convex hull part.

Answer 2

那里有很多材料。只需谷歌搜索“网格减少”、“网格简化”、“网格优化”等内容。