44
3
Graham 扫描算法小结
最好情况、平均情况和最坏情况:
O
(
n
log
n
)
graham(P)
low = point with lowest y coordinate in P
remove low from P
sort P by descending polar angle with respect to low
hull = {P[n-2], low}
for i = 0 to n-1 do
while (isLeftTurn(secondLast(hull), last(hull), P[i])) do
remove last point in hull
add P[i] to hull
remove duplicate last point
return hull
当多个点的
y
坐标值相同时选择
x
坐标最小的点。
P
[0]
的极角最大,
P
[
n
2]
的极角最小。
按照顺时针,从极角最小的点开始顺时针遍历。
如果出现左拐,那么最后一个点必须被删除掉。
因为这个重复点即是
P
[
n
2]
3.5.4 决方案
如果手动计算凸包,应该可以很轻松地处理好各种极端情况。但是如果需要用计算机
语言来描叙每一个步骤,我们可能会觉得比较困难
Graham
扫描算法的关键点在于计
算和最低点的极角大小。一旦计算并且排序之后,算法只需要遍历所有的点,不断地构
建凸包并且根据新发现的信息调整结构即可。代码见例
3-1
3-1
Graham
扫描算法的实现
public class NativeGrahamScan implements IConvexHull {
public IPoint[] compute(IPoint[] pts) {
int n = pts.length;
if (n < 3) {
returnpts;
}
//
如果最后一个点不是最低点,
//
那么找到最低点,然后和数组中最后一个点交换
int lowest = 0;
double lowestY = pts[0].getY();
for (inti = 1; i < n; i++) {
算法基础
45
算法基础
if (pts[i].getY() < lowestY) {
lowestY = pts[i].getY();
lowest = i;
}
}
if (lowest != n - 1) {
IPoint temp = pts[n - 1];
pts[n - 1] = pts[lowest];
pts[lowest] = temp;
}
//
pts
[0...
n
-2]
按照和
pts
[
n
-1]
的极角按照从大到小降序排列
new HeapSort<IPoint>().sort(pts, 0, n - 2,
new ReversePolarSorter(pts[n - 1]));
//
有三个点一定在凸包上,它们分别是
:
//
极角最小点
pts[n-2]
、最低点
pts
[
n
-1]
还有极角最大点
p
[0]
//
初始化凸包,从
pts[n-2]
pts
[
n
-1]
开始
DoubleLinkedList<IPoint> list = new DoubleLinkedList<IPoint>();
list.insert(pts[n - 2]);
list.insert(pts[n - 1]);
//
先处理多点共线的情况
double firstAngle = Math.atan2(pts[0].getY() - lowest,
pts[0].getX() - pts[n - 1].getX());
double lastAngle = Math.atan2(pts[n - 2].getY() - lowest,
pts[n - 2].getX() - pts[n - 1].getX());
if (firstAngle == lastAngle) {
return new IPoint[]{pts[n - 1], pts[0]};
}
//
顺序访问每个点,删掉不正确的点
//
一定会出现某个点
"
向右转
"
//
所以这个
while
循环必然能够结束
for (int i = 0; i < n - 1; i++) {
while (isLeftTurn(list.last().prev().value(),
list.last().value(),
pts[i])) {
list.removeLast();
}
//
将下一个点加入凸包中
list.insert(pts[i]);
}
//
最后一个点是重复的,所以我们只需要从最低的点开始取
n-1
个点即可
IPoint hull[] = new IPoint[list.size() - 1];
DoubleNode<IPoint> ptr = list.first().next();
intidx = 0;
while (idx < hull.length) {
hull[idx++] = ptr.value();
ptr = ptr.next();
}
return hull;
}

Get 算法技术手册(原书第2 版) now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.