1.3.1 贪心算法
以下的贪心算法展示了如何找到凸包上的每个点：
- 删除P中的最低点low——low必须在凸包上。
- 垂直画一条穿过点low的直线，将剩余的n－1个点分别和点low连线，以垂直直线右侧的点的夹角为正值降序排列，夹角的范围是从90皛－90啊n-2是最右侧的点，而P0是最左侧的点。图1-3中显示了垂直线以及每个点与其的夹角。
- 以{Pn-2, low, P0}这个顺序组成的点集为基础，在剩余的点中选择可以组成凸包的点——从P1开始，将每个点尝试加至这个点集的尾部，如果这个点集的最后三个点组成的两条线段向左拐，那么就需要移除这个错误的点。
- 在访问完所有的点之后，就得到了一个凸包，如图1-3所示。
图1-3：使用贪心算法得到的凸包
