一个包含四个二维点的数组。我需要按顺时针顺序对它们进行排序。我认为只需要一次交换操作就能完成，但我还没有能够正式地写下来。
编辑：在我的情况下，这四个点是一个凸多边形。
编辑：这四个点是凸多边形的顶点。它们不一定是有序的。
顺时针排序四个点
29
- Vulcan Eager
5
你的意思是指绕原点顺时针方向吗？ - Vincent Ramdhanie
或者它可以顺时针绕着边界中心。 - vmarquez
对我来说，凸多边形的顺时针顺序意味着在遍历点时只进行右转。原点不应该影响顺序。 - Agnel Kurian
如果我们在讨论顺时针的多边形，检查我的编辑关于分解成两个三角形并基于此进行交换的内容。这是一个更简单的方法。 - SmacL
参见：https://dev59.com/PnE85IYBdhLWcg3wShaf - Dave Jarvis
16个回答
18
如果你想从更数学的角度来看，我们可以考虑4个点的排列。
在我们的例子中，有4个以顺时针顺序排列的排列。
A B C D
B C D A
C D A B
D A B C
所有其他可能的排列都可以通过0或1次交换转换为这些形式之一。（我只考虑以A开头的排列，因为它是对称的）
- 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
因此，只需要一次交换 - 但是可能需要一些工作来确定交换哪一个。
通过查看前三个点，并检查ABC的有向面积的符号，我们可以确定它们是否顺时针。如果它们顺时针，则我们在情况1、2或5中
为了区分这些情况，我们必须检查另外两个三角形 - 如果ACD是顺时针，则我们可以将其缩小到情况1，否则我们必须处于情况2或5。
要在情况2和5之间选择，我们可以测试ABD。
我们可以类似地检查ABC逆时针的情况。
在最坏的情况下，我们必须测试3个三角形。
如果您的点不是凸的，则会找到内部点，对其余点进行排序，然后将其添加到任何一条边上。请注意，如果四边形是凸的，则4个点不再唯一确定四边形，有3个同样有效的四边形。
- Oliver Hallam
1
你能解释一下“ABC的有向面积”是什么意思吗？ - Minh Nghĩa
7
这里有几个值得考虑的想法：
顺时针只有在参照点的情况下才有意义。我倾向于将参照点视为一组点的重心，例如相对于四个点的平均位置处的点的顺时针方向，而不是可能非常远的原点。
如果您有四个点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)。
我强烈建议您用一些样本点来绘制图形，以便更好地理解我的意思。请注意，您需要处理很多特殊情况，如凹多边形、共线点、重合点等等...
- smacl
3
只有在你把它分成的两个三角形不相交时才有效。请参见我帖子中的第二张图表 - ABC和CDA互相交叉，因此使它们顺时针并不能完全解决问题。 - Oliver Hallam
我认为 (a,b,c,d) 是一个有序的顶点集合或循环，其中多边形的边为ab，bc，cd和da。我认为这是合理的，因为开头的问题涉及凸多边形，这意味着顶点的顺序。 - SmacL
我的意思是这些点是凸多边形的顶点，而不是按顺序排列的。 - Agnel Kurian
5
如果有人感兴趣，这是我解决类似问题的快速且简单的方法。
我的问题是要按以下顺序排列矩形的角：
左上角 > 右上角 > 右下角 > 左下角
基本上就是按照顺时针方向开始于左上角。
该算法的思路是：
按行对角进行排序，然后按列对角对进行排序。
我的问题是要按以下顺序排列矩形的角：
左上角 > 右上角 > 右下角 > 左下角
基本上就是按照顺时针方向开始于左上角。
该算法的思路是：
按行对角进行排序，然后按列对角对进行排序。
// 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;
}
- Rui Marques
1
在
orderPointsByRows 函数中，应该是 if (p1.y > p2.y) return -1; if (p1.y < p2.y) return 1; 吗？
你想要更大的（顶部）y值排在前面。 - Yoav Gur3
奥利弗是正确的。这段代码（社区维基）生成并排序了由4个点组成的数组的所有可能组合。
#include <cstdio>
#include <algorithm>
struct PointF {
float x;
float y;
};
// Returns the z-component of the cross product of a and b
inline double CrossProductZ(const PointF &a, const PointF &b) {
return a.x * b.y - a.y * b.x;
}
// Orientation is positive if abc is counterclockwise, negative if clockwise.
// (It is actually twice the area of triangle abc, calculated using the
// Shoelace formula: http://en.wikipedia.org/wiki/Shoelace_formula .)
inline double Orientation(const PointF &a, const PointF &b, const PointF &c) {
return CrossProductZ(a, b) + CrossProductZ(b, c) + CrossProductZ(c, a);
}
void Sort4PointsClockwise(PointF points[4]){
PointF& a = points[0];
PointF& b = points[1];
PointF& c = points[2];
PointF& d = points[3];
if (Orientation(a, b, c) < 0.0) {
// Triangle abc is already clockwise. Where does d fit?
if (Orientation(a, c, d) < 0.0) {
return; // Cool!
} else if (Orientation(a, b, d) < 0.0) {
std::swap(d, c);
} else {
std::swap(a, d);
}
} else if (Orientation(a, c, d) < 0.0) {
// Triangle abc is counterclockwise, i.e. acb is clockwise.
// Also, acd is clockwise.
if (Orientation(a, b, d) < 0.0) {
std::swap(b, c);
} else {
std::swap(a, b);
}
} else {
// Triangle abc is counterclockwise, and acd is counterclockwise.
// Therefore, abcd is counterclockwise.
std::swap(a, c);
}
}
void PrintPoints(const char *caption, const PointF points[4]){
printf("%s: (%f,%f),(%f,%f),(%f,%f),(%f,%f)\n", caption,
points[0].x, points[0].y, points[1].x, points[1].y,
points[2].x, points[2].y, points[3].x, points[3].y);
}
int main(){
PointF points[] = {
{5.0f, 20.0f},
{5.0f, 5.0f},
{20.0f, 20.0f},
{20.0f, 5.0f}
};
for(int i = 0; i < 4; i++){
for(int j = 0; j < 4; j++){
if(j == i) continue;
for(int k = 0; k < 4; k++){
if(j == k || i == k) continue;
for(int l = 0; l < 4; l++){
if(j == l || i == l || k == l) continue;
PointF sample[4];
sample[0] = points[i];
sample[1] = points[j];
sample[2] = points[k];
sample[3] = points[l];
PrintPoints("input: ", sample);
Sort4PointsClockwise(sample);
PrintPoints("output: ", sample);
printf("\n");
}
}
}
}
return 0;
}
- Vulcan Eager
1
将有符号面积计算分离为一个函数会提高可读性。如果性能很重要，那么您可以提取出所有表达式，例如（a.xc.y - c.xa.y）- 最终您会使用它们两次。 - Oliver Hallam
2
我有一个进一步的改进要添加到我的先前答案中
记住 - 这些是我们可能遇到的情况。
- A B C D
- A B D C
- A C B D
- A C D B
- A D B C
- A D C B
如果ABC是逆时针的（具有负面积），那么我们处于第3、4、6种情况。如果我们在这种情况下交换B和C，那么我们就只剩下以下可能性：
- A B C D
- A B D C
- A B C D
- A B D C
- A D B C
- A D B C
接下来，我们可以检查ABD并在其逆时针时交换B和D（第5、6种情况）
- A B C D
- A B D C
- A B C D
- A B D C
- A B D C
- A B D C
最后，我们需要检查ACD并在ACD逆时针时交换C和D。现在我们知道我们的点都是有序的。
这种方法不如我的先前的方法高效 - 每次需要3个检查和多个交换; 但代码会简单得多。
- Oliver Hallam
2
如果你只需要处理4个点，那么最简单的方法是：
按y值排序
第一行为前两个点，第二行为后两个点
对于第一行和第二行，按x值排序
.
corners.sort(key=lambda ii: ii[1], reverse=True)
topRow = corners[0:2]
bottomRow = corners[2:]
topRow.sort(key=lambda ii: ii[0])
bottomRow.sort(key=lambda ii: ii[0])
# clockwise
return [topRow[0], topRow[1], bottomRow[1], bottomRow[0]]
- Eisneim
1
先用较长的方式解决问题，然后再进行优化。
更具体的问题是按照相对于正x轴的角度递减顺序对坐标进行排序。这个角度，以弧度表示，将由以下函数给出：
x>0
AND y >= 0
angle = arctan(y/x)
AND y < 0
angle = arctan(y/x) + 2*pi
x==0
AND y >= 0
angle = 0
AND y < 0
angle = 3*pi/2
x<0
angle = arctan(y/x) + pi
然后，当然，只需要按角度对坐标进行排序。请注意，如果且仅当x>z时，arctan(w)>arctan(z)，因此您可以轻松优化将角度相互比较的函数。
对于角度在窗口上单调递减（或者最多增加一次）的排序略有不同。
缺少详细证明，我要提到的是，我验证了单个交换操作将以顺时针顺序排序4个2D点。当然，确定哪个交换操作是必要的是诀窍。
- Wedge
5
不需要详细的证明，我只想提一下我验证过单个交换操作可以按顺时针顺序排序4个2D点。当然，确定哪个交换操作是必要的是关键。 你是如何验证的？ - Agnel Kurian
通过检查，有限的排列方式可以用于4个值的排序。我列出了所有可能的排列方式，然后确定如何按照所需的方式进行排序，在每种情况下仅需要一个交换操作即可完成。你也可以自己尝试，写出对数字1、2、3、4进行排序的所有方法。 - Wedge
这将使点围绕原点顺时针排列，而不是顺时针四边形。此外，arctan（相对而言）速度较慢。 - Oliver Hallam
1请注意，在.NET中，Math.Atan2(x, y)可以计算您的角度，而无需进行所有这些混乱。 - Oliver Hallam
@Oliver，实际目标是创建一个优化的解决方案，完全不使用atan函数。 - Wedge
1
var arr = [{x:3,y:3},{x:4,y:1},{x:0,y:2},{x:5,y:2},{x:1,y:1}];
var reference = {x:2,y:2};
arr.sort(function(a,b) {
var aTanA = Math.atan2((a.y - reference.y),(a.x - reference.x));
var aTanB = Math.atan2((b.y - reference.y),(b.x - reference.x));
if (aTanA < aTanB) return -1;
else if (aTanB < aTanA) return 1;
return 0;
});
console.log(arr);
参考点位于多边形内部。
更多信息请访问网站。
- Shekhar
0
这个怎么样？
// Take signed area of ABC.
// If negative,
// Swap B and C.
// Otherwise,
// Take signed area of ACD.
// If negative, swap C and D.
Ideas?
- Vulcan Eager
2
交换相对的顶点而不是相邻的顶点。但除此之外，是的。 - Menkboy
PS：只有当ABC的有符号面积为零（或接近零的epsilon）时，您才需要执行第二个测试。 - Menkboy
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接