小编trm*_*mag的帖子

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

我已经编写了一些代码来计算给定随机点集的凸包.为了比较的目的,我制作了自己的慢速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; …