作为对线程的扩展和部分回答，我写了一个简单的算法，给定一组点（带有xy坐标）可以形成一个非自相交的多边形。

要求：给定任意一组具有不同坐标的点，始终可以构造规则或不规则，非自相交的多边形。

算法：

假设有一个包含所有顶点的集合V

1）通过x坐标对V中的所有顶点进行排序

2）想象一条平行于x轴的直线（我们称其为“分隔线”），该线从第一个节点开始扩展到无穷大，并将顶点划分/分为两组。

3）现在考虑两组：

A =分隔线以上或分隔线上的所有顶点的集合

B =所有剩余顶点的集合

4）从A的最左侧顶点开始，连接A中的所有顶点，直到到达最右侧

5）如果排序集合V的最右边的顶点（x坐标最大的顶点）不在A中，则将最后一个顶点（A的最右边）与其连接。

6）向后工作，并从已排序集合V的最右边顶点（x坐标最大的顶点）开始，连接B中的所有顶点

7）将B的第一个（B的最左顶点）与A的最左的顶点相连

我认为该算法是正确的，无法找到会失败的测试，但也许我遗漏了一些东西。

如果您可以看一眼，请给我一个示例，如果有的话（我确定一定有）将不起作用，我将不胜感激。