凸包的Graham算法

  几何背景：点集S的顶点构成了S的一个子集（不必是真子集）。凸包问题有两个变体：1、求得凸包的顶点（极点）2、以某一顺序求得凸包的顶点

考虑从点p1=（x1，y1）到另一个顶点p2（x2，y2）的有向线。如果q=(x3，y3)是另外一个点，角度p1p2q左(右)旋，我们说q在的左(右)边。（如果一个角度小于或等于（大于或等于180，则称其为左(右)旋））。可以通过下列的行列式的值来确定q是否在的左(右)边。如果该行列式为正（负），则q是在的左(右)边，若为零则表示三点在一条直线上，这个测试可以用来确定一个给定点是否在由三个点组成的三角形内，当且仅当p在线段，,的右边时在三角形内，此外，对人和三个点(x1,y1),(x2,y2),(x3,y3),对应的三角形的带符号面积为上式行列式的值的一半。

  Graham算法：如果S为平面内的点的集合，Graham扫描算法从S中找出有最小的y坐标的点p（通过选出最左边的点打破平局）。然后根据点和p连线和正X轴所成的角度将S中的点排序。下图是一个例子

在将点排序后，当扫描从p开始的有序列表时，如果所有这些点都在凸包上，则每三个相继的点会组成一个左旋。另一个方面，如果说有三个相继的点p1，p2，p3组成一个右旋，立即可以去除p2，因为他不可能在包上（算法导论中用了左拐还是右拐来描述，还是此处的描述比较好个人觉得）。注意，因这个店位于p，p1，p3组成的三角形内，所以他将是一个内点。使用上述过程可以去除所有内点，从p开始，一次考虑三个点p1，p2，p3，首先，p1=p，如果这些点组成一个左旋，移动到列表的下一个点，也就是p1=p2等等。如果组成一个右旋，删除p2。通过将p1设为其前驱，在列表中向后移动一个点，当再次到达p时，扫描结束。

主要代码如下

#define NIL 0
struct point {
    float x,y;
    struct point *prev,next;
};

typedef struct point Type;
class PointSet{
    private:
        Tyoe *ptslist;
        //area是计算行列式的值确定左旋还是右旋

        float Area(float,float,float,float,float,float);
        void PrintList(Type *);
        void Scan(Type *);
        void Sort(Type *);
    public:
        PointSet(){ptslist = NIL;}
        void Insert(float a,float b);
        void ConvexHull();
        
};

void PointSet::Scan(Type *){
    Type *p=list,*p1=list,*p2,*p3;
    float temp;
    do{
        p2 = p1->next;
        if(p2->next) p3 = p2->next;
        else p3 = p;
        temp = Area(p1->x,p1->y,p2->x,
                    p2->y,p3->x,p3->y);
        if(temp >= 0.0) p1 = p1->next;
        else{
            p1->next = p3;p3->prev = p1;delete p2;
            p1 = p1->prev;
        }
    }while(!((p3==p)&&temp>=0.0))
}

void PointSet::ConvexHull(){
    Sort(ptslist);
    Scan(ptslist);
    PrintList(ptslist);
}