一个顺时针排序算法的优化

Question

一个顺时针排序算法的优化

5

这是一个与优化相关的问题，我找不到答案。

我编写了一些代码来计算给定随机点集的凸包。为了比较目的，我使用一些旧的OpenGL工具编写了自己的慢速O(n³)算法来可视化它。由于慢凸包算法的性质，点根本没有排序。因此，排序发生在计算CH之后。

我的问题是，对于最多1000个点，我可以在一秒钟内获得视觉效果。但是对于10000个点，需要15-20分钟以上（我没有等超过那个时间）。但是如果跳过排序代码，让opengl显示未排序的凸包顶点，则只需不到一分钟。所以这就是吃掉所有时间的ClockWise排序的原因。请检查代码（某些名称因在其他地方被定义而不合理）：

// This code actually compares every pair iteratively with respect to the center point
// Consider a given vector "convex", which contains all the convex hull points unsorted

.
..
...
....

int avgx,avgy,sumx=0,sumy=0;

for (int i=0;i<convex.size();i++){
    sumx+=convex.at(i).at(0);
    sumy+=convex.at(i).at(1);
}

avgx=sumx/(convex.size()/2.0); //something like an internal point
avgy=sumy/(convex.size()/2.0);

sort(convex.begin(),convex.end()); //x-sort 
int det,tempx,tempy;
for (int i=0;i<convex.size()-1;i++){
    x1=convex.at(i).at(0);
    y1=convex.at(i).at(1);
    x2=convex.at(i+1).at(0);
    y2=convex.at(i+1).at(1);
    det=(x1-avgx)*(y2-avgy)-(x2-avgx)*(y1-avgy); 
    if (det<0){ //on which side of O-X1 lies X2?
        tempx=convex.at(i).at(0); //swapping points 
        tempy=convex.at(i).at(1);
        convex.at(i).at(0)=convex.at(i+1).at(0);
        convex.at(i).at(1)=convex.at(i+1).at(1);
        convex.at(i+1).at(0)=tempx;
        convex.at(i+1).at(1)=tempy;
        i=-1; //check again the new vector from the beginning
    }
    }
return convex;

显示部分：

glColor3f(0.8, 0.2, 0.2);
glPointSize(3);
glBegin(GL_LINE_LOOP);
    for (int i=0;i<count;i++){
        glVertex2f(convexHull.at(i).at(0),convexHull.at(i).at(1));
    }
glEnd();

根据我所见，通过比较叉积的方法是最有效的。不过，在这之前，我写了一些很糟糕的代码，实际上速度更快，因为它可以在8分钟内给出视觉结果。但我不想保留它，因为它太乱且太长了。这个更干净但非常慢（如果它真的能工作的话...）。那么，我必须等待这么久才能对10000个凸点进行CW排序，还是有什么我不知道的东西？如有需要，请告诉我其他方面的想法或需求。

- trmag

你是说你已经有了一个凸包，只是想将点排序成一个多边形（顺时针）以便可视化吗？这些点是从凸包算法中获取的吗？我问这个问题是因为我所知道的所有凸包算法都会按照多边形的顺序给出点，也就是说，它们会按照多边形中出现的顺序输出点。 - yzt

是的，这些点是我暴力算法的输出结果。这是有意为之的，因为我想将结果与使用 Graham 算法的 GeoLib 库进行比较。 - trmag

2个回答

3

您已经实现了O(n²)的冒泡排序算法，您可以使用STL中的sort函数，并结合适当的比较器来获得O(n log(n))的时间复杂度。以下是一份初步的代码，它使用了一个非传递性的比较器，在我的测试用例中似乎可以正常工作，我认为它通常是正确的:

struct clockwise : public binary_function<vector<int>, vector<int>, bool>
{
  bool operator()(vector<int> A, vector<int> B)
  {
    int det=(A[0]-avgx)*(B[1]-avgy)-(B[0]-avgx)*(A[1]-avgy);
    return(det<0);
  }

  static int avgx, avgy;
};

int clockwise::avgx = 0;
int clockwise::avgy = 0;

...

int clockwise::avgx=sumx/(convex.size()/2.0);
int clockwise::avgy=sumy/(convex.size()/2.0);
sort(convex.begin(),convex.end(), clockwise()); //clockwise-sort

编辑：

非传递性比较器不是一个好主意。这个更可靠：

#include <math.h>

...

struct clockwise : public binary_function<vector<int>, vector<int>, bool>
{
  bool operator()(vector<int> A, vector<int> B)
  {
    return(atan2(A[0]-avgx, A[1]-avgy) < atan2(B[0]-avgx, B[1]-avgy));
  }
}

- Beta

这正是我在寻找的。仅用 3 分钟显示 10000 个点的 CH，GeoLib 则需要 1 分钟。Compare 类使其非常快速和优雅。谢谢。很遗憾我现在还不能给你们两个点赞 :)。 - trmag

好吧，结果有点幸运。有时它会产生一个好的CH，但有时它也会搞砸。我看不出任何模式。确定的是，这不是关于共线点的问题，而是其他什么问题，因为即使在所有点的xs和ys都不同的4点CH上，边缘也会纠缠。使用比较进行排序是否能像冒泡排序一样安全地产生结果？ - trmag

我也会检查一下，但是使用atan2被认为是一种不好的做法吗？它计算了atan2，而我们不需要atan本身，而是两个点的相对位置（甚至不是角度）。我刚开始学习计算几何和图形学，在研究时我读到了一些评论说。 - trmag

@thetrooper：是的，它有点贵，但它可以给我们O(n log(n))。好吧，第三次一定会成功的... - Beta

它很快，但不幸的是有时会纠缠线条。这可能是因为atan2混淆了角度的正负吗？尽管它被设计成不会这样做。无论如何，工作已经完成，但我可能会再次检查它。谢谢。 - trmag

显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- yzt · Accepted Answer

通常来说，这个问题有点奇怪。大多数二维凸包算法（我所知的所有算法）都以顺时针或逆时针顺序给出点（顶点）列表，或者它们可以轻松修改以达到此目的。

无论如何，由于存在多种良好的运行时间为 O(N^2) 或更快的二维凸包确定方法，您可以使用其中之一将数据“排序”为顺时针顺序。我的意思是您可以在数据上运行一个凸包算法，并按照所需的顺序获得结果。

这里是我曾经写过的想必可以实现你想要的功能的示例代码：

#define TURN_DIR(p1,p2,p3)  (p1.x * p2.y - p1.y * p2.x + \
                             p2.x * p3.y - p2.y * p3.x + \
                             p3.x * p1.y - p3.y * p1.x)
#define LAST(cntnr)         (cntnr).back()
#define BEFORE_LAST(cntnr)  (cntnr)[(cntnr).size() - 2]

void ConvexHull (std::vector<Point> & pts)
{
    std::sort (pts.begin(), pts.end());

    std::vector<Point> lower, upper;
    for (unsigned i = 0; i < pts.size(); ++i)
    {
        while (lower.size() > 1 && TURN_DIR(BEFORE_LAST(lower), LAST(lower), pts[i]) <= 0)
            lower.pop_back ();
        while (upper.size() > 1 && TURN_DIR(BEFORE_LAST(upper), LAST(upper), pts[i]) >= 0)
            upper.pop_back ();

        lower.push_back (pts[i]);
        upper.push_back (pts[i]);
    }

    upper.insert (upper.end(), lower.rbegin() + 1, lower.rend() - 1);
    pts.swap (upper);
}

有几个要点需要考虑：

上面的代码在同一个参数pts中接收其输入并返回输出。
Point结构是一个简单的struct（或class），有两个公共成员x和y，以及一个小于运算符（一个operator <）来基于x首先，然后基于y进行简单比较。
我认为以上代码的运行时间为O(N*log(N))，但它绝对不会比O(N^2)更糟。
返回的点将是按顺时针顺序排列。如果你想要逆时针，则只需更改最后两行。
这段代码无法处理所有点具有相同X坐标的情况（我认为！）
除此之外，这是一个功能强大、快速而简单的二维凸壳实现。
如果输入中有连续的点位于同一条直线上，该实现将删除它们。如果你不想这样做，可以用< 0和> 0分别替换while循环中的<= 0和>= 0测试。

让我强调一下：虽然上面的代码是一个凸壳实现，但如果它们已经形成凸壳，你可以使用它来将点按顺时针方向排序。