是否按顺时针顺序排序点？
给定一个由x，y点组成的数组，如何按顺时针顺序(围绕它们的总体平均中心点)对该数组中的点进行排序？我的目标是将这些点传递给一个线创建函数，最终得到看起来相当“实心”的东西，尽可能地凸，没有线相交。
值得一提的是，我使用的是Lua，但任何伪代码都会受到欢迎。
app更新：供参考，这是基于Ciamej的优秀答案的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
回答 6
Stack Overflow用户
发布于 2011-08-09 06:26:58
首先，计算中心点。然后使用任何你喜欢的排序算法对点进行排序，但使用特殊的比较例程来确定一个点是否小于另一个点。
您可以通过以下简单计算来检查一个点(a)相对于中心是在另一个点(b)的左侧还是右侧：
det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y)如果结果是0，那么它们从中心开始在同一条线上，如果它是正的或负的，那么它在一边或另一边，所以一个点将在另一个点之前。使用它，您可以构造一个小于关系来比较点，并确定它们在排序数组中的出现顺序。但是你必须定义这个顺序的开始位置，我的意思是开始的角度是什么(例如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。但是，为了简单起见，我决定让代码保持原样。编译器很可能会优化代码并产生相同的结果。
Stack Overflow用户
发布于 2011-08-09 06:31:42
您所要求的是一个称为polar coordinates的系统。从笛卡尔坐标到极坐标的转换在任何语言中都很容易完成。这些公式可以在this section中找到。
在转换为极坐标后，只需按角度θ排序。
Stack Overflow用户
发布于 2011-08-10 23:01:31
你的问题的一个有趣的替代方法是找到旅行商问题(TSP)的近似最小值，即。连接所有点的最短路径。如果你的点形成一个凸起的形状，它应该是正确的解决方案，否则，它应该看起来仍然很好(“实心”形状可以定义为具有低周长/面积比的形状，这是我们在这里优化的)。
您可以为TSP使用任何优化器的实现，我非常肯定您可以在您选择的语言中找到大量的优化器。
https://stackoverflow.com/questions/6989100
复制相似问题