最小化多边形顶点

什么是一个很好的算法来减少多边形中的顶点数量而不改变它看起来非常多的方式？

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

输出:具有少得多的顶点的多边形,看起来仍然像原始的一样:例如可用于碰撞检测的东西(不一定是凸起的).

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

Edit2:道格拉斯Peucker算法是我真正想要的.

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

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

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

实际上，您可能只是将多边形中的所有顶点用作“点云”，然后计算围绕它的凹壳。我将寻找算法链接。最糟糕的情况是完全凸出的多边形。

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

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

这篇文章有一些关于凸包的细节。