▶ 书中第六章部分程序，加上自己补充的代码，包括 Graham 扫描生成凸包，计算最远点对
● Graham 扫描生成凸包
package package01; import java.util.Arrays;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Point2D;
import edu.princeton.cs.algs4.Stack; public class class01
{
private Stack<Point2D> hull = new Stack<Point2D>(); public class01(Point2D[] points)
{
if (points == null || points.length == 0)
throw new IllegalArgumentException("argument is null");
int n = points.length;
Point2D[] a = new Point2D[n];
for (int i = 0; i < n; i++)
a[i] = points[i]; Arrays.sort(a); // Y 坐标升序排序，等值的按 X 坐标升序排序，保证 a[0] 为最下最左，a[1] 为
Arrays.sort(a, 1, n, a[0].polarOrder()); // 以 a[0] 为原点，幅角升序排序
hull.push(a[0]); // 第一个点
int k1; // 找到下一个相异点
for (k1 = 1; k1 < n; k1++)
{
if (!a[0].equals(a[k1]))
break;
}
if (k1 == n)
return;
int k2; // 找到下一个非共线点
for (k2 = k1 + 1; k2 < n; k2++)
{
if (Point2D.ccw(a[0], a[k1], a[k2]) != 0)
break;
}
hull.push(a[k2 - 1]); // a[k2-1] 是与 a[0]，a[k1] 共线的最后一个点（也可以先压 a[k1] 然后跳过 a[k2-1]）
for (int i = k2; i < n; i++)
{
Point2D top = hull.pop();
for (; Point2D.ccw(hull.peek(), top, a[i]) <= 0; top = hull.pop()); // 倒数第 2 点、倒数第 1 点和当前点计算三角形面积，逆时针方向为正
// 吐栈吐到这 3 点的面积为正为止，压入倒数第 2 点当前点
hull.push(top);
hull.push(a[i]);
}
assert isConvex();
} public Iterable<Point2D> hull() // 得到凸包的迭代器
{
Stack<Point2D> s = new Stack<Point2D>();
for (Point2D p : hull)
s.push(p);
return s;
} private boolean isConvex() // 检查凸性
{
int n = hull.size();
if (n <= 2) return true; Point2D[] points = new Point2D[n];
int k = 0;
for (Point2D p : hull())
points[k++] = p; for (int i = 0; i < n; i++)
{
if (Point2D.ccw(points[i], points[(i + 1) % n], points[(i + 2) % n]) <= 0)
return false;
}
return true;
} public static void main(String[] args)
{
int n = StdIn.readInt();
Point2D[] points = new Point2D[n];
for (int i = 0; i < n; i++)
{
int x = StdIn.readInt(), y = StdIn.readInt();
points[i] = new Point2D(x, y);
}
class01 graham = new class01(points);
for (Point2D p : graham.hull())
StdOut.println(p);
}
}
● 计算最远点对
package package01; import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Point2D;
import edu.princeton.cs.algs4.GrahamScan; public class class01
{
private Point2D best1, best2;
private double bestDistanceSquared = Double.NEGATIVE_INFINITY; // 当前最远点对距离的平方 public class01(Point2D[] points)
{
if (points == null || points.length <= 1)
throw new IllegalArgumentException("constructor argument is null"); GrahamScan graham = new GrahamScan(points); int m = 0;// 凸包点数
for (Point2D p : graham.hull())
m++;
Point2D[] hull = new Point2D[m + 1]; // 凸包顶点放入 a[1] ~ a[m]
m = 1;
for (Point2D p : graham.hull())
hull[m++] = p;
m--; // m 等于凸包顶点数 if (m == 1) // 所有点都相同
return;
if (m == 2) // 所有点共线
{
best1 = hull[1];
best2 = hull[2];
bestDistanceSquared = best1.distanceSquaredTo(best2);
return;
} int k = 2;
for (; Point2D.area2(hull[m], hull[1], hull[k + 1]) > Point2D.area2(hull[m], hull[1], hull[k]); k++); // a[k] 是距离直线 a[1]a[m] 最远的点 int j = k;
for (int i = 1; i <= k && j <= m; i++) // j 搜索后半部分，i 搜索前半部分
{
update(hull[i], hull[j]); // i 挪动一位，检查 a[i] 和 a[j] 距离是否更大
for (j++; (j <= m) && Point2D.area2(hull[i], hull[i + 1], hull[j]) > Point2D.area2(hull[i], hull[i + 1], hull[j - 1]); j++)
// j 挪动保持 a[j] 远离直线 a[i]a[i+1]
update(hull[i], hull[j]);
}
} private void update(Point2D x, Point2D y)
{
double distanceSquared = x.distanceSquaredTo(y);
if (distanceSquared > bestDistanceSquared)
{
best1 = x;
best2 = y;
bestDistanceSquared = distanceSquared;
}
} public Point2D either()
{
return best1;
} public Point2D other()
{
return best2;
} public double distance()
{
return Math.sqrt(bestDistanceSquared);
} public static void main(String[] args)
{
int n = StdIn.readInt();
Point2D[] points = new Point2D[n];
for (int i = 0; i < n; i++)
{
int x = StdIn.readInt(), y = StdIn.readInt();
points[i] = new Point2D(x, y);
}
class01 farthest = new class01(points);
StdOut.println(farthest.distance() + " from " + farthest.either() + " to " + farthest.other());
}
}