算法 – 按顺时针顺序排序点？

发布时间：2020-12-14 23:28:04 所属栏目：大数据来源：网络整理

导读：给定一个x，y点的数组，如何按顺时针顺序(围绕它们的整体平均中心点)对该数组的点进行排序？我的目标是将点传递到一个线创建功能，结束了看起来相当“实体”的东西，尽可能凸起，没有线相交。对于什么是值得的，我使用Lua，但任何伪代码将不胜感激。非常感

给定一个x，y点的数组，如何按顺时针顺序(围绕它们的整体平均中心点)对该数组的点进行排序？我的目标是将点传递到一个线创建功能，结束了看起来相当“实体”的东西，尽可能凸起，没有线相交。

对于什么是值得的，我使用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。然而，我决定离开代码，因为它是为了简单。很可能编译器将优化代码并产生相同的结果。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!