c++ - 顺时针排序算法的优化

Question

所以这是一个优化问题，我找不到答案。

我已经编写了一些代码来计算一组给定随机点的凸包。出于比较的目的，我制作了自己的慢速 O(n³) 算法，使用一些旧的 OpenGL 东西来可视化它。由于慢速凸包算法的性质，点根本没有排序。所以排序发生在 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 分钟内给了我一个视觉结果。我不想保留它，因为它太脏而且太长，这个更干净但速度很慢(如果它真的有效......)。那么，我是否一定要等待 CW 类的 10000 个凸点，或者我缺少什么？

如果有任何想法，我将不胜感激，如果我需要添加任何其他内容，请告诉我。

Answer 1

总的来说，这个问题有点奇怪。大多数 2D 凸包算法(据我所知)按顺时针或逆时针顺序给出点(顶点)列表，或者可以对其进行微不足道的修改。

在任何情况下，由于有几种良好的 2D 凸包确定方法可以在 O(N^2) 或更快的时间内运行，您可以使用其中一种方法将数据“排序”为顺时针顺序。我的意思是，您可以对数据运行 CH 算法并按照您想要的顺序获得结果。

这是我手边的示例代码，我认为它可以满足您的要求:

#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);
}

有几点需要考虑:

1. 以上代码接收其输入并在同一参数中返回其输出:pts .
2. Point structure 是具有两个公共(public)成员的简单结构(或类)x和 y ，以及一个小于运算符(一个 operator < )，它基于 x 非常简单地比较它们先然后y .
3. 我相信上面代码的运行时间是O(N*log(N))，但肯定不比O(N^2)差.
4. 返回的点将按顺时针顺序排列。如果你想逆时针，你只需要改变最后两行。
5. 此代码不会处理所有点都具有相同 X 坐标的情况(我认为!)
6. 除此之外，这是一个实用且快速且简单的 2D 凸包实现。
7. 如果输入中有位于同一行上的连续点，此实现会将它们移除。如果你不想要那个，你可以替换 <= 0和 >= 0在 while 中进行测试与 < 0 循环和 > 0分别。

我要强调一点:虽然上面的代码是一个 CH 实现，但您可以使用它按顺时针顺序对您的点进行排序(如果它们已经形成一个凸包。)