给定一个点矢量(可能是乱序),找到多边形(不是凸包)

Question

我目前有一个点矢量

vector<Point> corners;

我以前存储过给定多边形的角点.鉴于此,我确信这些点形成了一个不包含任何自相交边的简单多边形.但是,在存储这些顶点的过程中,不保留它们彼此连接的顺序.

我现在有一个函数,给定一个点矢量,连接它们并绘制一个封闭的数字.但是,我需要按照需要连接的顺序给这个函数一系列点.任何人都可以提出一种方法,我可以按正确的顺序对这些点进行排序吗？它们形成一个非常简单的凹多边形,而不是凸包.在所有(7)点中找到中心点的算法也会有帮助:)

Answer 1

凹多边形没有唯一的解决方案:

凸多边形可以作为点的凸包发现不均匀(如果你知道这些点构建一个凸多边形).

Answer 2

一组给定的点通常可以通过多种方式连接以形成非自相交的多边形.除非您有关于点可能代表的多边形种类的更多信息,否则您可能会失败.

Answer 3

1.启发式确定形状

没有独特的解决方案,因此没有简单的算法.你可以尝试以某种方式模仿你的直觉.

• 从随机点开始,将每个点连接到最近的邻居.然后将最后一个点连接到第一个点.
• 首先选择一个点及其最近的邻居,然后用一条线连接它们.现在迭代地添加另一个点.始终选择最小化最后一个线段与新添加的线段之间角度的点.

这两种方法一般都不起作用,它们甚至不能保证避免交叉.您可以尝试通过回溯来解决这个问题,如果您发现了明显的错误(例如交叉路口),那么回溯到最后的决策点并采取"第二好"的方法,....

但是,由于解决方案不是唯一的,所以不要期望从这些启发式方法中获得太多.

2.顶点的平均值

顶点的平均点很容易计算.只需将所有点加在一起,然后除以刚刚添加的点数,这就是平均值.你可能更感兴趣的是"质心"意义上的中心点,见下文.

3.中心点

要确定质心,首先必须定义形状.这意味着你必须做类似第1步的事情.

给定多边形计算中心点的一种简单实现的方法是.

• 在多边形周围放置一个边界框.
• 在边界框内随机生成点.
• 对于每个点确定它是否在边界框内,如果没有,则将其丢弃.要确定某个点是否在任意多边形内,请使用光线测试.
• 对于您保留的所有点,应用方法2.这些点的平均点是对中心点的良好近似.