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
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]

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.