《算法技术手册》一1.3.5 融会贯通

1.3.5 融会贯通

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

图1-7：由Voronoi图计算而得的凸包
4. 不断添加点，直到遍历到起始区域为止。