python - 以(逆时针)顺序排列凹面多边形顶点？

Question

我有一组可能形成凹多边形的无序顶点。现在我想按顺时针或逆时针顺序排列它们。

An answer here建议执行以下步骤:

• 找到多边形中心
• 计算角度
• 按角度排序点

这显然只适用于凸多边形，当点形成凹多边形时会失败。

我怎样才能对凹面做这个？

我正在使用 Python，但欢迎所有通用答案。

Answer 1

一般来说，您的问题似乎不明确。例如，给定以下一组顶点:

您认为这些非凸多边形中的哪一个是连接它们的“正确”方式？

现在，显然，您可以使用各种可能的标准在不同的可能订单之间进行选择。例如，您可能希望选择最小化边的总长度 的顺序，如果这些点实际上在简单多边形的边界:

不幸的是，对于一组一般的点，找到最小化总边长的排序结果是 a well known NP-complete problem .也就是说，有很多 heuristic algorithms可以通常快速找到一个接近的最佳解决方案，即使他们不能始终保证他们找到的解决方案是真正的最小值。