什么是一种好的算法，可以在不显著改变多边形外观的情况下减少其顶点数量？
输入：表示为点列表的多边形，其具有过多的顶点，例如来自鼠标的原始输入。
输出：具有远少于原始多边形顶点数量的多边形，但仍然非常类似于原始多边形：例如适用于碰撞检测（不一定是凸多边形）。
编辑：解决方案类似于在图形上找到最佳的多线段拟合线。它在我的算法书中被称为分段最小二乘法。
编辑2：我真正想要的是 Douglas Peucker 算法。
2个回答
7
编辑：看看这个，简化多边形
你提到了碰撞检测。你可以非常简单地计算一个包围凸多边形。如果你关心凹多边形区域，你可以通过取多边形质心并选择一个起点来计算一个凹多边形。从起始点开始绕质心旋转，找到每个你想保留的顶点，并将其分配为包围壳中的下一个顶点。算法的复杂度将取决于您如何确定要保留哪些顶点，但我相信您已经考虑过这一点。您可以根据它们相对于质心的位置将所有顶点放入桶中。当一个桶装满了超过一个任意数量的顶点时，您可以将其拆分。然后，取该桶中顶点的平均值作为用于包围壳的顶点。或者，忘记桶，当您在质心周围移动时，只有在距离上一个点足够远时才选择一个点。
实际上，您可能只需使用多边形中的所有顶点作为“点云”，并计算其周围的凹多边形。最坏情况是完全凸多边形。
另一个选择是从一个包围矩形开始。对于矩形上的每个顶点，找到点到多边形的距离。对于最远的顶点，将其分成两个更多的顶点，并将它们向内移动一些。重复此过程，直到满足某些比例的顶点或面积。我需要再仔细考虑一下这个方法的细节。
如果您关心多边形实际上看起来相似，即使在自相交多边形的情况下，那么需要另一种方法，但是听起来您只是问了碰撞检测。
这篇帖子详细介绍了凸壳部分。
- John Ellinwood
1
如果需要进行碰撞检测，我可以使用cgal.org上的算法将我的多边形分解为凸组件。抱歉造成了困扰。 - Nick Retallack
1
有很多相关资料可以查阅。只需在谷歌上搜索“网格简化”、“网格优化”等关键词即可。
- Adam Rosenfield
2
大多数这些网格算法都期望许多三角形。我只是试图减少单个多边形中的顶点数。 - Nick Retallack
如果你的多边形不是由三角网格表示的，难道你不能将其转换为一个网格并使用任何提到的算法吗？ - Joe
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接