顺时针(逆)排序CONCAVE多边形顶点？

Question

我有一组无序顶点,可能形成一个凹多边形.现在我希望顺时针或逆时针订购它们.

这里的答案表明以下步骤:

• 找到多边形中心
• 计算角度
• 按角度订购点数

这显然仅适用于凸多边形,并且当这些点形成凹面时会失败.

我怎么能这样做呢？

我正在使用Python,但欢迎所有通用答案.

Answer 1

一般来说,你的问题似乎不明确.例如,给定以下顶点集:

 

您认为哪些非凸多边形是连接它们的"正确"方法？

     

现在,很明显,您可以使用各种可能的标准来选择不同的可能订单.例如,您可能希望选择最小化边长度的排序,如果这些点实际上在简单多边形的边界上彼此非常接近,则应产生相当"合理"的结果:

 

不幸的是,对于一组通用点,找到最小化总边长的排序结果是众所周知的NP完全问题.这就是说,有很多的启发式算法,可通常找到一个几乎快最佳的解决方案,即使他们不能总是保证他们找到的解决方案是真正的最小值.