按顺时针顺序对点排序？

一尘不染

按顺时针顺序对点排序？

algorithm

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

阅读 652

2020-07-28

共1个答案

一尘不染

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

您可以通过以下简单计算来检查相对于中心的点（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 (a.y - center.y >= 0 || b.y - center.y >=0)，以确保具有x =
0和负y的点从与中心更远的点开始排序。如果您不在乎同一“小时”上的点顺序，则可以忽略此if语句，并始终返回a.y > b.y。

更正了第一个if语句，添加了-center.x和-center.y。

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

2020-07-28