问个排序问题

yanmo

就我有很多坐标，基本就是一个长方形，我想让他顺时针排序或者逆时针都行，求个这样的算法，
就比如(1.1)(1,4)(4,1)(4,4)(4,3)(1,2)还有一些。。。
排序成(1,1)(1,2)(1,4)(3,4)(4,4)(4,1)这个就是逆时针排的，哪位大佬能帮个忙弄一个感谢

houtian

如果只是一个象限的话, 以0,0为原点, 计算每个点坐标与原点的角度, 然后对角度大小进行排序, 对应的就是坐标顺序了

asasqwwq

分哪种情况，极角排序、质心/重心排序、单向漫水排序(单像素图坐标)

补充内容 (2024-5-9 10:11):
漫水暂时不说，如果是线性坐标组：极角排序；闭合型/环形：重心排序。使用向量叉积即可：

.版本 2

.子程序 LQS点_叉积, 整数型, 公开, 向量：相对...

asasqwwq

asasqwwq 发表于 2024-5-9 10:08
分哪种情况，极角排序、质心/重心排序、单向漫水排序(单像素图坐标)

补充内容 (2024-5-9 10:11):

.版本 2

.子程序 LQS点_叉积, 整数型, 公开, 向量：相对于起点p0(x0,y0)，则p0p1和p0p2的叉积为(p1-p0)×(p2-p0) = (x1-x0)(y2-y0)-(x2-x0)(y1-y0)。若结果为负，p0p2在p0p1的逆时针方向(p1前点、p0中间点、p2后点/凸点)，在p1处左转； 结果为正则右转； 为0表示三点共线
.参数 起点, 坐标, , 向量共起点
.参数 终点1, 坐标, , 向量1终点
.参数 终点2, 坐标, , 向量2终点

返回 ((终点1.x － 起点.x) × (终点2.y － 起点.y) － (终点2.x － 起点.x) × (终点1.y － 起点.y))
[e=0][/e]

asasqwwq

asasqwwq 发表于 2024-5-9 10:11
.版本 2

.子程序 LQS点_叉积, 整数型, 公开, 向量：相对于起点p0(x0,y0)，则p0p1和p0p2的叉积为(p1-p0) ...

  

子程序名	返回值类型	公开	备 注
LQS坐标组_极角排序_坐标			可独立使用，不用添加变量“轮廓点集”
参数名	类 型	参考	可空	数组	备 注
参_坐标	坐标				对坐标点集进行排序。根据向量叉积的定义，向量OPi和OPj的叉积大于0，则向量OPj在向量OPi的逆时针方向，即点Pj小于点Pi。
反向排序	逻辑型

变量名	类 型	静态	数组	备 注
i	整数型
总数	整数型
j	整数型
顶点	坐标		1

如果真 (取数组成员数 (参_坐标) ≤ 0)
' 调试输出 (“没有排序成员。”)
返回 ()
顶点 [1] ＝ 参_坐标 [1]
j ＝ 1
计次循环首 (取数组成员数 (参_坐标), i)
判断 (顶点 [1].y ＞ 参_坐标 [i].y)
顶点 [1] ＝ 参_坐标 [i]
j ＝ i
判断 (顶点 [1].y ＝ 参_坐标 [i].y)
如果真 (顶点 [1].x ＞ 参_坐标 [i].x)
顶点 [1] ＝ 参_坐标 [i]
j ＝ i




计次循环尾 ()
删除成员 (参_坐标, j, 1)
总数 ＝ 取数组成员数 (参_坐标)
如果 (反向排序)
计次循环首 (总数 － 1, i)
计次循环首 (总数 － i, j)
判断 (LQS点_叉积 (顶点 [1], 参_坐标 [j], 参_坐标 [j ＋ 1]) ＞ 0)
交换变量 (参_坐标 [j], 参_坐标 [j ＋ 1])
判断 (LQS点_叉积 (顶点 [1], 参_坐标 [j], 参_坐标 [j ＋ 1]) ＝ 0)
如果真 (参_坐标 [j].x ＜ 参_坐标 [j ＋ 1].x)
交换变量 (参_坐标 [j], 参_坐标 [j ＋ 1])




计次循环尾 ()
计次循环尾 ()

计次循环首 (总数 － 1, i)
计次循环首 (总数 － i, j)
判断 (LQS点_叉积 (顶点 [1], 参_坐标 [j], 参_坐标 [j ＋ 1]) ＜ 0)
交换变量 (参_坐标 [j], 参_坐标 [j ＋ 1])
判断 (LQS点_叉积 (顶点 [1], 参_坐标 [j], 参_坐标 [j ＋ 1]) ＝ 0)
如果真 (参_坐标 [j].x ＜ 参_坐标 [j ＋ 1].x)
交换变量 (参_坐标 [j], 参_坐标 [j ＋ 1])




计次循环尾 ()
计次循环尾 ()

加入成员 (顶点, 参_坐标)
参_坐标 ＝ 顶点

子程序名	返回值类型	公开	备 注
LQS坐标组_极角重心排序_坐标			LQS写，主要用于环形点集排序。  可独立使用，不用添加变量“轮廓点集”
参数名	类 型	参考	可空	数组	备 注
参_坐标	坐标				对坐标点集进行排序。根据向量叉积的定义，向量OPi和OPj的叉积大于0，则向量OPj在向量OPi的逆时针方向，即点Pj小于点Pi。
反向排序	逻辑型

变量名	类 型	静态	数组	备 注
i	整数型
总数	整数型
j	整数型
顶点	坐标		1
临时成员数	整数型
X和	整数型
Y和	整数型

如果真 (取数组成员数 (参_坐标) ≤ 0)
' 调试输出 (“没有排序成员。”)
返回 ()
' ==========================
临时成员数 ＝ 取数组成员数 (参_坐标)
计次循环首 (临时成员数, i)
X和 ＝ X和 ＋ 参_坐标 [i].x
Y和 ＝ Y和 ＋ 参_坐标 [i].y
计次循环尾 ()
顶点 [1].x ＝ 到整数 (X和 ÷ 临时成员数)
顶点 [1].y ＝ 到整数 (Y和 ÷ 临时成员数)
' ==========================
总数 ＝ 取数组成员数 (参_坐标)
如果 (反向排序)
计次循环首 (总数 － 1, i)
计次循环首 (总数 － i, j)
判断 (LQS点_叉积 (顶点 [1], 参_坐标 [j], 参_坐标 [j ＋ 1]) ＞ 0)
交换变量 (参_坐标 [j], 参_坐标 [j ＋ 1])
判断 (LQS点_叉积 (顶点 [1], 参_坐标 [j], 参_坐标 [j ＋ 1]) ＝ 0)
如果真 (参_坐标 [j].x ＜ 参_坐标 [j ＋ 1].x)
交换变量 (参_坐标 [j], 参_坐标 [j ＋ 1])




计次循环尾 ()
计次循环尾 ()

计次循环首 (总数 － 1, i)
计次循环首 (总数 － i, j)
判断 (LQS点_叉积 (顶点 [1], 参_坐标 [j], 参_坐标 [j ＋ 1]) ＜ 0)
交换变量 (参_坐标 [j], 参_坐标 [j ＋ 1])
判断 (LQS点_叉积 (顶点 [1], 参_坐标 [j], 参_坐标 [j ＋ 1]) ＝ 0)
如果真 (参_坐标 [j].x ＜ 参_坐标 [j ＋ 1].x)
交换变量 (参_坐标 [j], 参_坐标 [j ＋ 1])




计次循环尾 ()
计次循环尾 ()

加入成员 (顶点, 参_坐标)
删除成员 (顶点, 1, 1)
参_坐标 ＝ 顶点

.版本 2<br /> <br /> .子程序 LQS坐标组_极角排序_坐标, , 公开, 可独立使用，不用添加变量“轮廓点集”<br /> .参数 参_坐标, 坐标, 数组, 对坐标点集进行排序。根据向量叉积的定义，向量OPi和OPj的叉积大于0，则向量OPj在向量OPi的逆时针方向，即点Pj小于点Pi。<br /> .参数 反向排序, 逻辑型, 可空<br /> .局部变量 i, 整数型<br /> .局部变量 总数, 整数型<br /> .局部变量 j, 整数型<br /> .局部变量 顶点, 坐标, , "1"<br /> <br /> .如果真 (取数组成员数 (参_坐标) ≤ 0)<br />     ' 调试输出 (“没有排序成员。”)<br />     返回 ()<br /> .如果真结束<br /> 顶点 [1] ＝ 参_坐标 [1]<br /> j ＝ 1<br /> .计次循环首 (取数组成员数 (参_坐标), i)<br />     .判断开始 (顶点 [1].y ＞ 参_坐标 <i>.y)<br />         顶点 [1] ＝ 参_坐标 <i><br />         j ＝ i<br />     .判断 (顶点 [1].y ＝ 参_坐标 <i>.y)<br />         .如果真 (顶点 [1].x ＞ 参_坐标 <i>.x)<br />             顶点 [1] ＝ 参_坐标 <i><br />             j ＝ i<br />         .如果真结束<br /> <br />     .默认<br /> <br />     .判断结束<br /> <br /> .计次循环尾 ()<br /> 删除成员 (参_坐标, j, 1)<br /> 总数 ＝ 取数组成员数 (参_坐标)<br /> .如果 (反向排序)<br /> <br />     .计次循环首 (总数 － 1, i)<br />         .计次循环首 (总数 － i, j)<br />             .判断开始 (LQS点_叉积 (顶点 [1], 参_坐标 [j], 参_坐标 [j ＋ 1]) ＞ 0)<br />                 交换变量 (参_坐标 [j], 参_坐标 [j ＋ 1])<br />             .判断 (LQS点_叉积 (顶点 [1], 参_坐标 [j], 参_坐标 [j ＋ 1]) ＝ 0)<br />                 .如果真 (参_坐标 [j].x ＜ 参_坐标 [j ＋ 1].x)<br />                     交换变量 (参_坐标 [j], 参_坐标 [j ＋ 1])<br />                 .如果真结束<br /> <br />             .默认<br /> <br />             .判断结束<br /> <br />         .计次循环尾 ()<br />     .计次循环尾 ()<br /> <br /> .否则<br />     .计次循环首 (总数 － 1, i)<br />         .计次循环首 (总数 － i, j)<br />             .判断开始 (LQS点_叉积 (顶点 [1], 参_坐标 [j], 参_坐标 [j ＋ 1]) ＜ 0)<br />                 交换变量 (参_坐标 [j], 参_坐标 [j ＋ 1])<br />             .判断 (LQS点_叉积 (顶点 [1], 参_坐标 [j], 参_坐标 [j ＋ 1]) ＝ 0)<br />                 .如果真 (参_坐标 [j].x ＜ 参_坐标 [j ＋ 1].x)<br />                     交换变量 (参_坐标 [j], 参_坐标 [j ＋ 1])<br />                 .如果真结束<br /> <br />             .默认<br /> <br />             .判断结束<br /> <br />         .计次循环尾 ()<br />     .计次循环尾 ()<br /> <br /> .如果结束<br /> <br /> 加入成员 (顶点, 参_坐标)<br /> 参_坐标 ＝ 顶点<br /> <br /> <br /> <br /> <br /> .子程序 LQS坐标组_极角重心排序_坐标, , 公开, LQS写，主要用于环形点集排序。  可独立使用，不用添加变量“轮廓点集”<br /> .参数 参_坐标, 坐标, 数组, 对坐标点集进行排序。根据向量叉积的定义，向量OPi和OPj的叉积大于0，则向量OPj在向量OPi的逆时针方向，即点Pj小于点Pi。<br /> .参数 反向排序, 逻辑型, 可空<br /> .局部变量 i, 整数型<br /> .局部变量 总数, 整数型<br /> .局部变量 j, 整数型<br /> .局部变量 顶点, 坐标, , "1"<br /> .局部变量 临时成员数, 整数型<br /> .局部变量 X和, 整数型<br /> .局部变量 Y和, 整数型<br /> <br /> .如果真 (取数组成员数 (参_坐标) ≤ 0)<br />     ' 调试输出 (“没有排序成员。”)<br />     返回 ()<br /> .如果真结束<br /> ' ==========================<br /> 临时成员数 ＝ 取数组成员数 (参_坐标)<br /> .计次循环首 (临时成员数, i)<br />     X和 ＝ X和 ＋ 参_坐标 <i>.x<br />     Y和 ＝ Y和 ＋ 参_坐标 <i>.y<br /> .计次循环尾 ()<br /> 顶点 [1].x ＝ 到整数 (X和 ÷ 临时成员数)<br /> 顶点 [1].y ＝ 到整数 (Y和 ÷ 临时成员数)<br /> ' ==========================<br /> 总数 ＝ 取数组成员数 (参_坐标)<br /> .如果 (反向排序)<br /> <br />     .计次循环首 (总数 － 1, i)<br />         .计次循环首 (总数 － i, j)<br />             .判断开始 (LQS点_叉积 (顶点 [1], 参_坐标 [j], 参_坐标 [j ＋ 1]) ＞ 0)<br />                 交换变量 (参_坐标 [j], 参_坐标 [j ＋ 1])<br />             .判断 (LQS点_叉积 (顶点 [1], 参_坐标 [j], 参_坐标 [j ＋ 1]) ＝ 0)<br />                 .如果真 (参_坐标 [j].x ＜ 参_坐标 [j ＋ 1].x)<br />                     交换变量 (参_坐标 [j], 参_坐标 [j ＋ 1])<br />                 .如果真结束<br /> <br />             .默认<br /> <br />             .判断结束<br /> <br />         .计次循环尾 ()<br />     .计次循环尾 ()<br /> <br /> .否则<br />     .计次循环首 (总数 － 1, i)<br />         .计次循环首 (总数 － i, j)<br />             .判断开始 (LQS点_叉积 (顶点 [1], 参_坐标 [j], 参_坐标 [j ＋ 1]) ＜ 0)<br />                 交换变量 (参_坐标 [j], 参_坐标 [j ＋ 1])<br />             .判断 (LQS点_叉积 (顶点 [1], 参_坐标 [j], 参_坐标 [j ＋ 1]) ＝ 0)<br />                 .如果真 (参_坐标 [j].x ＜ 参_坐标 [j ＋ 1].x)<br />                     交换变量 (参_坐标 [j], 参_坐标 [j ＋ 1])<br />                 .如果真结束<br /> <br />             .默认<br /> <br />             .判断结束<br /> <br />         .计次循环尾 ()<br />     .计次循环尾 ()<br /> <br /> .如果结束<br /> <br /> 加入成员 (顶点, 参_坐标)<br /> 删除成员 (顶点, 1, 1)<br /> 参_坐标 ＝ 顶点

参考用...................................................

fydcr

[JavaScript] 纯文本查看 复制代码

.版本 2
.程序集 程序集1
.子程序 坐标排序， , 公开
    .参数 坐标数组，二维数组，引用，要排序的坐标数组
    .参数 方向，文本型，可空，排序的方向，"顺时针" 或 "逆时针"
    .局部变量 排序后的坐标，二维数组，, 排序后的坐标数组
    .局部变量 i，整数型，, 循环变量
    .局部变量 极角，实数型，, 用于计算坐标与原点的极角
    .局部变量 临时坐标，二维数组，, 临时存储坐标
    .局部变量 原点，二维数组，, 原点坐标 (0,0)

    .如果 （方向 = "逆时针")
        .计次循环 (取数组成员数(坐标数组)，i)
            极角 = ATan(坐标数组[1] / 坐标数组[0])
            如果 (坐标数组[0] < 0)
                极角 = 极角 + 3.14159265
            临时坐标 = [极角，坐标数组]
        结束循环
    .否则
        .计次循环 (取数组成员数(坐标数组)，i)
            极角 = ATan(坐标数组[1] / 坐标数组[0])
            如果 (坐标数组[0] < 0 且 坐标数组[1] >= 0)
                极角 = 极角 + 6.28318531
            如果 (坐标数组[0] < 0 且 坐标数组[1] < 0)
                极角 = 极角 + 3.14159265
            临时坐标 = [极角，坐标数组]
        结束循环
    .如果结束

    .对 临时坐标 按 第1个元素 用 极角 排序

    .计次循环 (取数组成员数(临时坐标)，i)
        排序后的坐标 = 临时坐标[2]
    结束循环

    .返回 (排序后的坐标)
.子程序结束

补充内容 (2024-5-9 11:27):
这个算法首先计算每个坐标与原点形成的极角，然后根据指定的方向调整极角的值，以确保逆时针排序时，负x轴的坐标极角会加上π，而顺时针排序...