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

• 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