計算幾何入門 2：凸包的構(gòu)造

imelee 2018-09-29

展開全文

一、極點（extreme point）

繼續(xù)考慮釘子與橡皮筋的例子。我們可以發(fā)現(xiàn)邊緣上的釘子是對范圍圈定“有貢獻”的，而范內(nèi)部的的釘子對范圍圈定是“沒有貢獻的”。這只是直觀的結(jié)論，嚴(yán)謹(jǐn)考慮我們將其抽象為極性與極點的概念。

簡單的數(shù)學(xué)前提：過一個點有無數(shù)直線；有向直線可以將平面劃分確定的左右兩部分；

可以在圖像上表示為：

可以發(fā)現(xiàn)，邊緣上“有貢獻”的釘子，總可以找到一條穿過它的有向直線，使得其余是有點都處于直線的同一邊；而范圍內(nèi)“沒有貢獻”的釘子則無法找到這種有向直線。這正是兩種點的本質(zhì)區(qū)別：極性。我們將這些“有貢獻”的點就稱為：極點（extreme point）。那么如何將極點在點集中篩選出來呢？也就是給定一個多邊形，如何判斷它是凸的呢？

二、凸包構(gòu)造方法

考慮冒泡排序的原理：序列是有序的當(dāng)且僅當(dāng)它的每個子序列都是有序的。類比冒泡排序的原理來考察凸包問題，如果一個多邊形是對應(yīng)點集的凸包，當(dāng)且僅當(dāng)多邊形各點都是極點，或者說多邊形各點都是有“有貢獻”的。即：凸包由極點集確定。

那么如何確定某個點是否為極點呢？再考慮顏色勾兌的例子，某種顏色能被其他顏色勾兌出來，當(dāng)且僅當(dāng)該顏色對應(yīng)的點包含于另外三個點的范圍內(nèi)。因此可以將其余點的所有三角形組合與待定點做判斷，若待定點不在任何一個三角形的范圍內(nèi)，則說明待定點是一個極點。所有極點就能構(gòu)成凸包，這就是凸包的基本構(gòu)造步驟。

上圖中處于某三角形內(nèi)部的兩點都判定為非極點。

通過上述論證，我們的計算任務(wù)劃分為子任務(wù)：

判斷某待定點是否位于某個三角形的內(nèi)部（in-triangle test）

通過反復(fù)進行in-triangle test，我們就能將各個非極點排除，最終得到極點集合，構(gòu)成凸包。而進行in-triangle test的基礎(chǔ)就是to-left test。

三、to-left test

上述篩選極點的算法偽代碼描述為：

Mark all points of S as EXTREME //首先將集合S的所有點標(biāo)記為極點

for each triangle △(p, q, r) //對于每個三角形pqr（枚舉每個三角形）

for each s ∈ S\{p, q, r} //若某個集合S內(nèi)非pqr的點s

if s ∈ △(p, q, r) then //若s在三角形pqr內(nèi)（in-triangle test）

mark s as NON_EXTREME //則將s標(biāo)記為非極點

這個算法看似非常直白，但是其中第二行：枚舉每個三角形，需要三重循環(huán)，加上第3句枚舉每個點s，整個算法至少要O(n^4)的復(fù)雜度。

為了解決基礎(chǔ)算法復(fù)雜度過高的問題，我們引入to-left test算法。

首先還是來看in-triangle test：如何判斷待定是否落在某三角形內(nèi)部。將in-triangle test劃分為子任務(wù)：三次to-left test，每條邊對應(yīng)一次to-left test，且三次測試返回相同結(jié)果（true/false）。

我們知道，每兩個點能確定一條直線，而對于每個有向直線能將平面分為左右兩部分。

按照慣例約定逆時針來表示三角形，因此三角形pqr對應(yīng)三個有向直線：pq，qr，rp。而待定點s若在三角形pqr內(nèi)部，當(dāng)且僅當(dāng)s對于三個有向直線都在左側(cè)。即：

ToLeft(p, q, s) == true;

ToLeft(q, r, s) == true;

ToLeft(r, p, s) == true;

實際上三條直線能將平面最多切分為7塊，每一塊都對應(yīng)三個to-left測試，而只有三角形內(nèi)部的區(qū)域中三個to-left測試結(jié)果全為真。

至此，我們將in-triangle test分解為三個to-left test，問題就進一步歸結(jié)為：如何用算法高效的表示to-left test。

考慮如下一般情況：

如何判斷待定點s位于有向直線pq哪一側(cè)呢？

當(dāng)然可以通過解析幾何的方式實現(xiàn)：每個直線對應(yīng)一個解析方程，點到直線的距離能夠通過公式計算。但是這種方式并不是最好的，其缺陷很明顯。我們先看更通用的方法：計算三角形pqs的面積S。S可由以下行列式計算（算出的是兩倍面積）：

注意此處計算出的面積是由正負(fù)的，面積為正，則s位于有向直線pq的左側(cè)，面積為負(fù)，則s位于有向直線pq的右側(cè)。因此得到了to-left test的算法：

bool ToLeft(Point p, Point q, Point s)
{
	int area2 =   p.x * q.y - p.y * q.x 
				+ q.x * s.y - q.y * s.x
				+ s.x * p.y - s.y * p.x;
	return area2 > 0;
}

這種基于行列式的方法比解析幾何的優(yōu)勢不僅在于更加簡單明確，更重要在于這種方法有效避免了除法和三角函數(shù)，完全消除了誤差。

四、極邊（extreme edge）

通過極點的引入并沒有降低凸包構(gòu)造算法O(n^4)的復(fù)雜度，為此我們轉(zhuǎn)換視角，從邊的角度考慮問題。

類比極點，引入極邊（extreme edge）的概念，如下圖中：

所謂極邊就是點集S中過某兩點的有向直線，使得S中其余點都落在此直線的一側(cè)，而非極邊則兩側(cè)總是都有點。與極點類似，所有極邊圈出的區(qū)域構(gòu)成了凸包。依然選擇逆時針順序來看，對于任何一個極邊，其余點的to-left測試都是true。

因此，構(gòu)造凸包的問題轉(zhuǎn)化為如何篩選極邊的問題。算法偽碼描述如下：

for each directed segment pq //對于每個有向邊pq

if points in S\{p, q} lie to the same side of pq then //如果S中除了pq外是有點都在有向邊pq同側(cè)

let EE = EE ∪ {pq} //則邊pq是極邊

再來分析一下復(fù)雜度。首先枚舉每條邊需要n^2復(fù)雜度，接下來判斷某個邊是不是極邊僅需要線性復(fù)雜度，因此算法復(fù)雜度為O(n^3)，比極點方法提高了一個量級。

然后將上述偽碼用C++表述出來：

bool ToLeft(Point p, Point q, Point s)
{
	int area2 =   p.x * q.y - p.y * q.x 
				+ q.x * s.y - q.y * s.x
				+ s.x * p.y - s.y * p.x;
	return area2 > 0;	//左側(cè)為真
}
void checkEdge(Point S[], int n, int p, int q)
{
	bool LEmpty = true, REmpty = true;	//先假定pq左右都無點
	for (int k = 0; k < n && (LEmpty || REmpty); k++)
		if (k != p && k != q)
			ToLeft(S[p], S[q], S[k]) : LEmpty = false ? REmpty = false;
	if (LEmpty || REmpty)	//若有一側(cè)為空則為極邊
		S[p].extreme = S[q].extreme = true;
}
void markEE(Point S[], int n)	//點集S共n個點，n>2
{
	for (int k = 0; k < n; k++)	//將所有點先標(biāo)為非極點
		S[k].extreme = false;
	for (int p = 0; p < n; p++)
		for (int q = p + 1; q < n; q++)
			checkEdge(S, n, p, q);	//枚舉所有邊并進行判斷
}