geometry - 具有来自一组点的顶点的多边形

Question

我如何从给定的点集制作多边形。

可能的多边形：

无效的多边形：

多边形不能自相交。

我一直在考虑根据一个点对点进行排序，但它似乎对某些情况无效。谢谢。

Answer 1

可能是这样：

1. 找到给定点的凸包 H
2. 对于不在船体中的每个点P，找到船体最近的边HiHi+1，并将其替换为边HiP和PHi+1。
3. 如果两个点具有相同的最近边，则将它们连接起来