给定一个x，y点数组，如何按顺时针顺序（围绕它们的整体平均中心点）对该数组的点进行排序？我的目标是将点传递给线创建函数，以最终看起来相当“坚实”的东西，尽可能凸起，没有相交的线。
为了它的价值，我正在使用Lua，但任何伪代码都会受到赞赏。
更新：作为参考，这是基于Ciamej优秀答案的Lua代码（忽略我的“app”前缀）：
function appSortPointsClockwise(points)
local centerPoint = appGetCenterPointOfPoints(points)
app.pointsCenterPoint = centerPoint
table.sort(points, appGetIsLess)
return points
end
function appGetIsLess(a, b)
local center = app.pointsCenterPoint
if a.x >= 0 and b.x < 0 then return true
elseif a.x == 0 and b.x == 0 then return a.y > b.y
end
local det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y)
if det < 0 then return true
elseif det > 0 then return false
end
local d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y)
local d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - center.y)
return d1 > d2
end
function appGetCenterPointOfPoints(points)
local pointsSum = {x = 0, y = 0}
for i = 1, #points do pointsSum.x = pointsSum.x + points[i].x; pointsSum.y = pointsSum.y + points[i].y end
return {x = pointsSum.x / #points, y = pointsSum.y / #points}
end
首先，计算中心点。然后使用您喜欢的任何排序算法对点进行排序，但使用特殊比较例程来确定一个点是否小于另一个点。
通过这个简单的计算，您可以检查一个点（a）是否相对于中心位于另一个点（b）的左侧或右侧：
det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y)
如果结果为零，则它们在中心的同一条线上，如果它是正的或负的，则它在一侧或另一侧，因此一个点将在另一侧之前。使用它，您可以构建一个小于关系的比较点，并确定它们在排序数组中的显示顺序。但是你必须定义该顺序的开始位置，我的意思是起始角度（例如x轴的正半部分）。
比较函数的代码如下所示：
bool less(point a, point b)
{
if (a.x - center.x >= 0 && b.x - center.x < 0)
return true;
if (a.x - center.x < 0 && b.x - center.x >= 0)
return false;
if (a.x - center.x == 0 && b.x - center.x == 0) {
if (a.y - center.y >= 0 || b.y - center.y >= 0)
return a.y > b.y;
return b.y > a.y;
}
// compute the cross product of vectors (center -> a) x (center -> b)
int det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y);
if (det < 0)
return true;
if (det > 0)
return false;
// points a and b are on the same line from the center
// check which point is closer to the center
int d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y);
int d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - center.y);
return d1 > d2;
}
这将从12点开始顺时针点顺序。同一“小时”的积分将从远离中心的点开始。
如果使用整数类型（Lua中并不存在），则必须确保det，d1和d2变量属于能够保存执行计算结果的类型。
如果你想要实现看起来很稳固，尽可能凸出的东西，那么我想你正在寻找一个Convex Hull。你可以使用Graham Scan来计算它。在此算法中，您还必须从特殊轴心点开始顺时针（或逆时针）对点进行排序。然后每次重复简单的循环步骤，检查是否向左或向右转向凸包添加新点，此检查基于十字产品，就像上面的比较函数一样。
编辑：
添加了一个if语句if (a.y - center.y >= 0 || b.y - center.y >=0)，以确保具有x = 0和负y的点从远离中心的点开始排序。如果您不关心同一'小时'的点数顺序，您可以省略此if语句并始终返回a.y > b.y。
通过添加-center.x和-center.y更正了第一个if语句。
添加了第二个if语句(a.x - center.x < 0 && b.x - center.x >= 0)。这是一个明显的疏忽，它失踪了。现在可以重新组织if语句，因为某些检查是多余的。例如，如果第一个if语句中的第一个条件为false，则第二个if的第一个条件必须为true。但是，为了简单起见，我决定保留代码。编译器很可能会优化代码并产生相同的结果。
您要求的是一个称为polar coordinates的系统。从笛卡尔坐标到极坐标的转换很容易用任何语言完成。公式可以在this section找到。
我不知道Lua，但是this page似乎为这次转换提供了代码片段。
转换为极坐标后，只需按角度θ进行排序。
解决问题的一个有趣的替代方法是找到旅行商问题（TSP）的近似最小值，即。连接所有积分的最短路线。如果你的点形成凸形，它应该是正确的解决方案，否则，它应该仍然看起来很好（“实心”形状可以定义为具有低周长/面积比的形状，这是我们在这里优化的） 。
您可以为TSP使用优化器的任何实现，我非常确定您可以用您选择的语言找到它。
另一个版本（如果在逆时针方向b之前返回true）：
bool lessCcw(const Vector2D ¢er, const Vector2D &a, const Vector2D &b) const
{
// Computes the quadrant for a and b (0-3):
// ^
// 1 | 0
// ---+-->
// 2 | 3
const int dax = ((a.x() - center.x()) > 0) ? 1 : 0;
const int day = ((a.y() - center.y()) > 0) ? 1 : 0;
const int qa = (1 - dax) + (1 - day) + ((dax & (1 - day)) << 1);
/* The previous computes the following:
const int qa =
( (a.x() > center.x())
? ((a.y() > center.y())
? 0 : 3)
: ((a.y() > center.y())
? 1 : 2)); */
const int dbx = ((b.x() - center.x()) > 0) ? 1 : 0;
const int dby = ((b.y() - center.y()) > 0) ? 1 : 0;
const int qb = (1 - dbx) + (1 - dby) + ((dbx & (1 - dby)) << 1);
if (qa == qb) {
return (b.x() - center.x()) * (a.y() - center.y()) < (b.y() - center.y()) * (a.x() - center.x());
} else {
return qa < qb;
}
}
这更快，因为编译器（在Visual C ++ 2015上测试）不会生成跳转到计算dax，day，dbx，dby。这里是编译器的输出程序集：
; 28 : const int dax = ((a.x() - center.x()) > 0) ? 1 : 0;
vmovss xmm2, DWORD PTR [ecx]
vmovss xmm0, DWORD PTR [edx]
; 29 : const int day = ((a.y() - center.y()) > 0) ? 1 : 0;
vmovss xmm1, DWORD PTR [ecx+4]
vsubss xmm4, xmm0, xmm2
vmovss xmm0, DWORD PTR [edx+4]
push ebx
xor ebx, ebx
vxorps xmm3, xmm3, xmm3
vcomiss xmm4, xmm3
vsubss xmm5, xmm0, xmm1
seta bl
xor ecx, ecx
vcomiss xmm5, xmm3
push esi
seta cl
; 30 : const int qa = (1 - dax) + (1 - day) + ((dax & (1 - day)) << 1);
mov esi, 2
push edi
mov edi, esi
; 31 :
; 32 : /* The previous computes the following:
; 33 :
; 34 : const int qa =
; 35 : ( (a.x() > center.x())
; 36 : ? ((a.y() > center.y()) ? 0 : 3)
; 37 : : ((a.y() > center.y()) ? 1 : 2));
; 38 : */
; 39 :
; 40 : const int dbx = ((b.x() - center.x()) > 0) ? 1 : 0;
xor edx, edx
lea eax, DWORD PTR [ecx+ecx]
sub edi, eax
lea eax, DWORD PTR [ebx+ebx]
and edi, eax
mov eax, DWORD PTR _b$[esp+8]
sub edi, ecx
sub edi, ebx
add edi, esi
vmovss xmm0, DWORD PTR [eax]
vsubss xmm2, xmm0, xmm2
; 41 : const int dby = ((b.y() - center.y()) > 0) ? 1 : 0;
vmovss xmm0, DWORD PTR [eax+4]
vcomiss xmm2, xmm3
vsubss xmm0, xmm0, xmm1
seta dl
xor ecx, ecx
vcomiss xmm0, xmm3
seta cl
; 42 : const int qb = (1 - dbx) + (1 - dby) + ((dbx & (1 - dby)) << 1);
lea eax, DWORD PTR [ecx+ecx]
sub esi, eax
lea eax, DWORD PTR [edx+edx]
and esi, eax
sub esi, ecx
sub esi, edx
add esi, 2
; 43 :
; 44 : if (qa == qb) {
cmp edi, esi
jne SHORT $LN37@lessCcw
; 45 : return (b.x() - center.x()) * (a.y() - center.y()) < (b.y() - center.y()) * (a.x() - center.x());
vmulss xmm1, xmm2, xmm5
vmulss xmm0, xmm0, xmm4
xor eax, eax
pop edi
vcomiss xmm0, xmm1
pop esi
seta al
pop ebx
; 46 : } else {
; 47 : return qa < qb;
; 48 : }
; 49 : }
ret 0
$LN37@lessCcw:
pop edi
pop esi
setl al
pop ebx
ret 0
?lessCcw@@YA_NABVVector2D@@00@Z ENDP ; lessCcw
请享用。
- y = |a * b| , x = a . b
- Atan2(y , x)...............................gives angle between -PI to + PI in radians
- (Input % 360 + 360) % 360................to convert it from 0 to 2PI in radians
- sort by adding_points to list_of_polygon_verts by angle we got 0 to 360
最后，您将获得Anticlockwize排序的顶点
list.Reverse（）.................. Clockwise_order