這些問題都可以簡化為betway必威游戏一群點的凸包

当前位置:betway必威平台 > betway必威游戏 > 這些問題都可以簡化為betway必威游戏一群點的凸包
作者: betway必威平台|来源: http://www.bag139.com|栏目:betway必威游戏

文章关键词:betway必威平台,凸包

  中譯「凸包」或「凸殼」。在多維空間中有一群散佈各處的點,「凸包」是包覆這群點的所有外殼當中,表面積暨容積最小的一個外殼,而最小的外殼一定是凸的。

  至於「凸」的定義是:圖形內任意兩點的連線不會經過圖形外部。「凸」並不是指表面呈弧狀隆起,事實上凸包是由許多平坦表面組成的。

  二維平面上的凸包是一個凸多邊形,在所有點的外圍繞一圈即得凸包。另外,最頂端、最底端、最左端、最右端的點,一定是凸包上的點。

  計算凸包時需考慮一些特殊情況:一、凸包上多點重疊;二、凸包上多點共線;三、凸包呈一條線段、一個點、沒有點。通常我們會簡化資訊,以最少的點來記錄凸包,去掉重疊、共線的點。

  任意圖形都能求出凸包。例如一個多邊形的凸包、大量三角形的凸包、大量線段的凸包。這些問題都可以簡化為一群點的凸包。

  每當尋找下一個要被包覆的點,則窮舉平面上所有點,找出最外圍的一點來包覆。可以利用叉積運算來判斷。

  實作時請多多運用指標、索引值,儘量避免搬動原本資料。此處的程式碼是不良示範,僅供參考。

  如果想找出凸包上重疊的點與共線的點,則改為尋找離上一點最近的點,並且標記目前已包過的點。

  由前面章節可知:凸包上的頂點很有順序的沿著外圍繞行一圈,這個順序是時針順序。

  Grahams Scan嘗試先將所有點依照時針順序排好,再來做繞行一圈的動作,繞行途中順便掃除凸包內部的點,如此就不必以窮舉所有點的方式來尋找最外圍的點。

  要讓所有點依照時針順序排好,只要將中心點設定在凸包內部或者凸包上,然後讓各點依照角度排序即可。如果把中心點設定在凸包外部,結果就不見得是時針順序了。包覆時必須按照時針順序,才能確保結果正確。

  一般來說,選擇凸包上的頂點當作中心點是比較好的,因為角度排序時的夾角皆小於180°,可以使用叉積運算來排序(大於180°叉積得負值、等於180°叉積等於零,導致排序錯誤)。另一個好處是,中心點也可以作為包覆的起點。

  角度排序時,遇到角度相同的情況,要小心排序。通常是讓距離中心點較近的點排前面。也可以排後面,但是不能亂排。

  掃除的過程當中,經常株連許多點。使用stack資料結構來儲存凸包,逐一判斷stack頂端的點,逐一彈出凹陷的點。凹陷的點必定不是凸包上的頂點。

  如果想找出凸包上重疊的點、共線的點,必須特別小心處理剛開始包、快包好時那些重疊的點、共線的點。一種解決方式是:從最低最左點開始,分頭往左右兩邊包,包至最高最右點。相當麻煩。

  尋找起點的時間O(N)。加上排序的時間O(NlogN)。加上包覆的時間O(N):總共前進N次,最多倒退N次,共為2N次。

  星狀多邊形(star-shaped polygon)的定義是:多邊形內部存在一個點,可以看到整個多邊形內部。也就是說,星狀多邊形可以直接依照連接順序包覆,不必再做角度排序。

  前面章節採用時針順序,此處改為座標順序。以X座標大小排序,當X座標相同則以Y座標大小排序。

  先從起點開始,按照順序掃描,找到下半凸包。再從終點開始,按照相反順序掃描,找到上半凸包。合起來就是完整的凸包。

  一口氣解決了凸包有重疊的點、共線的點、退化成線段和點的問題,是相當優美的演算法。

  時間複雜度為排序的時間O(NlogN),加上包覆的時間O(N)。總共是O(NlogN)。

  一、找出最左點與最右點,連線,所有點分為上半部與下半部。 上半部與下半部分開求解。 二、處理上半部,找出上半凸包: 甲、找到距離底線最遠的點,形成一個三角形區域。 (如果有許多點,就找最靠近左端點的那一點。避免凸包上多點共線。) 乙、運用叉積運算,找出三角形外部的點,分為左、右兩份。 至於三角形內部、三角形上的點,不會是凸包頂點,盡數剔除之。 丙、左、右兩份分別遞迴求解,直到找出上半凸包。 三角形的兩翼,分別做為左、右兩份的底線。 三、處理下半部,找出下半凸包。

  儘管時間複雜度是O(N²),卻是實務上最有效率的演算法。此演算法的好處是:預先剔除凸包內部大部分的點,而且不必預先排序所有點。

  排序的時間複雜度是O(NlogN),空間複雜度是O(N)。當點的數量很大時,例如一千萬,時間約是一千萬的23倍。又由於記憶體不足,必須採用外部排序,需要更多時間。

  此演算法一開始掃描一次所有點,找到三角形外部的點,時間約是一千萬的1倍。如果三角形外部的點很少,例如一千點,那麼接下來的步驟得以節省許多時間。因此,總時間通常遠低於一千萬的23倍。

  遞迴呼叫函數很花時間。當遞迴一兩次後,點數變少,此時可以直接套用其他凸包演算法,節省時間,例如Andrews Monotone Chain。

  合併凸包,找到兩條外公切線即可。從左凸包最右點、右凸包最左點開始,固定左端順時針轉、固定右端逆時針轉,輪流前進直到卡死,就得到下公切線,時間複雜度為O(N)。

  注意到,下公切線並不見得是左右兩凸包的最低點連線,所以就算一開始抓的是左右凸包的最低點,運氣不好時,仍需要O(N)時間才能找到下公切線。況且抓最低點有可能已經衝過頭了。

  附帶一提,內公切線也可如法炮製,改為從左凸包最左點、右凸包最右點開始。如果一個取內側、一點取外側,找公切線有可能衝過頭。

  正確性證明:找外公切線的過程中絕對不會與兩凸包相交、找內公切線的過程中一定會與兩凸包相交,卡死時即是相交與不相交的分際,分際即是公切線。

  時間複雜度為下述兩項總和:一、一次排序的時間,通常為O(NlogN)。二、Divide and Conquer向下遞迴O(logN)深度,合併凸包需要O(N)時間,總共為O(NlogN)。然而凸包內部的點不必用上;找公切線途中遭遇的點,往後不必用上,總共應為O(N)。betway必威游戏

  一開始可以不必排序,只要把所有點分成兩等份即可。兩個凸包合併成一個凸包時,兩個凸包可能會重疊,仍然可以用O(N)時間解決,不過演算法較複雜,此處省略之。

  這是online演算法,隨時維護一個凸包。每當輸入一點,如果此點在凸包內部就直接捨棄;不然就計算此點與當前凸包的兩條切線,然後更新凸包。

  要找切線,窮舉切點即可。切點的左右鄰點都在切線同側,反之則否,判斷僅需O(1)時間。要小心切線與邊重疊的情況。

  凸包的資料結構採用circular list,找到兩個切點後,移除其間的連續凹點僅需O(1)時間。總時間複雜度是O(N²)。

  以試誤法嘗試舊凸包的每個頂點。以當前輸入點為基準,若為凸面、切點,則留下;若為凹面,則捨棄。最後就得到新凸包。

  以當前輸入點為基準,切點的一側是凸面,另一側是凹面,切點恰為凹凸分際。故可用Binary Search找切點。

  凸包的資料結構可以採用Splay Tree,找切點、移除連續頂點僅需O(logN)均攤時間。總時間複雜度是O(NlogN)。

  預先按照XY座標排序所有點(平移的掃描線),此演算法便與Andrews Monotone Chain大同小異,時間複雜度為O(NlogN)。

  預先隨機排列所有點,則第i回合固定新增兩點、平均掃描N/i點,平均時間複雜度為O(NlogN)。推廣到三維空間仍然如此。

  一、假設凸包最多有M個點。 二、使用試誤法,依序嘗試2^(2^0)、2^(2^1)、2^(2^2)、……這些數值作為M。 甲、每M個點為一組,所有點被分作⌈N/M⌉組。 O(N)。betway必威游戏 乙、每一組各自求凸包,一共得到⌈N/M⌉個凸包。《Grahams Scan》 O(MlogM ⋅ ⌈N/M⌉) = O(NlogM)。 丙、嘗試求出這些凸包的凸包。《Jarvis March》 O(3 ⋅ ⌈N/M⌉ ⋅ M) = O(N)。 子、每個凸包各用一個指標,指著各自的最低點。 O(N)。 丑、找出所有凸包的最低點,從最低點開始包覆。 O(N)。 寅、每當尋找下一個要被包覆的點: 回、各凸包各自找出最靠外面的一點,一共得到⌈N/M⌉個點。 由指標處繼續往後找,指標只進不退。要預覽下一點。 O(3 ⋅ ⌈N/M⌉),均攤。 回、再從這⌈N/M⌉個點當中,看看哪一點最靠外面。 O(⌈N/M⌉)。 卯、betway必威游戏若包了M個點還未形成凸包,則馬上停止,回到步驟二! 如果途中形成凸包,即是正解。演算法結束。

  步驟二的時間複雜度是O(NlogM),M每次都不同。對M進行試誤時,謹慎的選擇M的數值,可以將所有步驟二的時間複雜度總和,強壓在O(NlogM)以內。

  總時間複雜度是O(NlogM),N為所有點的數目,M為凸包的頂點數目,是目前時間複雜度最低的演算法。然而實際執行起來,比先前介紹的演算法來得慢。

  由外往內,一層一層的凸包,每一層都是一個Convex Layer。全部的Convex Layer合稱為一個「洋蔥」。

网友评论

我的2016年度评论盘点
还没有评论,快来抢沙发吧!