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

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

凸壳的定义

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

凸壳生成的格雷厄姆算法

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

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

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

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