struct Point 
{
    double x,y;
};    

inline double isLeft( Point P0, Point P1, Point P2 )
{
    return (P1.x - P0.x)*(P2.y - P0.y) - (P2.x - P0.x)*(P1.y - P0.y);
}
 

// simpleHull_2D():
//    Input:  V[] = polyline array of 2D vertex points 
//            n   = the number of points in V[]
//    Output: H[] = output convex hull array of vertices (max is n)
//    Return: h   = the number of points in H[]
int simpleHull_2D( Point* V, int n, Point* H )
{
    // initialize a deque D[] from bottom to top so that the
    // 1st three vertices of V[] are a counterclockwise triangle
    Point* D = new Point[2*n+2];
    int bot = n-2, top = bot+3;   // initial bottom and top deque indices
    D[bot] = D[top] = V[2];       // 3rd vertex is at both bot and top
    if (isLeft(V[0], V[1], V[2]) > 0) {
        D[bot+1] = V[0];
        D[bot+2] = V[1];          // ccw vertices are: 2,0,1,2
    }
    else {
        D[bot+1] = V[1];
        D[bot+2] = V[0];          // ccw vertices are: 2,1,0,2
    }

    // compute the hull on the deque D[]
    for (int i=3; i < n; i++) {   // process the rest of vertices
        // test if next vertex is inside the deque hull
        if(i>5)
        {
            printf(" %.2lf %.2lf :  %.2lf %.2lf - %.2lf %.2lf\n",D[bot].x,D[bot].y,D[top].x,D[top].y);
           printf(" i = %d, top = %d, bot = %d\n",i,top,bot);
        }    
        if ((isLeft(D[bot], D[bot+1], V[i]) > 0) &&
            (isLeft(D[top-1], D[top], V[i]) > 0) )
                continue;         // skip an interior vertex

        // incrementally add an exterior vertex to the deque hull
        // get the rightmost tangent at the deque bot
        while (isLeft(D[bot], D[bot+1], V[i]) <= 0)
            ++bot;                // remove bot of deque
        D[--bot] = V[i];          // insert V[i] at bot of deque

        // get the leftmost tangent at the deque top
        while (isLeft(D[top-1], D[top], V[i]) <= 0)
            --top;                // pop top of deque
        D[++top] = V[i];          // push V[i] onto top of deque
        printf(" i = %d,  bot = %d,  top = %d, n = %d\n",i,bot,top,n);
        for(int j = bot; j<= top; j++)
        {
            printf(" %.3lf  %.3lf\n",D[j].x,D[j].y);
        }    
    }

    // transcribe deque D[] to the output hull array H[]
    int h;        // hull vertex counter
    for (h=0; h <= (top-bot); h++)
        H[h] = D[bot + h];

    delete D;
    return h-1;
}

• 怎么连最简单的凸包都算不出呢，我对照算法书，也想不明白？ (2649) sunmoonstar_love 2005-08-11 18:48:33
• 汗……我一看就知道你的Melkman是哪里来的了…… (2649) Ikki 2005-08-11 18:49:41
  • Melkman算法是求凸多边形的凸包，而不是点集的凸包，先对点排序就可以了 (0) Ikki 2005-08-11 18:50:08
    • 不好意思，说错了……不是“凸多边形”，就是至少要有个“形” (0) Ikki 2005-08-11 18:50:26
      • 是简单多边形的凸包…… (0) Ikki 2005-08-11 18:51:14
        • 晕，书上说输入一个点，就构成当前所有点的凸包，还可以实现在线算法？不是么？ (0) sunmoonstar_love 2005-08-11 18:56:29
          • 是我看错了 (0) sunmoonstar_love 2005-08-11 18:59:57
            • 乱用算法，一看O(n)的，就拿过来用了 (0) sunmoonstar_love 2005-08-11 19:00:41