创建非自相交多边形的算法的有效性
作为对线程的扩展和部分回答，我写了一个简单的算法，给定一组点（带有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的最左的顶点相连
我认为该算法是正确的，无法找到会失败的测试，但也许我遗漏了一些东西。
如果您可以看一眼，请给我一个示例，如果有的话（我确定一定有）将不起作用，我将不胜感激。
回答：
我不确定我是否正确理解您要做什么。在另一个线程中，以及在math.SE的相应线程中（这把我带到了这里），您说您有一个多边形，并试图找到其重心。在这里，您说您有一组点，并且想要从中构造一个不相交的多边形。那是两个截然不同的事情。正如我在math.SE上提到的那样，如果不知道多边形是凸的，那么一组点就不会唯一地定义多边形-
因此，您在此处提出的算法可能会构造一些任意的非自相交多边形（我没有不会检查它是否成功完成了该操作），但可能与您最初感兴趣的多边形没有任何关系。或者我是否在Math.SE上误解了您的问题，而您实际上只有一些观点并且只想构建任何一个它们之间的非自相交多边形，不关心可能有几个不等价的解决方案吗？
以上是 创建非自相交多边形的算法的有效性 的全部内容， 来源链接： utcz.com/qa/414287.html
