排序四点按顺时针顺序 [英] Sort Four Points in Clockwise Order

问题描述

在一个数组四个2D点。我需要对它们进行排序以顺时针方向。我认为它可以只用一个掉期操作来完成，但我一直没能够把这个正式下来。

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)

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

因此​​，只有一个交换是以往任何时候都需要 - 但它可能需要一些工作，以确定哪些

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屋！