点集有很多特征，这里提到的有：最小凸包，最小外接矩形，最大内接三角形，最大内接四边形。

编程里面，如何求取点集的这些特征呢？

预处理知识

• 对于三个点，p0,p1,p2，如何判断以p0为中心，p0p1到p0p2是顺时针还是逆时针？

求向量p0p2与p0p1的叉积，若大于0,则说明是p0p2在p0p1的顺时针方向，若小于0，则说明p0p2在p0p1的逆时针方向。

最小凸包

Graham栈扫描法。

这里有一篇博客对此有比较详细的讨论，并给出比较好的伪代码，这里借鉴一下。

平面上有n个点p0,p1,p2,p3,…,pn，求其最小凸包

GRAHAM-SCAN(Q)
{
     1. 取出所有点钟y坐标最小的点作为初始点p0（如果有y坐标相同的，选择x坐标最小的）
     2. 之后对于所有其他点，以p0为中心，点集中的所有点按关于p0的极角逆时针排序,形成p1,p2,..pn-1（如果有极角重合，保存最远的点）
     3. push(p0,S) 
     4. push(p1,S)
     5. push(P2.S)
     for(i: 3->m)
     {     
           px = nexttoTop(S)
           py = Top(S) 
           do while (如果(py->pi向量)相对于(px->py向量)是顺时针的)
                     pop(S)
                     px = nextotTop(S)
                     py = Top(S)
           push(pi, S);
     }
     return S;
}

最小外接矩形

在上述最小凸包的基础上，进行求取，最小外接矩形

这里就是开始旋转卡壳思想的应用。

首先有一个前提，也是可以证明的，凸包的最小外接矩形，至少有一条边与凸包的一条边重合，这点是可以证明的，但过程比较复杂。

在这个前提下，就可以通过下列为代码进行求解了：

MinRec(Q)
{
    Rec=MAXINT
    for i=0:n
        Pick pipi+1 作为矩形的一条边
        依次找投影在这条边上最左边/最右边以及距此边最远的点，作出矩形
        计算面积Si_i+1,如果Si_i+1<Rec，则 Rec=Si_i+1，并记录该边与另外三点
    end
}

上述求解过程，还可以优化。

在找 最左边/最右边/最远 的三点时，对于固定一条边pipi+1而言，从点pi+2逆时针一直找到pi-1，点到边的距离都是先增大，再减小，在该边上最左边/最右边的投影也是先增大后减小的。所以，保存这三点后，下一次计算，找最左边/最右边/最远 的三点时，就可以分别以上次找到的三点为起点，进行寻找。这里可以减去很多计算。

最大内接三角形

最大内接三角形 同样应用 旋转卡壳 的思想

MaxTrangle(Q)
{
    选p0,p1,p2三点，构成三角形；
    1, 固定p0,p1，移动p2，找到能构成的最大三角形p0p1p2'；
    2, 固定p0p2'，移动p1，找到能构成的最大三角形p0p1'p2'；
    3, 固定p1'p2'，移动p0,找到能构成的最大三角形p0'p1'p2'；
    重复1～3，直至三角形面积不再增大
}

最大内接四边形

最大内接四边形， 同样应用 旋转卡壳 的思想

MaxSquare(Q)
{
    选p0,p1,p2,p3三点，构成三角形；
    1, 固定p0,p1,p2，移动p3，找到能构成的最大四边形p0p1p2p3'；
    2, 固定p0,p1,p3'，移动p2，找到能构成的最大四边形p0p1p2'p3'；
    3, 固定p0,p2',p3'，移动p1,找到能构成的最大四边形p0p1'p2'p3'；
    4, 固定p1',p2',p3'，移动p0,找到能构成的最大四边形p0'p1'p2'p3'；
    重复1～4，直至四边形面积不再增大
}

旋转卡壳的思想在求点集的集合特征上有较为广泛的应用，在求得凸包的基础上，可以方便的求取最小外接矩形/最大内接三角形/最大内接四边形。

当然，以上都是伪代码，具体实现，还有一些边界条件得注意。