求解2维凸包问题
2020-12-02 本文已影响0人
bazinga_dmc
参照《数据结构、算法与应用（c++语言描述）》书中的算法，2维凸包求解分为三步：
-
处理退化情况（点集S的个数小于等于2的情形）
-
选定点集S内的一点，根据点集内所有点与之形成的极角由小到大排序（极角相同的点由近到远排序）
-
从y轴最小的点开始循环处理排序后的点集S，删除非极点的点
利用双向循环链表实现，算法的核心在于如何判断三个点的逆时针夹角是否小于或等于180度（三个点为p1,p2,p3，形成的向量为v1（p2 - p1）和v2（p3 - p2））。如果三个点逆时针夹角小于或等于180度，根据右手定则和v1、v2所指的方向，可知v1和v2的向量积方向应指向坐标轴的负向，即v1和v2的向量积不大于0）。完整代码传送门。
原书中 Step3（删除非极点的点） 算法似乎有问题，原步骤如下：
当初始的x,rx,rrx逆时针夹角小于或等于180度时，rx = x（即rx = p），for循环直接退出，未达到删除非极点的点的目的。修改后的代码片段如下（当将链表遍历一圈发现均为有效极点时才退出循环）：
