数组中的四个二维点.我需要按顺时针顺序对它们进行排序.我认为只需一次交换操作即可完成，但我无法正式将其放下.
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)
因此只需要一次交换 - 但可能需要一些工作才能确定哪个.
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.
更多推荐
按顺时针顺序排列四个点
发布评论