对于什么是值得的，我使用Lua，但任何伪代码将不胜感激。非常感谢任何帮助！
更新：为了参考，这是基于Ciamej的优秀答案(忽略我的“app”前缀)的Lua代码：
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(ay – center.y> = 0 || by – center.y> = 0)，以确保具有x = 0和负y的点从进一步从中心。如果你不关心在同一’小时’点的顺序，你可以省略这个if语句，并总是返回a.y>通过。
通过添加-center.x和-center.y更正了第一个if语句。
添加了第二个if语句(a.x – center.x< 0& b.x - center.x> = 0)。这是一个明显的疏忽，它失踪了。 if语句现在可以重新组织，因为一些检查是多余的。例如，如果第一个if语句中的第一个条件为false，则第二个if的第一个条件必须为true。然而，我决定离开代码，因为它是为了简单。很可能编译器将优化代码并产生相同的结果。