上学时曾读过一本算法竞赛书，其中一章介绍几何算法。因为平时很少接触，所以当时在我看来，几何问题都有一种瑰丽神奇的色彩，难度很大而不敢触碰。我一直好奇，计算机只能计算数字，那他是怎样处理图形的呢？
提起几何，我们会想起图形，长度，角度，周长，面积等要素，如果想让计算机认知图形，就必须讲图形数字化，然后运用数形结合的思维去计算。提起来数形结合，我第一反应是解析几何，那是用方程驾驭图形。其实在学习解析几何之前，我们在中学就学到过更简单的数形结合的工具——向量。
向量是既有方向又有大小的量，也叫矢量。两个点之间做减法，就能产生向量，它等于从起点到终点的位移。
关于向量的运算有以下几种：
- 加法
- 减法
- 点积
- 叉积
- 与实数的乘法
- 旋转
加法和减法都可用通过平行四边形法则求解。点积常用作求两个向量之间的夹角[ 0 - π ]。叉积常用来求有向面积。
写到这里不难发现，无论是向量还是解析几何，都是把图形放在坐标系中数字化，通过计算数字来认知图形。
几何中最基本的单元是点。
class Point {
double x;
double y;
private Point(double x, double y) {
this.x = x;
this.y = y;
}
static Point create(double x, double y) {
return new Point(x, y);
}
Vector substract(Point a) {
return new Vector(x - a.x, y - a.y);
}
}
再写一个向量类
class Vector {
double x;
double y;
public Vector(double x, double y) {
this.x = x;
this.y = y;
}
Vector mutiply(double n) {
return new Vector(x * n, y * n);
}
static double dot(Vector v, Vector w) {
return v.x * w.x + v.y * w.y;
}
static double length(Vector v) {
return Math.sqrt(dot(v, v));
}
static double angle(Vector v, Vector w) {
return Math.acos(dot(v, w) / length(v) / length(w));
}
// 根据两角和公式推导
static Vector rotate(Vector v, double rad) {
return new Vector(v.x * Math.cos(rad) - v.y * Math.sin(rad), v.x * Math.sin(rad) + v.y * Math.cos(rad));
}
static double cross(Vector v, Vector w) {
return v.x * w.y - v.y * w.x;
}
static double area(Point a, Point b, Point c) {
Vector v = new Vector(a.x - b.x, a.y - b.y);
Vector w = new Vector(a.x - c.x, a.y - c.y);
return cross(v, w);
}
static Point getLineIntersection(Point p, Vector v, Point q, Vector w) {
Vector u = p.substract(q);
double t = cross(w, u) / cross(v, w);
v = v.mutiply(t);
Point point = create(v.x, v.y);
return create(p.x + point.x, p.y + point.y);
}
}
三角形是最基本的图形，我们可以根据叉积来求出三角形的面积。所以尝试把多边形拆成若干三角形求面积，然后累加得解。
class Polygon {
Point[] points;
public Polygon(Point[] points) {
this.points = points;
}
double area() {
double area = 0.0D;
for (int i = 1; i < points.length - 1; i++) {
area += Vector.area(points[0], points[i], points[i+1]);
}
return area / 2;
}
public static void main(String[] args) {
Point[] points = {create(3, 0), create(1, 2), create(-1, 2), create(-3, 0), create(-1, -2), create(1, -2)};
Polygon polygon = new Polygon(points);
System.out.println(polygon.area());
}
}
测试数据是一个面积是16的六边形。注意测试数据必须按逆时针顺序的各个顶点。如果按顺时针排列，那么得到的是负数。
值得一提，上述代码也可以求非凸多边形的面积，因为求出的面积是有向的，所以外面的部分可以正负抵消。
鸣谢：《算法竞赛入门经典训练指南》，两角和公式_百度百科
