按顺序排序四点

阵列中的四个2D点.我需要按顺时针顺序对它们进行排序.我认为只需一次交换操作即可完成,但我无法正式解决这个问题.

编辑:在我的情况下,四个点是凸多边形.

编辑:四个点是凸多边形的顶点.他们不需要整理好.

如果你想采用更多的数学观点,我们可以考虑4点的排列

在我们的例子中,有4种顺序顺序排列

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

所有其他可能的排列可以转换为具有0或1个交换的这些形式之一.(我只考虑以A开头的排列,因为它是对称的)

ABCD - 完成了

ABDC - 交换C和D.

ACBD - 交换B和C.

ACDB - 交换A和B.

ADBC - 交换A和D.

ADCB - 交换B和D.

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

通过查看前三个点,并检查ABC签名区域的符号,我们可以确定它们是否顺时针方向.如果它们是顺时针方向,那么我们就是1 2或5

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

为了在案例2和5之间进行选择,我们可以测试ABD

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

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

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

这里有几个值得考虑的想法;

顺时针方向仅对原点有意义.我倾向于将原点视为一组点的重心.例如,相对于四个点的平均位置处的点顺时针方向,而不是可能非常遥远的原点.

如果您有四个点,a,b,c,d,则原点周围存在多个顺时针顺序.例如,如果(a,b,c,d)形成顺时针排序,那么(b,c,d,a),(c,d,a,b)和(d,a,b,c)也是如此

你的四个点已形成多边形吗？如果是这样,则需要检查和反转绕组而不是对点进行分类,例如a,b,c,d变为d,c,b,a.如果没有,我会根据每个点和原点之间的连接方式进行排序,根据Wedges响应.

编辑:关于你要交换哪些点的评论;

在三角形(a,b,c)的情况下,如果第三点c位于线ab的右侧,我们可以说它是顺时针的.我使用以下辅助函数根据点的坐标确定这个;

int side(double x1,double y1,double x2,double y2,double px,double py)
{
 double dx1,dx2,dy1,dy2;
 double o;

 dx1 = x2 - x1;
 dy1 = y2 - y1;
 dx2 = px - x1;
 dy2 = py - y1;
 o = (dx1*dy2)-(dy1*dx2);
 if (o > 0.0) return(LEFT_SIDE);
 if (o < 0.0) return(RIGHT_SIDE);
 return(COLINEAR);
}

如果我有一个四点凸多边形,(a,b,c,d),我可以将其视为两个三角形,(a,b,c)和(c,d,a).如果(a,b,c)是逆时针方向,我将绕组(a,b,c,d)改为(a,d,c,b),以将多边形的绕组整体改为顺时针方向.

我强烈建议用几个样本点来绘制它,看看我在说什么.请注意,您有很多特殊情况需要处理,例如凹多边形,共线点,重合点等等......