如何在非凸多边形中排序顶点(如何找到许多解中的一个)

Question

我有同样的问题:如何在一个简单的非凸多边形中排序顶点, 但没有我可以使用的解决方案.

我有点的坐标,需要找到一些多边形.对于一个点列表有更多解决方案并不重要.我需要一些算法来找到其中一个.无论哪一个.我真的不知道如何解决这个问题.

(我在数组中存储坐标,我想在Javascript中使用一些算法)

非常感谢.

Answer 1

首先,找到包含所有顶点的边界框的中心.我们将这一点称为C.

根据每个点相对于C的角度对顶点列表进行排序.您可以使用它来查找角度.如果两个或多个顶点具有相同的角度,则应该首先接近C的顶点.atan2(point.y - C.y, point.x - C.x)

然后,按照它们在列表中出现的顺序绘制您的点.你将得到一个非交叉的星爆图案,可能是非凸的.例: