按顺时针顺序对点进行排序? [英] 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 代码(忽略我的应用程序"前缀):

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屋！