优化顺时针排序算法

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结构是一个简单的结构（或类），具有两个公共成员x和y，以及一个小于运算符 (an operator <)，该运算符基于xfirst 和then非常简单地比较它们y。
3. 我相信上面代码的运行时间是O(N*log(N))，但它肯定不比O(N^2)差。
4. 返回的点将按顺时针顺序排列。如果你想逆时针旋转，你只需要改变最后两行。
5. 此代码不会处理所有点具有相同 X 坐标的情况（我认为！）
6. 除此之外，这是一个实用且快速且简单的 2D 凸包实现。
7. 如果输入中存在位于同一行的连续点，则此实现会将它们删除。如果您不想这样做，可以将循环中的<= 0和测试分别替换为和。>= 0while< 0> 0

让我强调这一点：虽然上面的代码是 CH 实现，但您可以使用它来按顺时针缠绕顺序对点进行排序（如果它们已经形成凸包）。