如何按照（逆）时针方向排序凹多边形的顶点？

Question

8

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

这里的答案建议以下步骤：

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

如何对凹多边形进行排序？

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

- Sibbs Gambling

在寻找一种算法来找到一组点的“凹壳”时，你找到了什么？一旦你有了这些点，围绕它们走应该是编程上很简单的事情。 - High Performance Mark

@HighPerformanceMark 我想你指的是alpha shape。是的，我已经研究过它，但在这里遇到了一个未解决的问题，因此无法继续进行。 - Sibbs Gambling

1

我认为在讨论一般凹多边形的顶点时，顺时针和逆时针顺序没有任何意义。 - martineau

但是为了使点在多边形算法射线投射法起作用，必须首先对顶点进行排序，然后再执行它。我实际上也有同感，但如果它们只是无序的，我不知道该怎么办。你能给些建议吗？ - Sibbs Gambling

1

这些点可以按多种方式排序，每种方式都可以创建不同类型的有效多边形（包括具有自相交边的多边形）。例如，我可以想到另一种排序方式是选择最近的相邻点。这可以进一步限制为最近的不穿过现有边的点。这可能会变得非常缓慢，就像尝试解决旅行商最短路径问题一样。 - martineau

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ilmari Karonen · Accepted Answer

总的来说，您的问题似乎定义不清。例如，给定以下顶点集合：

Four points on the plane in a non-convex arrangement

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

Polygon ABCD Polygon ACDB Polygon ACBD

显然，你可以使用各种可能的标准来选择不同的顺序。例如，你可能想选择使边的总长度最小的排序方式，如果点实际上相对靠近简单多边形的边界，则应该得到相当“合理”的结果：

Simple non-convex polygon with many vertices

很遗憾，对于一般的点集来说，找到使总边长最小的排序方式是一个众所周知的NP完全问题。尽管如此，有许多启发式算法可以快速地通常找到几乎最优解，即使它们不能保证找到的解是真正的最小值。