三角剖分（triangulation）

電腦極擅長處理三角形，對其他一切則笨拙。三角形是最簡單的平面形狀——三個點，永遠共面、永遠凸——所以要讓複雜形狀變得可計算，第一步幾乎總是把它切成三角形。三角剖分正是如此：把一個多邊形、一個曲面、或一組點分割成一堆互不重疊、邊對邊拼合、並覆蓋整個區域的三角形。

對一個簡單多邊形（其邊界不自交者），三角剖分意味著只用對角線——多邊形內兩角之間且留在內部的直線——把它切成三角形，使任兩個三角形都不重疊，且合起來填滿多邊形。一個俐落的事實釘住了個數：一個有 n 個頂點的簡單多邊形「永遠」剖分成恰好 n - 2 個三角形，不管怎麼分，並使用 n - 3 條對角線。最簡單的演算法是「剪耳法」：一隻耳是由三個連續頂點構成、且完全落在多邊形內的三角形；反覆剪掉一隻耳，每次使多邊形少一個頂點，直到只剩一個三角形。雙耳定理保證每個簡單多邊形（至少四個頂點）都至少有兩隻耳，所以剪耳法永遠不會卡住。更聰明的方法能在與 n 成正比的時間內剖分簡單多邊形，並在 n log n 內剖分點集。

三角剖分支撐著大量的實務計算：電玩或電影中每一個三維模型都是三角形的網格；有限元素工程、地形繪製、著名的美術館定理（關於守衛擺放）、以及面積計算，全都由三角剖分起步。幾個誠實的重點。第一，一個區域通常有「許多」有效的三角剖分——三角形的個數固定為 n - 2，但你挑哪些對角線並不固定，而不同的選擇品質迥異（這正是德勞內三角剖分發揮價值之處，選的是胖三角形那種）。第二，帶「洞」的多邊形，或非平面的曲面，需要更謹慎的定義與演算法；乾淨的 n - 2 規則專指沒有洞的簡單多邊形。