algorithm - 创建通过所有给定点的凹多边形

Question

给定一组点，我想使用这些点创建一个凹面不相交的多边形。凸包会否定凹入部分，而通过 x/y 坐标或从中心的角度排列它们会产生尖刺的伪像。有没有一种简单的方法可以做到这一点？

我要创建的多边形类型的示例：

Answer 1

如果您只有周界顶点并且可以保证周界顶点之间的距离将小于周界边缘之间的距离，那么您可以使用最小生成树。

上面的示例显示了 MST 的工作位置（连接结果折线中的第一个和最后一个顶点）

下面的例子是如果周边的边缘太靠近会发生什么。