两个吃奶一个添下面视频_人妻第一页香蕉网_欧美xxxx少妇_妺妺窝人体色www婷婷

凸包(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:Andrew算法求凸包,則彈出棧頂,回到上一步,繼續(xù)檢測(cè),直到Andrew算法求凸包或者棧內(nèi)僅剩一個(gè)元素為止。

通常情況下不需要保留位于凸包邊上的點(diǎn),因此上面一段中Andrew 算法求凸包這個(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)就是

周長(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ù)雜度復(fù)雜度。

點(diǎn)贊(0)

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)課程

Dotcpp在線編譯      (登錄可減少運(yùn)行等待時(shí)間)