新建網(wǎng)頁 1
一般來說，多邊形是由頂點(diǎn)和邊構(gòu)成的平面物體。
簡(jiǎn)單多邊形與復(fù)雜多邊形
簡(jiǎn)單多邊形不包含"洞"，復(fù)雜多邊形可能包含"洞"（圖12.26）。簡(jiǎn)單多邊形可以通過沿多邊形列出的所有頂點(diǎn)來描述（左手坐標(biāo)系中，通常以從多邊形正面看時(shí)的順時(shí)針方向列出所有點(diǎn)）。簡(jiǎn)單多邊形的使用頻率比復(fù)雜多邊形高得多。
通過添加一對(duì)"接縫"邊，能將任意復(fù)雜多邊形轉(zhuǎn)化成簡(jiǎn)單多邊形，如圖12.27所示。見右邊的放大圖，我們?cè)诿總€(gè)"縫"添加了兩個(gè)邊，這兩個(gè)邊實(shí)際上是重合的，放大圖中將其分開是為了讓你看得更清楚。當(dāng)我們考慮到繞多邊形的邊的順序時(shí)，這兩個(gè)接縫邊的方向是相反的。
自相交多邊形
大多數(shù)簡(jiǎn)單多邊形的邊不相交，如果有的邊相交了，那么這個(gè)多邊形叫做自相交多邊形。一個(gè)簡(jiǎn)單的自相交多邊形如圖12.28所示。
凸多邊形與凹多邊形
非自相交多邊形能進(jìn)一步細(xì)分為凸多邊形和凹多邊形。給凸多邊形下一個(gè)精確定義是一件非常困難的事，因?yàn)榇嬖诤芏嗔钊思值耐嘶问健?duì)大多數(shù)多邊形，下列常用的定義是等價(jià)的。不過對(duì)于一些退化多邊形來說，根據(jù)一種定義它是凸的，而根據(jù)另一種定義它又可能是凹的。
（1）直觀上，凸多邊形是沒有任何"凹陷處"的，而凹多邊形至少有一個(gè)頂點(diǎn)處于"凹陷處"----凹點(diǎn)。
（2）凸多邊形，任意兩頂點(diǎn)的連線都包含在多邊形中。但在凹多邊形中，總能找到一對(duì)頂點(diǎn)，它們的連線有一部分在多邊形外。
（3）沿凸多邊形周邊移動(dòng)時(shí)，在每個(gè)頂點(diǎn)的轉(zhuǎn)向都是相同的。對(duì)凹多邊形，一些是向右轉(zhuǎn)，一些是向左轉(zhuǎn)，在凹點(diǎn)的轉(zhuǎn)向是相反的（注意這僅是對(duì)非自相交多邊形來說的）。
前面曾提到過，退化多邊形會(huì)使這些相對(duì)清晰的定義變得模糊不清。例如一些多邊形有兩個(gè)連續(xù)的頂點(diǎn)重合，或這一條邊以相反的方向重復(fù)了兩次。能認(rèn)為這些多邊形是凸的嗎？實(shí)踐中，經(jīng)常用到下列凸性的定義:
（1）如果只能對(duì)凸多邊形起作用的代碼對(duì)這個(gè)多邊形也能起作用，那么它就是凸的（也就是說如果一個(gè)定義沒有被打破就不用修正它）。
（2）如果凸性測(cè)試算法判斷它是凸的，那么它就是凸的（這是由"算法定義"解釋的）。
現(xiàn)在，讓我們忽略一些病態(tài)情況，給出一些大家意見都一致的凸、凹多邊形。如圖12.29所示，右上角的凹多邊形有1個(gè)凹點(diǎn)，而下面的凹多邊形有5個(gè)凹點(diǎn)。
任意凹多邊形都能分解為凸多邊形片，它的基本思路是定位凹點(diǎn)并通過添加對(duì)角線來有系統(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)乘，這種方法返回的角總是以較短的弧度來度量的。
下面的代碼說明了怎樣用角度和來判斷多邊形是否為凸多邊形。
Listing 12.4: 3D polygon convexity test using angle sum
// Function to determine if a polygon is convex. The polygon is
// assumed to be planar.
//
// Input:
// n Number of vertices
// vl pointer to array of of vertices
bool isConvex(int n, const Vector3 vl[])
{
// Initialize sum to 0 radians
float angleSum = 0.0f;
// Go around the polygon and sum the angle at each vertex
for (int i = 0 ; i < n ; ++i)
{
// Get edge vectors. We have to be careful on
// the first and last vertices. Also, note that
// this could be optimized considerably…
Vector3 e1;
if (i == 0)
e1 = vl[n–1] – vl[i];
else
e1 = vl[i–1] – vl[i];
Vector3 e2;
if (i == n–1)
e2 = vl[0] – vl[i];
else
e2 = vl[i+1] – vl[i];
// Normalize and compute dot product
e1.normalize();
e2.normalize();
float dot = e1 * e2;
// Compute smaller angle using “safe” function that protects
// against range errors which could be caused by numerical imprecision
float theta = safeAcos(dot);
// Sum it up
angleSum += theta;
}
// Figure out what the sum of the angles should be, assuming
// we are convex. Remember that pi/2 rad = 180 degrees
float convexAngleSum = (float)(n – 2) * kPiOverTwo;
// Now, check if the sum of the angles is less than it should be;
// then we’re concave. We give a slight tolerance for numerical imprecision
if (angleSum < convexAngleSum – (float)n * 0.0001f)
{
// We’re concave
return false;
}
// We’re convex, within tolerance
return true;
}
另一種檢測(cè)凸性的方法是檢測(cè)多邊形上是否有凹點(diǎn)，如果一個(gè)都沒有找到，就是凸多邊形。它的基本想法是每個(gè)頂點(diǎn)的轉(zhuǎn)向應(yīng)該一致，任何轉(zhuǎn)向不一致的點(diǎn)都是凹點(diǎn)。
怎樣檢測(cè)一個(gè)點(diǎn)的轉(zhuǎn)向呢？技巧是利用邊向量的叉乘，左手坐標(biāo)系中，如果向量的轉(zhuǎn)向是順指針，它們的叉乘就會(huì)指向你。什么是指向你呢？我們從多邊形的正面看，正面由法向量指明。如果沒有提供法向量，就必須做一些計(jì)算來得到。一旦有了法向量，檢查多邊形的每個(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)單多邊形的三角分解是一件容易的事。一種顯而易見的三角分解技術(shù)是選取一個(gè)點(diǎn)（稱作第一個(gè)點(diǎn)），沿著頂點(diǎn)按"扇形"分解多邊形。給定一個(gè)有n個(gè)頂點(diǎn)的多邊形，沿多邊形列頂點(diǎn)v1...vn，能夠很容易地構(gòu)造形如{v1,vi-1, vi}的n-2個(gè)三角形，見圖12.30。
扇形三角分割會(huì)分割出一些長的、較細(xì)的三角形，這在某些情況下會(huì)引起麻煩。如同計(jì)算表面的法向量一樣，數(shù)值的不精確性在度量極小的角時(shí)會(huì)造成一些問題。
一種更加"聰明"的分解方法是：連接兩頂點(diǎn)的對(duì)角線將一個(gè)多邊形分解為兩部分。這時(shí)，對(duì)角線端點(diǎn)處的兩個(gè)內(nèi)角都能分解為兩個(gè)新的內(nèi)角。因此，總共產(chǎn)生了4個(gè)新內(nèi)角。為了分解多邊形，選擇能使這4個(gè)新內(nèi)角中最小的角最大化的對(duì)角線，用這條對(duì)角線將多邊形分為兩個(gè)。對(duì)分割后的每一部分都遞歸應(yīng)用這個(gè)過程直到剩下的都是三角形。
這個(gè)方法產(chǎn)生較少的細(xì)三角形，但在實(shí)踐中，它過于復(fù)雜。根據(jù)幾何學(xué)和應(yīng)用目的，扇形分解已經(jīng)足夠了（并且簡(jiǎn)單得多）。