凸包(Convex Hull)是一個(gè)計(jì)算幾何(圖形學(xué))中的概念。
在一個(gè)實(shí)數(shù)向量空間V中,對(duì)于給定集合X,所有包含X的凸集的交集S被稱為X的凸包。
X的凸包可以用X內(nèi)所有點(diǎn)(X1,...Xn)的線性組合來(lái)構(gòu)造.
在二維歐幾里得空間中,凸包可想象為一條剛好包著所有點(diǎn)的橡皮圈。
用不嚴(yán)謹(jǐn)?shù)脑拋?lái)講,給定二維平面上的點(diǎn)集,凸包就是將最外層的點(diǎn)連接起來(lái)構(gòu)成的凸多邊型,它能包含點(diǎn)集中所有的點(diǎn)。
例子:假設(shè)平面上有p0~p12共13個(gè)點(diǎn),過(guò)某些點(diǎn)作一個(gè)多邊形,使這個(gè)多邊形能把所有點(diǎn)都“包”起來(lái)。當(dāng)這個(gè)多邊形是凸多邊形的時(shí)候,我們就叫它“凸包”。如下圖:
一、二維凸包
1. 定義
凸多邊形是指所有內(nèi)角大小都在[0,π]范圍內(nèi)的簡(jiǎn)單多邊形。
在平面上能包含所有給定點(diǎn)的最小凸多邊形叫做凸包。
其定義為:對(duì)于給定集合X,所有包含X的凸集的交集S被稱為X的凸包。
實(shí)際上可以理解為用一個(gè)橡皮筋包含住所有給定點(diǎn)的形態(tài)。
凸包用最小的周長(zhǎng)圍住了給定的所有點(diǎn)。如果一個(gè)凹多邊形圍住了所有的點(diǎn),它的周長(zhǎng)一定不是最小,如下圖。根據(jù)三角不等式,凸多邊形在周長(zhǎng)上一定是最優(yōu)的。
2. Andrew 算法求凸包
常用的求法有 Graham 掃描法和 Andrew 算法,這里主要介紹 Andrew 算法。
(1)性質(zhì)
該算法的時(shí)間復(fù)雜度為O(nlogn),其中 n 為待求凸包點(diǎn)集的大小,同時(shí)復(fù)雜度的瓶頸也在于對(duì)所有點(diǎn)坐標(biāo)的雙關(guān)鍵字排序。
(2)過(guò)程
首先把所有點(diǎn)以橫坐標(biāo)為第一關(guān)鍵字,縱坐標(biāo)為第二關(guān)鍵字排序。
顯然排序后最小的元素和最大的元素一定在凸包上。而且因?yàn)槭峭苟噙呅?,我們?nèi)绻麖囊粋€(gè)點(diǎn)出發(fā)逆時(shí)針走,軌跡總是“左拐”的,一旦出現(xiàn)右拐,就說(shuō)明這一段不在凸包上。因此我們可以用一個(gè)單調(diào)棧來(lái)維護(hù)上下凸殼。
因?yàn)閺淖笙蛴铱矗舷峦箽にD(zhuǎn)的方向不同,為了讓單調(diào)棧起作用,我們首先升序枚舉求出下凸殼,然后降序求出上凸殼。
求凸殼時(shí),一旦發(fā)現(xiàn)即將進(jìn)棧的點(diǎn)(P)和棧頂?shù)膬蓚€(gè)點(diǎn)(S1,S2,其中S1為棧頂)行進(jìn)的方向向右旋轉(zhuǎn),即叉積小于0:,則彈出棧頂,回到上一步,繼續(xù)檢測(cè),直到或者棧內(nèi)僅剩一個(gè)元素為止。
通常情況下不需要保留位于凸包邊上的點(diǎn),因此上面一段中這個(gè)條件中的“<”可以視情況改為≤,同時(shí)后面一個(gè)條件應(yīng)改為>。
(3)實(shí)現(xiàn):
// C++ Version // stk[] 是整型,存的是下標(biāo) // p[] 存儲(chǔ)向量或點(diǎn) tp = 0; // 初始化棧 std::sort(p + 1, p + 1 + n); // 對(duì)點(diǎn)進(jìn)行排序 stk[++tp] = 1; // 棧內(nèi)添加第一個(gè)元素,且不更新 used,使得 1 在最后封閉凸包時(shí)也對(duì)單調(diào)棧更新 for (int i = 2; i <= n; ++i) { while (tp >= 2 // 下一行 * 操作符被重載為叉積 && (p[stk[tp]] - p[stk[tp - 1]]) * (p[i] - p[stk[tp]]) <= 0) used[stk[tp--]] = 0; used[i] = 1; // used 表示在凸殼上 stk[++tp] = i; } int tmp = tp; // tmp 表示下凸殼大小 for (int i = n - 1; i > 0; --i) if (!used[i]) { // ↓求上凸殼時(shí)不影響下凸殼 while (tp > tmp && (p[stk[tp]] - p[stk[tp - 1]]) * (p[i] - p[stk[tp]]) <= 0) used[stk[tp--]] = 0; used[i] = 1; stk[++tp] = i; } for (int i = 1; i <= tp; ++i) // 復(fù)制到新數(shù)組中去 h[i] = p[stk[i]]; int ans = tp - 1;
# Python Version stk = [] # 是整型,存的是下標(biāo) p = [] # 存儲(chǔ)向量或點(diǎn) tp = 0 # 初始化棧 p.sort() # 對(duì)點(diǎn)進(jìn)行排序 stk[tp] = 1 tp = tp + 1 # 棧內(nèi)添加第一個(gè)元素,且不更新 used,使得 1 在最后封閉凸包時(shí)也對(duì)單調(diào)棧更新 for i in range(2, n + 1): while tp >= 2 and (p[stk[tp]] - p[stk[tp - 1]]) * (p[i] - p[stk[tp]]) <= 0: # 下一行 * 操作符被重載為叉積 used[stk[tp]] = 0 tp = tp - 1 used[i] = 1 # used 表示在凸殼上 stk[tp] = i tp = tp + 1 tmp = tp # tmp 表示下凸殼大小 for i in range(n - 1, 0, -1): if used[i] == False: # ↓求上凸殼時(shí)不影響下凸殼 while tp > tmp and (p[stk[tp]] - p[stk[tp - 1]]) * (p[i] - p[stk[tp]]) <= 0: used[stk[tp]] = 0 tp = tp - 1 used[i] = 1 stk[tp] = i tp = tp + 1 for i in range(1, tp + 1): h[i] = p[stk[i]] ans = tp - 1
根據(jù)上面的代碼,最后凸包上有ans個(gè)元素(額外存儲(chǔ)了1號(hào)點(diǎn),因此 h 數(shù)組中有 ans+1 個(gè)元素),并且按逆時(shí)針?lè)较蚺判?。周長(zhǎng)就是
二、三維凸包
圓的反演:反演中心為O,反演半徑為R,若經(jīng)過(guò)O的直線經(jīng)過(guò)P,P′,且OPXP′=R^2,則稱P、P′關(guān)于 O 互為反演。
求凸包的過(guò)程如下:
(1)首先對(duì)其微小擾動(dòng),避免出現(xiàn)四點(diǎn)共面的情況。
(2)對(duì)于一個(gè)已知凸包,新增一個(gè)點(diǎn) P,將 P 視作一個(gè)點(diǎn)光源,向凸包做射線,可以知道,光線的可見(jiàn)面和不可見(jiàn)面一定是由若干條棱隔開(kāi)的。
(3)將光的可見(jiàn)面刪去,并新增由其分割棱與 P 構(gòu)成的平面。重復(fù)此過(guò)程即可,由Pick定理、歐拉公式(在凸多面體中,其頂點(diǎn) V、邊數(shù) E 及面數(shù) F 滿足 V-E+F=2)和圓的反演,復(fù)雜度。
C語(yǔ)言網(wǎng)提供由在職研發(fā)工程師或ACM藍(lán)橋杯競(jìng)賽優(yōu)秀選手錄制的視頻教程,并配有習(xí)題和答疑,點(diǎn)擊了解:
一點(diǎn)編程也不會(huì)寫的:零基礎(chǔ)C語(yǔ)言學(xué)練課程
解決困擾你多年的C語(yǔ)言疑難雜癥特性的C語(yǔ)言進(jìn)階課程
從零到寫出一個(gè)爬蟲的Python編程課程
只會(huì)語(yǔ)法寫不出代碼?手把手帶你寫100個(gè)編程真題的編程百練課程
信息學(xué)奧賽或C++選手的 必學(xué)C++課程
藍(lán)橋杯ACM、信息學(xué)奧賽的必學(xué)課程:算法競(jìng)賽課入門課程
手把手講解近五年真題的藍(lán)橋杯輔導(dǎo)課程