按顺时针顺序排序点？

小编典典

按顺时针顺序排序点？

all

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

阅读 89

2022-08-19

共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。

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

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

2022-08-19