按顺序排序四点

Question

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

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

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

Answer 1

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

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

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

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

1. ABCD - 完成了
2. ABDC - 交换C和D.
3. ACBD - 交换B和C.
4. ACDB - 交换A和B.
5. ADBC - 交换A和D.
6. ADCB - 交换B和D.

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

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

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

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

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

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

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

Answer 2

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

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

• 如果您有四个点,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),以将多边形的绕组整体改为顺时针方向.

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

Answer 3

如果有人感兴趣，这是我对类似问题的快速而肮脏的解决方案。

我的问题是让我的矩形角按以下顺序排序：

左上 > 右上 > 右下 > 左下

基本上是从左上角开始顺时针顺序。

该算法的思想是：

按行对角进行排序，然后按列对角对进行排序。

    // top-left = 0; top-right = 1; 
    // right-bottom = 2; left-bottom = 3;
    List<Point> orderRectCorners(List<Point> corners) {    
        if(corners.size() == 4) {    
            ordCorners = orderPointsByRows(corners);
                
            if(ordCorners.get(0).x > ordCorners.get(1).x) { // swap points
                Point tmp = ordCorners.get(0);
                ordCorners.set(0, ordCorners.get(1));
                ordCorners.set(1, tmp);
            }
                    
            if(ordCorners.get(2).x < ordCorners.get(3).x) { // swap points
                Point tmp = ordCorners.get(2);
                ordCorners.set(2, ordCorners.get(3));
                ordCorners.set(3, tmp);
            }               
            return ordCorners;
        }    
        return empty list or something;
    }

    List<Point> orderPointsByRows(List<Point> points) {
        Collections.sort(points, new Comparator<Point>() {
            public int compare(Point p1, Point p2) {
                if (p1.y < p2.y) return -1;
                if (p1.y > p2.y) return 1;
                return 0;
            }
        });
        return points;
    }