GIS基础-分割合并算法的凸壳生成算法

    在上文中介绍了生成D_三角网时需要用到凸壳生成算法，这里做个具体介绍。

     凸壳的定义

     凸壳是数据点的自然极限边界，为包含所有数据点的最小凸多边形，连接任意两点的线段完全位于该凸多边形中，同时其区域面积达到最小值。

     凸壳生成的格雷厄姆算法

     S1 找到点集中纵坐标最小的点P1

     S2 将P1与其它点用线段连接，并计算这些线段的水平夹角

     S3 按夹角大小对数据点排序；如夹角相同，则按距离排序，得到P1，P2，… ，Pn.

     S4 依次连接点，得到一多边形。循环删除多边形的非凸顶点得到点集的凸壳。