1.3.5 融会贯通
通常，解决某一类问题的算法和解决某一个特定问题的算法是大致相通的。Voronoi图（Preparata and Shamos，1993）是这样一个几何结构——它可以将平面上的点集划分成多个区域，其中每个区域的重心点为输入集P中的点。每个区域Ri中任意一点(x, y)到Pi的距离都比到其他区域的重心点要近。图1-7展示了计算出的Voronoi图。灰色区域是半无限的，并且灰色区域的重心点组成了凸包。由此可以得出以下算法：
- 计算输入集P的Voronoi图。
- 将P中的最低点low作为凸包的起始位置，并从与之相联的区域开始遍历。
- 按顺时针顺序访问共享一条无限长边的邻接区域，并不断将这些区域的重心点加入凸包。
图1-7：由Voronoi图计算而得的凸包
- 不断添加点，直到遍历到起始区域为止。
