一般來(lái)說(shuō)，多邊形是由頂點(diǎn)和邊構(gòu)成的平面物體。

　

簡(jiǎn)單多邊形與復(fù)雜多邊形

簡(jiǎn)單多邊形不包含"洞"，復(fù)雜多邊形可能包含"洞"（圖12.26）。簡(jiǎn)單多邊形可以通過(guò)沿多邊形列出的所有頂點(diǎn)來(lái)描述（左手坐標(biāo)系中，通常以從多邊形正面看時(shí)的順時(shí)針?lè)较蛄谐鏊悬c(diǎn)）。簡(jiǎn)單多邊形的使用頻率比復(fù)雜多邊形高得多。

通過(guò)添加一對(duì)"接縫"邊，能將任意復(fù)雜多邊形轉(zhuǎn)化成簡(jiǎn)單多邊形，如圖12.27所示。見(jiàn)右邊的放大圖，我們?cè)诿總€(gè)"縫"添加了兩個(gè)邊，這兩個(gè)邊實(shí)際上是重合的，放大圖中將其分開(kāi)是為了讓你看得更清楚。當(dāng)我們考慮到繞多邊形的邊的順序時(shí)，這兩個(gè)接縫邊的方向是相反的。

　

自相交多邊形

大多數(shù)簡(jiǎn)單多邊形的邊不相交，如果有的邊相交了，那么這個(gè)多邊形叫做自相交多邊形。一個(gè)簡(jiǎn)單的自相交多邊形如圖12.28所示。

　

凸多邊形與凹多邊形

非自相交多邊形能進(jìn)一步細(xì)分為凸多邊形和凹多邊形。給凸多邊形下一個(gè)精確定義是一件非常困難的事，因?yàn)榇嬖诤芏嗔钊思值耐嘶问健?duì)大多數(shù)多邊形，下列常用的定義是等價(jià)的。不過(guò)對(duì)于一些退化多邊形來(lái)說(shuō)，根據(jù)一種定義它是凸的，而根據(jù)另一種定義它又可能是凹的。

（1）直觀上，凸多邊形是沒(méi)有任何"凹陷處"的，而凹多邊形至少有一個(gè)頂點(diǎn)處于"凹陷處"----凹點(diǎn)。

（2）凸多邊形，任意兩頂點(diǎn)的連線(xiàn)都包含在多邊形中。但在凹多邊形中，總能找到一對(duì)頂點(diǎn)，它們的連線(xiàn)有一部分在多邊形外。

（3）沿凸多邊形周邊移動(dòng)時(shí)，在每個(gè)頂點(diǎn)的轉(zhuǎn)向都是相同的。對(duì)凹多邊形，一些是向右轉(zhuǎn)，一些是向左轉(zhuǎn)，在凹點(diǎn)的轉(zhuǎn)向是相反的（注意這僅是對(duì)非自相交多邊形來(lái)說(shuō)的）。

前面曾提到過(guò)，退化多邊形會(huì)使這些相對(duì)清晰的定義變得模糊不清。例如一些多邊形有兩個(gè)連續(xù)的頂點(diǎn)重合，或這一條邊以相反的方向重復(fù)了兩次。能認(rèn)為這些多邊形是凸的嗎？實(shí)踐中，經(jīng)常用到下列凸性的定義:

（1）如果只能對(duì)凸多邊形起作用的代碼對(duì)這個(gè)多邊形也能起作用，那么它就是凸的（也就是說(shuō)如果一個(gè)定義沒(méi)有被打破就不用修正它）。

（2）如果凸性測(cè)試算法判斷它是凸的，那么它就是凸的（這是由"算法定義"解釋的）。

現(xiàn)在，讓我們忽略一些病態(tài)情況，給出一些大家意見(jiàn)都一致的凸、凹多邊形。如圖12.29所示，右上角的凹多邊形有1個(gè)凹點(diǎn)，而下面的凹多邊形有5個(gè)凹點(diǎn)。

任意凹多邊形都能分解為凸多邊形片，它的基本思路是定位凹點(diǎn)并通過(guò)添加對(duì)角線(xiàn)來(lái)有系統(tǒng)地移除它們。

怎樣才能知道一個(gè)多邊形是凸的還是凹的？一種方法是檢查各頂點(diǎn)的內(nèi)角和，考慮n個(gè)頂點(diǎn)的凸多邊形，它的內(nèi)角和為(n-2)180^。,有兩種方法可以證明這個(gè)結(jié)論。

（1）設(shè)θ_i為頂點(diǎn)i的內(nèi)角，很明顯，θ_i≤ 180^。(假設(shè)多邊形是凸的)。在每個(gè)頂點(diǎn)上，補(bǔ)角為（180-θ_i）^。，對(duì)于一個(gè)封閉的凸多邊形，全部頂點(diǎn)的補(bǔ)角之和為360^。，有：

（2）任意n個(gè)頂點(diǎn)的凸多邊形都能分解為n-2個(gè)三角形，由經(jīng)典幾何知識(shí)可知，三角形內(nèi)角和為180^。。所有三角形的內(nèi)角和為(n-2)180^。，可以看到，這個(gè)和總是等于多邊形的內(nèi)角和。

不幸的是，凹多邊形和凸多邊形一樣，內(nèi)角和也是(n-2)180^。。怎樣才能進(jìn)一步判斷一個(gè)多邊形是不是凸多邊形呢？對(duì)一個(gè)凸多邊形，內(nèi)角不會(huì)大于外角。（外角不是補(bǔ)角，一對(duì)內(nèi)角外角的和等于360^。）

所以，將每個(gè)頂點(diǎn)處較小的角（內(nèi)角或外角）相加，凸多邊形得到(n-2)180^。，凹多邊形則小于它。怎樣判斷哪個(gè)角較小呢？幸運(yùn)的是，有這樣一個(gè)工具 ---- 點(diǎn)乘，這種方法返回的角總是以較短的弧度來(lái)度量的。

下面的代碼說(shuō)明了怎樣用角度和來(lái)判斷多邊形是否為凸多邊形。

另一種檢測(cè)凸性的方法是檢測(cè)多邊形上是否有凹點(diǎn)，如果一個(gè)都沒(méi)有找到，就是凸多邊形。它的基本想法是每個(gè)頂點(diǎn)的轉(zhuǎn)向應(yīng)該一致，任何轉(zhuǎn)向不一致的點(diǎn)都是凹點(diǎn)。

怎樣檢測(cè)一個(gè)點(diǎn)的轉(zhuǎn)向呢？技巧是利用邊向量的叉乘，左手坐標(biāo)系中，如果向量的轉(zhuǎn)向是順指針，它們的叉乘就會(huì)指向你。什么是指向你呢？我們從多邊形的正面看，正面由法向量指明。如果沒(méi)有提供法向量，就必須做一些計(jì)算來(lái)得到。一旦有了法向量，檢查多邊形的每個(gè)頂點(diǎn)。用相鄰的兩個(gè)邊向量計(jì)算該頂點(diǎn)的法向量，接著用多邊形的法向量和頂點(diǎn)的法向量點(diǎn)乘，檢測(cè)它們的方向是否相反。如果是（點(diǎn)乘為負(fù)），那么這個(gè)頂點(diǎn)就是一個(gè)凹點(diǎn)。

　

三角分解和扇形分解

任意多邊形都能分解為三角形。因此，所有對(duì)三角形的操作都能應(yīng)用到多邊形上。復(fù)雜、自相交、甚至簡(jiǎn)單的凹多邊形的三角分解都不是一件簡(jiǎn)單的工作。幸運(yùn)的是，簡(jiǎn)單多邊形的三角分解是一件容易的事。一種顯而易見(jiàn)的三角分解技術(shù)是選取一個(gè)點(diǎn)（稱(chēng)作第一個(gè)點(diǎn)），沿著頂點(diǎn)按"扇形"分解多邊形。給定一個(gè)有n個(gè)頂點(diǎn)的多邊形，沿多邊形列頂點(diǎn)v₁...v_n，能夠很容易地構(gòu)造形如{v₁,v_i-1, v_i}的n-2個(gè)三角形，見(jiàn)圖12.30。

扇形三角分割會(huì)分割出一些長(zhǎng)的、較細(xì)的三角形，這在某些情況下會(huì)引起麻煩。如同計(jì)算表面的法向量一樣，數(shù)值的不精確性在度量極小的角時(shí)會(huì)造成一些問(wèn)題。

一種更加"聰明"的分解方法是：連接兩頂點(diǎn)的對(duì)角線(xiàn)將一個(gè)多邊形分解為兩部分。這時(shí)，對(duì)角線(xiàn)端點(diǎn)處的兩個(gè)內(nèi)角都能分解為兩個(gè)新的內(nèi)角。因此，總共產(chǎn)生了4個(gè)新內(nèi)角。為了分解多邊形，選擇能使這4個(gè)新內(nèi)角中最小的角最大化的對(duì)角線(xiàn)，用這條對(duì)角線(xiàn)將多邊形分為兩個(gè)。對(duì)分割后的每一部分都遞歸應(yīng)用這個(gè)過(guò)程直到剩下的都是三角形。

這個(gè)方法產(chǎn)生較少的細(xì)三角形，但在實(shí)踐中，它過(guò)于復(fù)雜。根據(jù)幾何學(xué)和應(yīng)用目的，扇形分解已經(jīng)足夠了（并且簡(jiǎn)單得多）。