按顺时针顺序对四个点进行排序 [英] Sort Four Points in Clockwise Order
问题描述
数组中的四个二维点.我需要按顺时针顺序对它们进行排序.我认为只需一次交换操作即可完成，但我无法正式放下.
Four 2D points in an array. I need to sort them in clockwise order. I think it can be done with just one swap operation but I have not been able to put this down formally.
在我的例子中，这四个点是一个凸多边形.
四个点是凸多边形的顶点.它们不需要按顺序排列.
The four points are the vertices of a convex polygon. They need not be in order.
推荐答案
如果你想从更数学的角度来看，我们可以考虑4点的排列
If you want to take a more mathematical perspective, we can consider the permutations of 4 points
在我们的例子中，有 4 个按顺时针顺序排列的排列
In our case there are 4 permutations that are in clockwise order
A B C D
B C D A
C D A B
D A B C
所有其他可能的排列都可以通过 0 或 1 次交换转换为这些形式之一.(我只会考虑以 A 开头的排列，因为它是对称的)
All other possible permutations can be converted to one of these forms with 0 or 1 swaps. (I will only consider permutations starting with A, as it is symmetrical)
- A B C D - 完成
- A B D C - 交换 C 和 D
- A C B D - 交换 B 和 C
- A C D B - 交换 A 和 B
- A D B C - 交换 A 和 D
- A D C B - 交换 B 和 D
因此只需要一次交换 - 但可能需要一些工作才能确定哪个.
Thus only one swap is ever needed - but it may take some work to identify which.
通过查看前三个点，并检查ABC有符号区域的符号，我们可以确定它们是否顺时针.如果它们是顺时针的，那么我们就是 1 2 或 5
By looking at the first three points, and checking the sign of the signed area of ABC, we can determine whether they are clockwise or not. If they are clockwise then we are in case 1 2 or 5
为了区分这些情况，我们必须检查另外两个三角形 - 如果 ACD 是顺时针方向，那么我们可以将其缩小到情况 1，否则我们必须是情况 2 或 5.
to distinguish between these cases we have to check two more triangles - if ACD is clockwise then we can narrow this down to case 1, otherwise we must be in case 2 or 5.
要在情况 2 和 5 之间进行选择，我们可以测试 ABD
To pick between cases 2 and 5, we can test ABD
我们可以类似地检查ABC逆时针的情况.
We can check for the case of ABC anti-clockwise similarly.
在最坏的情况下，我们必须测试 3 个三角形.
In the worst case we have to test 3 triangles.
如果你的点不是凸点，你会找到里面的点，对其余的点进行排序，然后将它添加到任何边缘.请注意，如果四边形是凸的，那么 4 个点不再唯一地确定四边形，则有 3 个同样有效的四边形.
If your points are not convex, you would find the inside point, sort the rest and then add it in any edge. Note that if the quad is convex then 4 points no longer uniquely determine the quad, there are 3 equally valid quads.
这篇关于按顺时针顺序对四个点进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
