我得到了一堆 2d 点。我试图找到的是一个特定点周围的最小多边形(由完全包围的最小点集创建)。我尝试使用凸包和 Voronoi,但它们都没有产生我正在寻找的结果,而且我已经没有想法了......
我想要找到的是代表点(绿色)周围最小凸多边形的线(红色),如下图所示:
另一个例子:
任何代码、建议或已知算法将不胜感激......
最佳答案
从图中的任意黑点开始,我们将其称为 A。从 A 点到绿点 G 绘制直线。现在从 A 点到任何其他点 A1、A2、... 绘制直线。如果从顺时针方向看,这条线位于 AG 线之后,则忽略它。从所有其他直线中选择与直线 AG 形成最小角度的直线。现在将点 A 移动到下一个点。重复此操作,直到您第二次访问某个点。
关于c++ - 围绕点的最小凸多边形,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51079218/