数组中的四个二维点。我需要按顺时针顺序对它们进行排序。我认为只需一次交换操作即可完成，但我无法正式将其放下。
编辑：在我的例子中，这四个点是一个凸多边形。
编辑：这四个点是凸多边形的顶点。他们不必井井有条。
Vulcan Eager
问问题
27918 次
16 回答
18
如果你想从更数学的角度来看，我们可以考虑 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 个同样有效的四边形。
于 2008-10-28T22:15:07.603 回答
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) 以将整个多边形的绕组更改为顺时针方向。
我强烈建议用几个样本点画这个，看看我在说什么。请注意，您有很多例外情况需要处理，例如凹多边形、共线点、重合点等...
于 2008-10-28T07:53:44.783 回答
4
如果有人感兴趣，这是我对类似问题的快速而肮脏的解决方案。
我的问题是按以下顺序排列我的矩形角：
左上>右上>右下>左下
基本上它是从左上角开始的顺时针顺序。
该算法的思想是：
按行对角进行排序，然后按列对角对进行排序。
// 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;
}
于 2012-04-11T16:55:18.047 回答
3
奥利弗是对的。此代码（社区维基化）生成并排序 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;
}
于 2008-10-29T07:41:23.667 回答
3
对于每个点排列，使用鞋带公式从坐标计算面积（没有绝对值，因此面积可以为正或负）。最大面积值似乎对应于直接简单四边形：使用鞋带公式找到的简单直接四边形
于 2012-12-20T11:35:18.883 回答
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 点进行排序。当然，确定需要哪个交换操作是诀窍。
于 2008-10-28T07:30:07.357 回答
1
我有一个进一步的改进要添加到我之前的答案中
记住 - 这些是我们可以遇到的情况。
- A B C D
- ABDC
- 生物多样性公约
- 数据库
- 中国农业银行
- ADCB
如果 ABC 是逆时针方向（有负符号区域），那么我们处于第 3、4、6 种情况。如果我们在这种情况下交换 B 和 C，则剩下以下可能性：
- A B C D
- ABDC
- A B C D
- ABDC
- 中国农业银行
- 中国农业银行
接下来我们可以检查 ABD 并在逆时针方向交换 B 和 D（案例 5、6）
- A B C D
- ABDC
- A B C D
- ABDC
- ABDC
- ABDC
最后，我们需要检查 ACD，如果 ACD 是逆时针方向，则交换 C & D。现在我们知道我们的观点都是有序的。
这种方法不如我之前的方法效率高——这需要每次检查 3 次，并且需要多次交换；但代码会简单得多。
于 2008-10-30T21:08:17.690 回答
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);
参考点位于多边形内的位置。
更多信息在这个网站
于 2012-08-27T11:56:39.160 回答
1
如果您只需要处理 4 个点，那么有一种最简单的方法可以做到这一点
按 y 值排序
顶行是前两点，底行是其余 2 点
对于顶行和底行，按 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]]
于 2017-05-15T07:26:10.640 回答
0
我相信您是对的，单次交换可以确保由平面中的四个点表示的多边形是凸的。仍有待回答的问题是：
- 这组四个点是凸多边形吗？
- 如果不是，那么需要交换哪两点？
- 哪个方向是顺时针？
进一步思考，我认为上面第二个问题的唯一答案是“中间两个”。
于 2008-10-28T06:45:14.547 回答
0
这个怎么样？
// Take signed area of ABC.
// If negative,
// Swap B and C.
// Otherwise,
// Take signed area of ACD.
// If negative, swap C and D.
想法？
于 2008-10-28T07:27:38.423 回答
0
如果我们假设点 x 大于点 y 如果它与点 (0,0) 的夹角更大，那么我们可以在 c# 中以这种方式实现
class Point : IComparable<Point>
{
public int X { set; get; }
public int Y { set; get; }
public double Angle
{
get
{
return Math.Atan2(X, Y);
}
}
#region IComparable<Point> Members
public int CompareTo(Point other)
{
return this.Angle.CompareTo(other.Angle);
}
#endregion
public static List<Point> Sort(List<Point> points)
{
return points.Sort();
}
}
于 2008-10-28T10:09:11.920 回答
0
if AB crosses CD
swap B,C
elif AD crosses BC
swap C,D
if area (ABC) > 0
swap B,D
(I mean area(ABC) > 0 when A->B->C is counter-clockwise).
Let p*x + q*y + r = 0 be the straight line that joins A and B.
Then AB crosses CD if p*Cx + q*Cy + r and p*Dx + q*Dy + r
have different sign, i.e. their product is negative.
第一个“if/elif”以顺时针或逆时针顺序带来四个点。（因为你的多边形是凸的，唯一的“交叉”选项是“AC 与 BD”，这意味着这四个点已经排序。）最后一个“if”在逆时针方向反转。
于 2008-10-29T03:05:01.667 回答
0
你应该看看格雷厄姆的扫描。当然，您需要对其进行调整，因为它会逆时针找到指向。
ps：这对于4分来说可能有点过分了，但是如果点数增加它可能会很有趣
于 2008-10-29T03:25:58.927 回答
-1
Wedge 的回答是正确的。
为了轻松实现它，我认为与 smacl 相同：您需要找到边界的中心并将您的点转换到该中心。
像这样：
centerPonintX = Min(x) + ( (Max(x) – Min(x)) / 2 )
centerPonintY = Min(y) + ( (Max(y) – Min(y)) / 2 )
然后，从每个点减少 centerPointX 和 centerPointY 以将其转换为边界的原点。
最后，只需一个转折即可应用 Wedge 的解决方案：获取每个实例的 arctan(x/y) 的绝对值（这样对我有用）。
于 2008-10-28T08:10:20.863 回答
-1
if( (p2.x-p1.x)*(p3.y-p1.y) > (p3.x-p1.x)*(p2.y-p1.y) )
swap( &p1, &p3 );
'>' 可能面对错误的方向，但你明白了。
于 2008-10-28T09:57:28.183 回答