第2章圖形處理中的幾何問題2.1圖形坐標系2.2幾何元素的定義及特點2.3平面圖形的幾何性質2.4幾何元素之間的位置判斷2.5幾何元素之間的求交計算2.6多邊形及其凸凹性2.7多邊形的分解與網格劃分

2.1圖形坐標系

對圖形對象的描述，圖形的處理及輸入、輸出，都是在一定的坐標系中進行的。目前，對世界坐標系、用戶坐標系、局部坐標系還沒有統一的定義，各種文獻及圖形軟件中的說法不一。這里從圖形系統的角度提出世界坐標系、局部坐標系、觀察坐標系、設備坐標系、規范化設備坐標系等5種坐標系。在標準圖形系統中，主要坐標系使用的邏輯關系如圖2.1所示。

圖2.1坐標系使用的邏輯關系

在三維坐標系統中，有右手坐標系和左手坐標系之分，通常采用右手坐標系。左手坐標系和右手坐標系的判斷方法有旋向法和三指法。伸開右手，若坐標系的手指間關系符合圖2.2所示的關系則稱為右手坐標系，否則為左手坐標系。

圖2.2右手坐標系的判斷方法

2.1.1世界坐標系

世界坐標系是用戶為繪圖而建立的初始直角坐標系，

為右手坐標系，可以是二維或三維的坐標系。世界坐標系的坐標軸方位是固定的，在顯示屏幕上，一般x軸正向朝右，y軸正向朝上，z軸正向按右手定則垂直于屏幕顯示平面朝外，坐標系的原點由定義的作圖范圍來確定，坐標的取值范圍可以是計算機能夠處理的實數范圍，可根據需要設置。

2.1.2局部坐標系

局部坐標系是用戶在世界坐標系或當前的坐標系中定

義的直角坐標系，為右手坐標系。局部坐標系的坐標原點、坐標軸的方位是任意的。在某些圖形系統中，把局部坐標系稱為用戶坐標系。設立局部坐標系是為了便于作圖。例如，在三維繪圖中，利用局部坐標系可以把較為復雜的三維作圖問題轉化為二維作圖問題。圖2.3為局部坐標系的應用。

圖2.3局部坐標系的應用

2.1.3觀察坐標系

觀察坐標系是以視點為坐標原點的三維左手(或右手)直角坐標系，其中z軸方向為視點與世界坐標系原點(默認情況)或模型上點的連線方向，xy平面(觀察平面，即投影平面)與z軸垂直，如圖2.4所示。

觀察坐標系取為左手系的原因在于:當把觀察平面作為屏幕時，z軸正方向朝向顯示器里的方向符合我們的視覺習慣，越向里表示離我們越遠，z值也就越大。

圖2.4觀察坐標系與世界坐標系

2.1.4設備坐標系

與一個圖形設備(輸入設備或輸出設備)相關聯的直角坐標系稱為設備坐標系。設備坐標系可以是二維坐標系(如二維掃描儀、屏幕、繪圖機、二維打印機等)，也可以是三維坐標系(如三維掃描儀、三維打印機)。圖形的輸出在設備坐標系下進行。設備坐標系的坐標取值范圍與設備的有效幅面和精度有關，為某個整數區間。對點陣圖形顯示器和無筆繪圖機而言，坐標單位是像素(也叫光柵單位)；對筆式繪圖機而言，其坐標單位是步距(也叫脈沖當量)。

點陣圖形顯示器的設備坐標系與屏幕分辨率有關。假定顯示器的分辨率為1024×768，則該顯示器的設備坐標系為:x∈［0，1023］，y∈［0，767］，x、y為整數(代表像素位置)。坐標原點默認情況是在屏幕左上角，如圖2.5(a)所示；坐標原點也可設置在屏幕左下角，如圖2.5(b)所示。

圖2.5屏幕坐標系

2.1.5規范化設備坐標系

坐標取值范圍為0到1.0的坐標系稱為規范化設備坐標系(。規范化設備坐標系為:x∈［0.0，1.0］，y∈［0.0，1.0］，x、y為實數。用戶的圖形處理數據(如對模型投影并經窗口裁剪得到的數據)經歸一化轉換即得規范化設備坐標系中的坐標值。

另外，在一些圖形系統中還使用圓柱面坐標系(ρ-φ-z，ρ、φ為空間點在xOy平面上投影的極坐標，ρ為極徑，φ為極角，z為空間點到xOy平面的距離)和球面坐標系(r-φ-θ，r為空間點到原點的距離，φ為從x軸正向起度量的經度角(0°~360°)，θ為從z軸正向起度量的緯度角(0°~180°))。在某些工程應用中，如三角形區域內物理量的插值計算，還可使用面積坐標等。

2.2幾何元素的定義及特點

1.點點是圖形處理中最基本的元素，分為端點、交點、切點等。在通常的直角坐標系下，二維空間中的點用二元組｛x，y｝或｛x(t)，y(t)｝表示；三維空間中的點用三元組｛x，y，z｝或｛x(t)，y(t)，z(t)｝表示。而在齊次坐標系下，n維空間中的點用n+1維坐標表示。

在自由曲線和曲面的描述中，常用以下三種類型的點：

(1)控制點:用來確定曲線和曲面的位置與形狀，而相應的曲線和曲面不一定經過的點。控制點用于構造逼近曲線、逼近曲面。

(2)型值點:用來確定曲線和曲面的位置與形狀，而相應的曲線和曲面一定經過的點。型值點用于構造插值曲線、插值曲面。

(3)插值點:為提高曲線和曲面的輸出精度，在型值點之間插入的一系列點。

2.邊(線)

邊分為直線邊和曲線邊。直線邊由其端點(起點和終點)定界；曲線邊由一系列型值點或控制點表示，也可用顯式、隱式方程表示。

3.環

環是由有序的有向邊(直線段或曲線段)組成的封閉邊界。環有內、外之分，確定面的最大外邊界的環稱為外環，其邊(或頂點)按逆時針方向排序；而把確定面中內孔或凸臺邊界的環稱為內環，其邊(或頂點)按順時針方向排序。基于這種定義，在面上沿一個環前進，其左側總是面內，右側總是面外。

4.面

面是由一個外環和若干個(包括0個)內環圍成的區域。一個面可以無內環，但必須有一個且只有一個外環。形體中的面有方向性，一般用其外法線矢量方向作為該面的正向。若一個面的外法線矢量向外，此面為正向面；反之，為反向面。區分正向面和反向面在實體造型中的新面生成、真實感圖形顯示等方面都很重要。

5.體

體是由封閉表面圍成的空間，其邊界是有限面的并集。為了保證幾何造型的可靠性和可加工性，要求形體上任意一點的足夠小的鄰域在拓撲上應是一個等價的封閉圓，即圍繞該點的形體鄰域在二維空間中可以構成一個單連通域。我們把滿足這個定義的形體稱為正則形體(或稱為流形物體)。含懸掛邊、懸掛面、懸掛體(以點、邊接觸的體)的形體均不是正則形體。

6.形體定義的層次結構

形體在計算機中可按上述幾何元素分五個層次表示，如圖2.6所示。圖2.6形體的層次表示

2.3平面圖形的幾何性質

1.平面的外法線矢量計算設形體表面外環上三個相鄰頂點依次為P1(x1，y1，z1)、P2(x2，y2，z2)、P3(x3，y3，z3)，則該平面的外法線矢量(按右手定則定方向)為

2.三角形的面積、質心和質量因子的計算

設三角形的三個頂點依次為P1(x1，y1，z1)、P2(x2，y2，z2)、P3(x3，y3，z3)，則有三角形的面積：

其中，ｐ為三角形周長的一半，a、b、c為三邊的邊長。

當α=0時，表示一條直線；當α=1時，表示正三角形，這時質量最好。圖2.7分別為不同三角形的質量因子α的值。在三角形質量判斷中，α的取值由經驗數據決定，一般它的推薦值為α>0.1。

圖2.7不同三角形的質量因子α的值

3.平面凸四邊形的面積、質心和質量因子的計算

2.4幾何元素之間的位置判斷

1.點與點的位置判斷點與點的位置關系主要用于兩點是否重合、兩三角形是否有公共邊的判斷等方面。設空間兩點P1(x1，y1，z1)、P2(x2，y2，z2)，則這兩點之間的距離1為當1＜ε(ε為誤差精度)時，可判定P1、P2兩點是同一點。

2.點與直線段的位置判斷

點與直線之間的位置關系用于點是否在直線上、三點是否共線以及三點是否能構成三角形的判斷等方面。

設點為P(x，y，z)，直線段端點為P1(x1，y1，z1)、P2(x2，y2，z2)，則點P到線段P1P2的距離為

3.點與平面的位置判斷

點與平面之間的位置關系用于四點共面、兩相鄰三角形是否可合并構成平面四邊形的判斷等方面。

已知平面上不共線的三點為P1(x1，y1，z1)、P2(x2，y2，z2)、P3(x3，y3，z3)，空間點為P(x，y，z)，設ｑ為點到平面的代數距離，則有

若｜ｑ｜≤ε(ε為誤差精度)，則點P在不共線的三點P1、P2、P3所確定的平面上。

4.點在多邊形內部的判斷

判斷平面上一個點是否包含在同平面的一個多邊形內有多種算法，經典方法有叉積判斷法、夾角之和檢驗法和交點計數檢驗法。

1)叉積判斷法

叉積判斷法適用于空間平面上一點在同一平面內的一個凸多邊形內的判斷。如圖2.8所示，設P0為平面上一點，P1P2P3P4為凸多邊形。由于空間點可用位置矢徑表示，令Vi=Pi-P0(i=1，2，…，n)，Vn+1=V1，一般情況下，點P0在多邊形內的充要條件是叉積Vi×Vi+1

(i=1，2，…，n)的符號相同。特殊地，當Vi×Vi+1=0(點P0在多邊形的邊上或邊的延長線上)時，認為點在多邊形外。

圖2.8叉積判斷法

2)夾角之和檢驗法

如圖2.9所示，假設平面上有點P0和多邊形P1P2P3

P4P5，將點P0分別與Pi相連，構成向量Vi=Pi-P0(i=1，2，…，n)，Vn+1=V1。假設∠Pi

P0Pi+1=αi(Pn+1=P

1)，則它可通過下列公式計算：

αi的正負號由Vi×Vi+1的正負決定。

圖2.9夾角之和檢驗法

3)交點計數檢驗法

交點計數檢驗法適用較廣，特別適用凹多邊形及帶孔多邊形情況下的點是否在多邊形內的判斷。判斷的基本思想是:從被判斷點(x0，y0)向右作一射線至無窮遠，即射線方程為

求射線與多邊形相交時的交點個數。

如果交點個數為奇數，則點在多邊形之內；如果交點

個數為偶數(含0)或特殊情況時點在多邊形邊上，則點在多邊形之外。如圖2.10(a)所示，射線a、c、d與多邊形相交，其交點個數分別為2、2、4，為偶數，可以直接判斷A、C、D三點均在多邊形之外；而射線b、e分別交多邊形的交點數為3和1，所以也可直接判斷B、E兩點均在多邊形之內。

但當圖2.10(b)中的射線f、g、h、i、j均通過多邊形的頂點、圖2.10(a)中射線ｋ與邊重合時，交點計數應特殊處理。如射線

g與多邊形的邊6、邊7交于一頂點，這時如果將交點計數為2，則會誤判斷點G在多邊形之外；如果將交點計數為1，則又會誤判斷點F在多邊形之內(射線f與邊7、邊8交于一頂點)。

圖2.10交點計數檢驗法

參見圖2.11，具體計數時，當兩條邊的另兩個端點的y值均大于y0，即兩邊均處于射線上方時，計數為2，如圖2.11(a)所示；當兩條邊另兩端點的y值均小于y0，即兩條邊均處在射線下方時，交點計數為0，如圖2.11(b)所示；當兩條邊的兩端點分布在射線兩側時，交點計數為1，如圖2.11(c)所示。當邊與射線重合時，可將邊視作壓縮為一點，按圖2.11(d)、(e)、(f)類似處理。

圖2.11交點計數方法

5.點在多面體內的判斷

1)點在凸多面體內的判斷

設點P為空間點，Ni是凸多面體每個面的外法矢量，Pi是面上一點(常取面的頂點)，若滿足Ni·(P-Pi)＜0，則點P在多面體內。

2)點在一般多面體內的判斷

點在一般多面體內的判斷類似于點在多邊形內部判斷的交點計數法。

2.5幾何元素之間的求交計算

幾何元素之間的求交計算主要有兩直線段求交、直線段與平面求交、平面與平面求交等，其應用十分廣泛，除用于點在多邊形及多面體內的包含性判斷外，還用于區域填充、二維或三維圖形裁剪、二維或三維圖形布爾運算、投影求取、多邊形或多面體分解、對稱計算、幾何量或物理量插值計算、消隱計算、光線跟蹤計算等。

1.空間平面上兩直線段的求交

兩條線段的求交分兩步，第一步為快速排斥判斷及跨立判斷以確定兩線段是否相交；第二步為對相交線段求交點。設線段P1P2、Q1Q2在同一平面上，兩線段求交算法的步驟如下。

1)快速排斥判斷

設以線段P1P2為對角線的軸向矩形(矩形邊與坐標軸平行)為R、以線段Q1Q2為對角線的軸向矩形為T，如果R和T分離不相交，顯然兩線段不會相交，則求交結束；否則(R和T相交或內含情況，這時線段可能相交，也可能不相交)進行跨立判斷。

2)跨立判斷

如果兩線段相交，則兩線段必然相互跨立對方(一條線段的兩個端點在另一條線段的兩側)，如圖2.12所示。

圖2.12跨立驗證

3)求取交點

線段P1P2、Q1Q2的方程用矢量形式分別表示為

2.直線段與平面的求交

1)矢量求解方法

考慮直線段與無界平面的求交問題，如圖2.13所示。

給定直線段的兩個端點，則直線段方程可表示為

給定平面上三個點，則平面方程可表示為

圖2.13直線段與平面的求交

2)代數求解方法

其中：

2.14直線與空間平面的交點

3.平面與平面的求交

平面是最常用的一種面。在進行包含平面的實體之間的布爾運算、進行實體的剖切運算(以便得到實體的剖面圖)或利用掃描線進行光照計算及消隱時，都涉及平面與平面的求交問題。

1)基于線面求交的面面求交算法

設兩個一般多邊形分別記為A和B，面面求交算法包括下面四步：

(1)將A的所有邊分別與B求交(利用直線段與平面求交，直線段落在平面上時不計交點)，求出所有有效交點(既在多邊形A的邊上(檢查參數范圍判斷)，又在多邊形B內(利用點在多邊形內的判斷)的點)；

(2)將B的所有邊分別與A求交，求出所有有效交點(既在多邊形B的邊上，又在多邊形A內的點)；

(3)將所有交點依次按x、y、z的大小進行排序，即先按x坐標排序，然后對x坐標相同的交點再按y坐標排序，最后對x、y相同的交點按z坐標排序；

(4)將每對交點(如交點1、交點2為一對，交點3、交點4為一對，依次類推)的中點與A和B進行包含性檢測(利用點在多邊形內的判斷)，若該中點既在A中又在B中，則該對交點為A和B的一條交線段。

2)基于線線求交的面面求交算法———課程思政案例

基于線線求交的面面求交算法是編者已授權的國家發明專利。此案例的創新思路在于抓住了平面與平面的理論交線這個兩個平面之間的橋梁，進而可以將線面求交轉化為線線求交并利用交點在理論交線的位置參數(直線參數方程中的參數)對交點排一次序即可。此案例旨在培養創新思維能力和創新精神。

設兩個一般多邊形分別記為A和B，參見圖2.15、圖2.16，算法步驟如下：

(1)求取A和B的理論交線，并取足夠長度形成理論交線段；

(2)分別在A和B上進行理論交線段與多邊形的邊線段求交(利用直線段與直線段求交)，線段重合時不計交點，以避免在進行三維實體布爾運算時出現重合或懸掛的線、面；

(3)分別對A和B沿理論交線對交點按位置參數從小到大排序并形成交點組(如圖2.15所示，A的交點11、9為一組，交點10、12為一組；B的交點9′、11′為一組，交點12′、10′為一組)，剔除端點重合的交點組，以避免在三維實體布爾運算時出現孤立的點或懸掛的線；

(4)對A和B的交點組按位置參數求交集得到可能交線段(如圖2.15所示的線段9′-9、10-10′，圖2.16所示的線段1-2、3-4、5-6)；

(5)對可能交線段的中點進行A和B的包含性檢測以確定最終交線段，這一步主要適用于有內環且內環邊在兩個平面理論交線上時的處理，如圖2.16所示。

按此算法，圖2.15的最終交線段為9′-9、10-10′，圖2.16所示最終交線段為1-2、5-6。圖2.15面面求交示例

圖2.16面面求交奇異情況

4.矢量表示點批判學習案例

比較有影響的國外專著《計算機圖形學幾何工具算法詳解》的9.2.1節講平面方程時，平面上的點用P=dn表示，其中n為平面法線矢量，d為常數，即點用矢量表示。11.5.1節講兩個平面求交時，直線上的點用P=an1+bn2表示，其中n1、n2分別為兩個平面的法線矢量，a、b為常數，an1+bn2的結果仍為矢量，即點也用矢量表示。

2.6多邊形及其凸凹性2.6.1基本概念1.簡單多邊形設Vi(i=1，2，3，…，n)是給定封閉多邊形的n個頂點。若同時滿足以下條件：(1)對任意的i≠j(i，j=1，2，3，…，n)，存在Vi≠Vj，即所有頂點均不相同；(2)任何頂點都只屬于它所在的邊；(3)任何兩條非相鄰邊都不相交。則稱該多邊形為簡單多邊形。

圖2.17為簡單多邊形，圖(a)是一個簡單單連通多邊形(不帶內環)，圖(b)是一個簡單多連通多邊形(帶內環)。圖2.17簡單多邊形

圖2.18不是簡單多邊形，其中(a)不滿足第(1)條，(b)不滿足第(2)、(3)條。圖2.18非簡單多邊形

2.簡單多邊形頂點凸凹性的定義、凸角與凹角、凸多邊形與凹多邊形

設V1，…，Vn是一個簡單多邊形。對于任一頂點Vi(i=1，2，3，…，n)，若線段Vi

-

1Vi(令V0=Vn)與線段ViVi+1(令Vn+1=V1)所形成的內角(由該多邊形所圍成有界區域內兩邊所夾的角)是一個小于180°的角，則稱Vi是凸頂點；若內角是一個大于180°的角，則稱Vi是凹頂點；若內角是一個等于180°的角，則稱Vi是中性點，在圖形處理時可根據需要將其看作凸頂點或者凹頂點。由此定義可知，對任意一個簡單多邊形，其每個頂點或是凸的，或是凹的。凸頂點對應的內角稱為凸角，凹頂點對應的內角稱為凹角。

對簡單單連通多邊形而言，所有頂點都為凸頂點的多邊形稱為凸多邊形，至少有一個頂點為凹頂點的多邊形稱為凹多邊形。

3.多邊形的方向、有向邊

多邊形的方向有逆時針方向和順時針方向之分。對簡單單連通多邊形而言，沿觀察方向看去，若觀察者按頂點序列V1V2…VnVn+1繞多邊形一周時，該多邊形所圍的有界區域總在左邊，則稱該多邊形為逆時針方向，如圖2.19(a)所示；否則，稱其為順時針方向，如圖2.19(b)所示。

圖2.19多邊形的方向

4.頂點的叉積

2.6.2多邊形凸凹性的判斷

1.多邊形方向的判斷

多邊形方向的判斷方法為極值頂點法。多邊形頂點中坐標值為xmin或xmax或ymin或ymax的頂點稱為極值頂點，極值頂點必為凸頂點。

極值頂點法如下：

(1)找出多邊形的某一極值頂點。

(2)求該極值頂點的叉積。

(3)若叉積值nz>0，則多邊形的方向為逆時針方向；若叉積值nz＜0，則多邊形的方向為順時針方向。

2.多邊形頂點凸凹性的判斷

假定多邊形V1V2…Vn的方向為逆時針方向，這是常見的情況。多邊形頂點凸凹性的判斷方法有頂點叉積法、平移旋轉法等。這里介紹較為簡單的頂點叉積法。

對于逆時針方向的多邊形，任一頂點Vi凸凹性判斷的頂點叉積法如下：

(1)計算頂點Vi的叉積。

(2)若叉積值nz>0，則該頂點為凸頂點；若叉積值nz＜0，則該頂點為凹頂點；若叉積值nz=0，則該頂點為中性點，可根據需要將其看作凸頂點或者凹頂點

如圖2.20所示，多邊形V1V2V3V4V5V6為逆時針走向，圖中箭頭代表各個頂點的叉積方向。箭頭朝上表示叉積值為正，可知頂點V1、V2、V3、V4、V6是凸頂點；箭頭朝下表示叉積值為負，可知頂點V5是凹頂點。

圖2.20逆時針方向多邊形的叉積示意圖

3.多邊形凸凹性的判斷

經過頂點凸凹性判斷后，若多邊形所有頂點都為凸頂點，則該多邊形是凸多邊形；否則為凹多邊形。

經上述判斷，圖2.20所示的多邊形為凹多邊形。

2.7多邊形的分解與網格劃分

2.7.1凸多邊形的三角分解參見圖2.21，凸多邊形三角分解的算法如下：(1)找出多邊形最長對角線的兩個端點，目的是得到質量較好的三角形。(2)將每個端點與它們相鄰頂點連線形成兩個三角形并輸出。(3)對剩余部分按(1)、(2)遞歸剖分，直至剖分完畢或最后剩余一個三角形輸出。

圖2.21凸多邊形的三角分解過程

2.7.2凹多邊形的分解

參見圖2.22，凹多邊形分解的算法如下：

圖2.22凹多邊形的分解

(1)找出多邊形中的第一個凹頂點(如C點)，并確定其前一個頂點(如B點)和后一個頂點(如D點)。

(2)根據頂點順序，往后另找一點(如E點)，判斷此點與凹頂點的連線是否與多邊形的各邊相交，如果相交，則繼續找下一點，直到找到不相交的點為止。

(3)計算并判斷此點(如E點)與凹頂點連線是否可將本凹頂點(如C點)對應的凹角(如∠BCD)劃分為兩個凸角(此例即是判斷劃分的兩個內角∠BCE和∠ECD是否構成凸頂點，可通過求頂點的叉積進行判斷)；如果可以，將凹角劃分，并將劃分后的多邊形分別輸出；如果不行繼續找下一點，直到滿足條件為止(此例F點滿足將凹角劃分為兩個凸角的要求，輸出兩個多邊形ABCF和DEFC)。

(4)判斷輸出的兩個多邊形的類型，若為三角形或凸多邊形，則不需再劃分；否則執行步驟(1)～(3)。

(5)對劃分出的凸多邊形調用凸多邊形分解算法，將這些凸多邊形分解為三角形輸出。

此算法簡單，但缺點是分解結果與多邊形頂點的排序有關，分解不具有唯一性。

2.7.3帶內環多邊形的分解與基于單調鏈的凸分解

1.非自交多邊形

在有向多邊形中，非相鄰邊相交的多邊形稱為自交多邊形，如圖2.23所示。非相鄰邊不相交但可以重疊的多邊形稱為非自交多邊形，如圖2.24所示。非自交多邊形包括簡單多邊形(圖2.24(a))和有重疊邊但不自相交的多邊形(圖2.24(b))。在圖形處理中，為使帶內環多邊形拓撲等價于不帶內環的多邊形，從而使多邊形分解簡單、統一，就需要在形式上消除內環，其方法就是在外環與內環之間、內環與內環之間引入重疊邊或“橋邊”，如圖2.23、圖2.24、圖2.25所示。

圖2.23自交多邊形

圖2.24非自交多邊形NIP

2.基于NIP多邊形的三角分解

該方法通過在外環與內環之間、內環與內環之間引入“橋邊”將帶內環多邊形轉換為NIP多邊形，然后對NIP多邊形進行三角分解。圖2.25是帶兩個內環的多邊形轉換為一個NIP多邊形的情況。

圖2.25帶內環多邊形的NIP轉換

圖2.26NIP三角分解過程

圖2.27帶內環多邊形的NIP三角分解

3.基于單調鏈的凸分解

基于單調鏈的凸分解的目標是將帶內環多邊形分解為凸多邊形。

1)單調鏈、尖點的概念

單調鏈的定義:如果一條鏈(開口多邊形)上的點在直線L上的正交投影是有序的，即投影點的坐標值依次增大(包括相等)，或依次減小(包括相等)，則稱該鏈相對于L單調，如圖2.28所示。點在直線L上的正交投影是否有序的判斷方法為:沿直線L建立局部坐標系并取L為x軸正向，將鏈頂點坐標轉換為局部坐標，比較鏈頂點的x坐標看其是否依次增大或依次減小。

圖2.28單調鏈

如果直線L為y軸，則稱該單調鏈為對y軸單調鏈。基于單調鏈的凸分解算法中的單調鏈均為對y軸單調鏈。圖2.29中的多邊形有M1、M2、M3、M4共4條單調鏈。

尖點的定義:任意多邊形中，單調鏈的端點稱為尖點。對于相對于y軸的單調鏈，其上端點定義為上尖點，其下端點定義為下尖點。如圖2.29中，S1、S3為上尖點，S2、S4為下尖點。

上、下單調鏈:任意多邊形中，若沿環的方向單調鏈的起點為上尖點，終點為下尖點，則定義其為下單調鏈，相反則定義其為上單調鏈。圖2.29中，M1、M3為下單調鏈，M2、M4為上單調鏈。

圖2.29上、下尖點與上、下單調鏈

2)凸分解算法

參見圖2.30，基于單調鏈的凸分解算法主要包括三個步驟：

(1)將帶內環多邊形分解為有序單調鏈。圖2.30(a)按下單調鏈分解，可分解為9個下單調鏈。

(2)通過分裂和組合單調鏈，逐次拆分出單調多邊形。由兩條單調鏈組成的多邊形稱為單調多邊形，圖(a)的多邊形可拆分如圖(b)所示的4個單調多邊形。

(3)將單調多邊形分解為凸多邊形，如圖(c)所示。可利用前述的凹多邊形分解算法進行分解。

圖2.30基于單調鏈的凸分解過程

2.7.4Delaunay三角剖分

蘇聯數學家Delaunay于1934年證明，對于散亂點集，必定存在且僅存在一種三角剖分算法，使得剖分得到的所有三角形的最小內角之和最大(“最小角最大原則”)，這種算法稱為Delaunay三角剖分，簡稱DT剖分。Delaunay三角剖分算法是最著名的三角化網格生成方法，因為它具有“三角剖分最小內角之和為最大”的性質，從而保證了網格整體質量最優，稱為最優三角剖分。DT剖分可用于數字地形建模、工程網格劃分、人臉圖像結構建模等。

1.Delaunay三角剖分的性質

Delaunay三角剖分具有一些非常重要的性質，其中最為重要的性質如下：

1)最小內角最大準則

對一個凸四邊形進行劃分時，該準則要求對角線兩側兩個三角形中的最小內角為最大。沿短對角線進行劃分可滿足最小內角最大準則，如圖2.31所示。

圖2.31最小內角最大原則

2)空外接圓(空外接球)準則

對于三角形剖分而言，該準則稱為空外接圓準則。對于四面體剖分而言，該準則稱為空外接球準則。這里討論三角形剖分。對于任意一個Delaunay三角形，它的外接圓的內部區域不包含其他的任何結點，所有Delaunay三角形互不重疊，并且完整地覆蓋整個區域。

如圖2.32所示，左圖三點組成了Delaunay三角形，因其外接圓內即虛線所示部分再無其他結點，而右圖三角形不滿足空外接圓準則，故不是Delaunay三角形。

圖2.32Delaunay三角形空外接圓準則

3)局部性

在已有的Delaunay剖分中加入、去除或移動一個結點后，僅需進行局部修改即可獲得Delaunay三角剖分，這就是DT剖分的局部性。所有需要進行修改的三角形的并集稱為影響域。圖2.33左圖影響域為帶虛線的5個三角形的并集，右圖影響域為帶虛線的3個三角形的并集。可以證明，影響域的各結點對于加入或刪除的點來說都是可見的，所謂可見是指該點與結點連線不與三角形的邊相交，這給出了影響域的求取方法。因此，影響域是局部的。圖2.33表示了加入或刪除一點所需進行的修改。局部性可用于網格稀疏或加密操作。

圖2.33Delaunay三角剖分的局部性

2.Delaunay三角剖分算法

參見圖2.34，算法主要步驟如下：

(1)從當前多邊形(初始多邊形和每剖分一次剩余的多邊形)的第一邊開始，找對該邊的可見頂點(在多邊形內且頂點與邊的端點連線不與多邊形的邊相交的頂點)，若可見頂點有多個