幾何演算法：求多邊形面積

上學時曾讀過一本演算法競賽書，其中一章介紹幾何演算法。因為平時很少接觸，所以當時在我看來，幾何問題都有一種瑰麗神奇的色彩，難度很大而不敢觸碰。我一直好奇，計算機只能計算數字，那他是怎樣處理圖形的呢？

提起幾何，我們會想起圖形，長度，角度，周長，面積等要素，如果想讓計算機認知圖形，就必須講圖形數字化，然後運用數形結合的思維去計算。提起來數形結合，我第一反應是解析幾何，那是用方程駕馭圖形。其實在學習解析幾何之前，我們在中學就學到過更簡單的數形結合的工具——向量。

向量是既有方向又有大小的量，也叫矢量。兩個點之間做減法，就能產生向量，它等於從起點到終點的位移。

關於向量的運算有以下幾種：

1. 加法
2. 減法
3. 點積
4. 叉積
5. 與實數的乘法
6. 旋轉

加法和減法都可用通過平行四邊形法則求解。點積常用作求兩個向量之間的夾角[ 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的六邊形。注意測試數據必須按逆時針順序的各個頂點。如果按順時針排列，那麼得到的是負數。

值得一提，上述代碼也可以求非凸多邊形的面積，因為求出的面積是有向的，所以外面的部分可以正負抵消。

鳴謝：《演算法競賽入門經典訓練指南》，兩角和公式_百度百科

推薦閱讀：