作为对我的线程的扩展和部分回答,我编写了一个简单的算法,给定一组点(带有 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的最左边的顶点
我认为该算法是正确的,找不到会失败的测试,但也许我遗漏了一些东西。
如果您能看一下并给我一个示例,如果有的话,我将不胜感激(我确信必须有)。