按顺时针顺序排序分？ [英] 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中，但任何伪code将AP preciated。非常感谢您的帮助！

For what it's worth, I'm using Lua, but any pseudocode would be appreciated. Thanks so much for any help!

更新：作为参考，这是一款基于Ciamej的出色答卷的Lua的code（忽略我的应用程序preFIX）：

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)

如果结果是零，那么它们是从中心的同一行，如果它是正或负的，则它是在一侧上或其他的，因此一个点将precede其他。 使用它，你可以构造一个低于关系比较点，决定它们应该出现在排序数组中的顺序。但是，你必须定义在这里是为了一开始，我的意思是什么角度将开始一项（如正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).

在code的比较功能可以是这样的：

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.

如果使用整型（这是不是真的present在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扫描计算它。 在此算法还具有点顺时针（逆时针或）从一个特殊的枢轴点开始进行排序。然后你重复简单的循环步骤，每次检查，如果你左转或右转增加新点的凸包，这个检查是基于跨产品就像在上面的对比功能。

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 cross product just like in the above comparison function.

编辑：

增加了一个if语句如果（AY - center.y＆GT; = 0 ||通过 - center.y＆GT; = 0）来确保点具有x = 0和负y的排序从那些进一步是从中心开始。如果你不关心顺序相同的'小时'点，你可以if语句忽略这一点，总是返回 AY＆GT; 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 order of points on the same 'hour' you can omit this if statement and always return a.y > b.y.

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

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

增加了第二个if语句（AX - center.x℃的＆安培;＆安培; BX - center.x＆GT; = 0）。这是它缺少一个明显的监督。该if语句现在可以进行重组，因为有些检查是多余的。例如，如果在第一if语句的第一条件是第二假，则第一个条件，如果必须为真。然而，我决定，离开code，因为它是为简单起见。这很可能是编译器将优化code，反正产生相同的结果。

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