按顺时针顺序排序点？

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

您要求的是一个称为极坐标的系统。从笛卡尔坐标到极坐标的转换很容易用任何语言完成。公式可以在本节中找到。我不认识Lua，但此页面似乎提供了此转换的代码段。转换为极坐标后，只需按角度θ进行排序。

Answer 2

解决问题的一个有趣的替代方法是找到旅行商问题（TSP）的近似最小值，即。连接所有积分的最短路线。如果你的点形成凸形，它应该是正确的解决方案，否则，它应该仍然看起来很好（“实心”形状可以定义为具有低周长/面积比的形状，这是我们在这里优化的） 。您可以为TSP使用优化器的任何实现，我非常确定您可以用您选择的语言找到它。