graphics - 最小化多边形顶点

Question

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

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

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

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

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

Answer 1

编辑:哦，看，Simplifying Polygons

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

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

实际上，您可能只是将多边形中的所有顶点用作“点云”并计算其周围的凹 shell 。我会寻找一个算法链接。最坏的情况是完全凸多边形。

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

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

此 post有一些关于凸包部分的细节。