1.3.2 分治算法

我们也可以将点按x坐标从左到右排序（如果x坐标相同，就按照y坐标排序），就能将这个问题分成两个稍微小一点的子问题。首先可以从点p0到pn-1，按照从左到右、顺时针的顺序计算出一个上半部分凸包，然后用同样的方法从pn-1到p0，按照从右到左、同样是顺时针的顺序计算出下半部分凸包。凸包扫描算法（将在第9章中介绍）可以计算出这些半凸包（见图1-4），然后将结果合并在一起生成最终的凸包。