algorithm - 按顺时针顺序排列四个点

Question

数组中的四个二维点。我需要按顺时针顺序对它们进行排序。我认为这可以通过一次交换操作来完成，但我还没有能够正式地把它写下来。

编辑:在我的例子中，这四个点是一个凸多边形。

编辑:这四个点是凸多边形的顶点。它们不需要按顺序排列。

Answer 1

如果想从更数学的角度来看，我们可以考虑4个点的排列

在我们的例子中，有 4 个顺时针排列的排列

A B C D
B C D A
C D A B
D A B C

所有其他可能的排列都可以通过 0 或 1 次交换转换为这些形式之一。 (我只会考虑以 A 开头的排列，因为它是对称的)

1. A B C D - 完成
2. A B D C - 交换 C 和 D
3. A C B D - 交换 B 和 C
4. A C D B - 交换 A 和 B
5. A D B C - 交换 A 和 D
6. A D C B - 交换 B 和 D

因此只需要一次交换 - 但可能需要一些工作来确定是哪一个。

看前三点，再看ABC带符号区的符号，就可以判断是不是顺时针了。如果它们是顺时针的，那么我们就是 1 2 或 5

为了区分这些情况，我们必须检查另外两个三角形 - 如果 ACD 是顺时针的，那么我们可以将其缩小到情况 1，否则我们必须是情况 2 或 5。

要在情况 2 和情况 5 之间进行选择，我们可以测试 ABD

我们可以类似地检查 ABC 逆时针的情况。

在最坏的情况下，我们必须测试 3 个三角形。

如果您的点不是凸点，您会找到内部点，对其余点进行排序，然后将其添加到任何边缘。请注意，如果四边形是凸的，则 4 个点不再唯一确定四边形，有 3 个同样有效的四边形。