5

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

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

我的问题是，直到 1000 分，我在不到一秒的时间内就有了视觉结果。但是对于 10000 点，需要 15-20 分钟（我还没有等过）。但是，如果我跳过排序代码并让 opengl 显示未排序的凸包顶点，则只需不到一分钟。所以一直以来都是顺时针排序。检查代码（有些名称没有意义，因为它们是在别处定义的）：

// 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 个凸点，或者我缺少什么？

我很感激任何想法，让我知道是否需要包含其他内容。

4

2 回答 2

3

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

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

于 2013-03-10T02:32:36.173 回答
3

您已经实现了冒泡排序，即 O(n 2 )。sort您可以通过使用带有适当比较函子的 STL 来获得 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));
  }
}
于 2013-03-10T03:23:35.030 回答