按顺时针顺序排序点？

Question

给定一个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

Answer 1

首先,计算中心点.然后使用您喜欢的任何排序算法对点进行排序,但使用特殊比较例程来确定一个点是否小于另一个点.

您可以通过以下简单计算检查一个点(a)是否位于另一个点(b)的左侧或右侧(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变量属于能够保存执行计算结果的类型.

如果你想要实现看起来坚固,尽可能凸起的东西,那么我想你正在寻找一个凸面船体.您可以使用Graham Scan计算它.在此算法中,您还必须从特殊轴心点开始顺时针(或逆时针)对点进行排序.然后每次重复简单的循环步骤,检查是否向左或向右转向凸包添加新点,此检查基于十字产品,就像上面的比较函数一样.

编辑:

添加了一个if语句if (a.y - center.y >= 0 || b.y - center.y >=0),以确保具有x = 0和负y的点从远离中心的点开始排序.如果您不关心同一'小时'的点数顺序,您可以省略此if语句并始终返回a.y > b.y.

修正了添加-center.x和的第一个if语句-center.y.

添加了第二个if语句(a.x - center.x < 0 && b.x - center.x >= 0).这是一个明显的疏忽,它失踪了.现在可以重新组织if语句,因为某些检查是多余的.例如,如果第一个if语句中的第一个条件为false,则第二个if的第一个条件必须为true.但是,为了简单起见,我决定保留代码.编译器很可能会优化代码并产生相同的结果.

Answer 2

您要求的是一个称为极坐标的系统.从笛卡尔坐标到极坐标的转换很容易用任何语言完成.公式可以在本节中找到.

我不认识Lua,但此页面似乎提供了此转换的代码段.

转换为极坐标后,只需按角度θ进行排序.

Answer 3

解决问题的一个有趣的替代方法是找到旅行商问题(TSP)的近似最小值,即.连接所有积分的最短路线.如果你的点形成凸形,它应该是正确的解决方案,否则,它应该仍然看起来很好("实心"形状可以定义为具有低周长/面积比的形状,这是我们在这里优化的) .

您可以为TSP使用优化器的任何实现,我非常确定您可以用您选择的语言找到它.