按顺时针顺序排序点? [英] Sort points in clockwise order?

问题描述

给定一个 x,y 点数组，我如何按顺时针顺序(围绕它们的整体平均中心点)对该数组的点进行排序?我的目标是将这些点传递给一个线创建函数，最终得到一个看起来相当实心"的东西，尽可能凸出，没有相交的线.

Given an array of x,y points, how do I sort the points of this array in clockwise order (around their overall average center point)? My goal is to pass the points to a line-creation function to end up with something looking rather "solid", as convex as possible with no lines intersecting.

对于它的价值，我使用的是 Lua，但任何伪代码都会受到赞赏.

For what it's worth, I'm using Lua, but any pseudocode would be appreciated.

更新:作为参考，这是基于 Ciamej 出色答案的 Lua 代码(忽略我的app"前缀):

Update: For reference, this is the Lua code based on Ciamej's excellent answer (ignore my "app" prefix):

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

推荐答案

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

First, compute the center point. Then sort the points using whatever sorting algorithm you like, but use special comparison routine to determine whether one point is less than the other.

您可以通过这个简单的计算来检查一个点 (a) 相对于中心是在另一个 (b) 的左侧还是右侧:

You can check whether one point (a) is to the left or to the right of the other (b) in relation to the center by this simple calculation:

det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y)

如果结果为零，则它们与中心在同一条线上，如果为正或负，则在一侧或另一侧，因此一个点将在另一个之前.使用它，您可以构建一个小于关系来比较点并确定它们应该出现在排序数组中的顺序.但是您必须定义该顺序的开始位置，我的意思是起始角度是什么角度(例如 x 轴的正半部分).

if the result is zero, then they are on the same line from the center, if it's positive or negative, then it is on one side or the other, so one point will precede the other. Using it you can construct a less-than relation to compare points and determine the order in which they should appear in the sorted array. But you have to define where is the beginning of that order, I mean what angle will be the starting one (e.g. the positive half of x-axis).

比较函数的代码如下所示:

The code for the comparison function can look like this:

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 点开始顺时针排列点.同一小时"上的点将从离中心较远的点开始排序.

This will order the points clockwise starting from the 12 o'clock. Points on the same "hour" will be ordered starting from the ones that are further from the center.

如果使用整数类型(在 Lua 中并不真正存在)，您必须确保 det、d1 和 d2 变量属于能够保存执行计算结果的类型.

If using integer types (which are not really present in Lua) you'd have to assure that det, d1 and d2 variables are of a type that will be able to hold the result of performed calculations.

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

If you want to achieve something looking solid, as convex as possible, then I guess you're looking for a Convex Hull. You can compute it using the Graham Scan. In this algorithm, you also have to sort the points clockwise (or counter-clockwise) starting from a special pivot point. Then you repeat simple loop steps each time checking if you turn left or right adding new points to the convex hull, this check is based on a cross product just like in the above comparison function.

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

Added one more if statement if (a.y - center.y >= 0 || b.y - center.y >=0) to make sure that points that have x=0 and negative y are sorted starting from the ones that are further from the center. If you don't care about the order of points on the same 'hour' you can omit this if statement and always return a.y > b.y.

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

Corrected the first if statements with adding -center.x and -center.y.

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

Added the second if statement (a.x - center.x < 0 && b.x - center.x >= 0). It was an obvious oversight that it was missing. The if statements could be reorganized now because some checks are redundant. For example, if the first condition in the first if statement is false, then the first condition of the second if must be true. I decided, however, to leave the code as it is for the sake of simplicity. It's quite possible that the compiler will optimize the code and produce the same result anyway.

这篇关于按顺时针顺序排序点?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！