凸包问题

凸包问题

---

# 故事

这些天想到了某某编程问题，联想到了凸包问题……犹记得当年，我还在大学时，学习《算法分析与设计》课程过程，参与ACM程序设计过程，均面对过凸包问题，回忆那时光还是比较清晰的，毕竟日子还未曾久远……但是，尝试想起具体的凸包问题及其解决方案（算法），却真的有些模糊了啊。不行…我需找时间回头学习之，所以，自己需要花时间去查查书，翻翻曾经的测试代码……再回过头来整理了下，这样才再次清晰了，温故而知新啊，知新啊……

那就稍微梳理，博客一篇吧。

在此介绍凸包问题的两种解决算法包括, 蛮力法与分治法。

# 蛮力法
 > 蛮力法使用到几何知识:
P1，P2{(x1, y1), (x2, y2)} => ax + by = c
=> {a = y2-y1, b = x1 - x2, c = x1y2 - y1x2}

使用公式ax + by = c可判断点P3(x3, y3)落在{(x1, y1), (x2, y2)}哪边.

蛮力解法步骤：


1. 循环遍历所有的点，找出所有像P1，P2的点，需满足条件：
其他所有的点均分布在直线P1P2同一边，借助以上几何知识。
2. 找出了所有这样的点，那么就完成凸包问题。

蛮力解决方案时间复杂度O(n^3).

# 分治法
 > 分治法使用到几何知识:
{(x1, y1), (x2, y2), (x3, y3)} P1, P2, P3.面积S(P1P2P3)为以下行列式绝对值的一半，
|x1 y1 1|
|x2 y2 1| = x1y2 + x3y1 + x2y3 - x3y2 - x2y1 - x1y3
|x3 y3 1|


P3位于直线P1P2的左侧时，该表达式为正值。
P3位于直线P1P2的右侧时，该表达式为负值。
 该绝对值越大，即P3就与直线P1P2距离越大。

分治解法步骤：


1. 按照X轴（或Y轴）排序点集合S0，得到最小大值P1，Pn，并划分上包，下包不同点集合。
2. 以上包为例，根据以上几何知识，找出上包顶点Pmax即距离P1Pn最远的点，找不到即结束。
3. 继续以P1Pmax和PmaxPn构造上包，递归下去直至找不到上包顶点。得到点集合S1.
4. 下包操作同。得到点集合S2.
5. 合并集合S1, S2, 得到S3即凸包结果.


分治法解决方案时间复杂度O(n^2).

# 附
BTW，详细的算法可以参见《算法分析与设计》3.蛮力法3.3.2凸包问题 & 4.分治法4.6.2凸包问题.

文章描述的两种解法，完整的示例代码可以参见 github I II。