李紅軍 ， 張曉鵬

（1. 北京林業(yè)大學(xué)理學(xué)院，北京 100083；2. 中國(guó)科學(xué)院自動(dòng)化研究所模式識(shí)別國(guó)家重點(diǎn)實(shí)驗(yàn)室&中法聯(lián)合實(shí)驗(yàn)室，北京 100190）

平面點(diǎn)集的最小包圍圓(smallest enclosing disk)問(wèn)題的提出至少可以追溯至1857年[1]。只是隨著計(jì)算機(jī)技術(shù)的快速發(fā)展，點(diǎn)集的最小包圍圓應(yīng)用越來(lái)越廣泛，比如在工業(yè)機(jī)器人的設(shè)計(jì)、碰撞檢測(cè)、機(jī)器學(xué)習(xí)、計(jì)算機(jī)圖形學(xué)等領(lǐng)域中都有應(yīng)用，研究成果也越來(lái)越多。僅就這個(gè)問(wèn)題的算法設(shè)計(jì)而言，國(guó)內(nèi)外也有不少文獻(xiàn)。本文對(duì)這些現(xiàn)有的典型算法給予簡(jiǎn)單的介紹并進(jìn)行分析和比較。為了避免重述，早期的研究結(jié)果可以參考Emo Welzl的有關(guān)工作[2]。1991年，Welzl在這篇文章中對(duì)早期的一些研究方法和結(jié)果進(jìn)行了簡(jiǎn)要評(píng)述并提出了新方法。Welzl用隨機(jī)增量算法求解平面點(diǎn)集的最小包圍圓或橢圓( smallest enclosing ellipse )，并把這個(gè)算法推廣到高維空間的最小包圍球(smallest enclosing ball )、最小包圍橢球(smallest enclosing ellipsoid )。后來(lái)的Mark de Berg等作了進(jìn)一步的改進(jìn)[3]，我們稱之為改進(jìn)的隨機(jī)增量算法。2005年，F(xiàn)rank Nielsen等也提出了一個(gè)基于對(duì)偶決策的、快速的、確定性算法[1]，這里稱之為對(duì)偶決策算法。2000年復(fù)旦大學(xué)汪衛(wèi)等提出了一個(gè)離散點(diǎn)集最小包圍圓的快速算法，我們稱之為最遠(yuǎn)點(diǎn)優(yōu)先漸近算法[4]。這3種算法思路清晰，不失為有代表性的經(jīng)典算法。本文將對(duì)這3種算法進(jìn)行分析、比較。

1 離散點(diǎn)集最小包圍圓和典型算法

1.1 最小包圍圓問(wèn)題

問(wèn)題：對(duì)于給定的平面上n個(gè)點(diǎn)所組成的一個(gè)集合P，求出P的最小包圍圓，即包含P中所有點(diǎn)、半徑最小的那個(gè)圓。也就是求出這個(gè)最小包圍圓的圓心位置和半徑。

對(duì)于這樣的問(wèn)題，為了便于理解各種算法，需要了解一些有關(guān)最小包圍圓的性質(zhì)：

性質(zhì) 1 有限點(diǎn)集P的最小包圍圓是唯一的。

這里約定，若P中只有一個(gè)點(diǎn)v，則最小包圍圓是退化的，其半徑為 0，圓心為點(diǎn)v。這個(gè)定理的詳細(xì)證明參見(jiàn)文獻(xiàn)[2]。

性質(zhì) 2 非退化最小包圍圓可以由 2個(gè)或者3個(gè)邊界點(diǎn)定義。

顯然，最小包圍圓的構(gòu)成有兩種情況：第1種是距離最遠(yuǎn)的2個(gè)邊界點(diǎn)定義了最小包圍圓的直徑。如圖 1(a)所示，直徑AB定義了這個(gè)最小包圍圓，其余的點(diǎn)都是包含在這個(gè)圓的內(nèi)部。這意味著不能僅僅通過(guò)求最大三角形的外接圓來(lái)計(jì)算最小包圍圓。第2種情況是最小包圍圓的邊界上有3個(gè)以上的點(diǎn)，則任意3個(gè)邊界點(diǎn)為三角形頂點(diǎn)所定義的外接圓確定了這個(gè)點(diǎn)集的最小包圍圓。如圖 1(b) 所示，這個(gè)最小包圍圓由邊界點(diǎn) A、B、C所形成的三角形的外接圓定義。需要注意的是，邊界線上可以有3個(gè)以上的點(diǎn)，只是任意3個(gè)邊界點(diǎn)定義的外接圓是相同的。因此，求點(diǎn)集P的最小包圍圓等價(jià)于求這些邊界點(diǎn)的最小包圍圓。

圖1 最小包圍圓由2個(gè)或3個(gè)邊界點(diǎn)確定

性質(zhì) 3 點(diǎn)集P中，距離最大的2個(gè)點(diǎn)A、B不一定都在邊界上，但是必有，這里d為點(diǎn)集P的最小包圍圓的長(zhǎng)度。

如圖2所示，點(diǎn)集P的最小包圍圓由等邊三角形ABC所定義，但是線段AD卻是最大的邊。顯然，線段AD為直徑的圓小于點(diǎn)集P的最小包圍圓。

證明見(jiàn)文獻(xiàn)[3]。

圖2 最長(zhǎng)線段不一定是最小包圍圓直徑

性質(zhì) 4 直角三角形或鈍角三角形的3個(gè)頂點(diǎn)的最小包圍圓是以最長(zhǎng)邊為直徑的圓；銳角三角形3個(gè)頂點(diǎn)的最小包圍圓是三角形的外接圓。

證明：（1）設(shè)直角三角形或鈍角三角形ABC的最大邊為AB，則A、B兩點(diǎn)確定的最小包圍圓是以AB為直徑的圓，則點(diǎn)C在圓上或者圓內(nèi)，如圖3(a)所示。根據(jù)引理1的前一部分知，A、B、C 3點(diǎn)確定的最小包圍圓還是以AB為直徑的圓。

（2）對(duì)于銳角三角形ABC，由于點(diǎn)C不屬于以AB為直徑的圓，因此，根據(jù)引理1的后一部分知點(diǎn)C在A、B、C三點(diǎn)確定的最小包圍圓DABC的邊界上；同理B和C也在最小包圍圓DABC的邊界上。不共線3點(diǎn)確定1個(gè)圓，所以DABC是A、B、C的外接圓，見(jiàn)圖3(b)。

上述性質(zhì)對(duì)于理解、構(gòu)造或者實(shí)現(xiàn)最小包圍圓算法有一定幫助。下面對(duì)幾個(gè)常用的、經(jīng)典的算法思想進(jìn)行簡(jiǎn)要介紹和分析。

圖3 不共線三點(diǎn)確定的最小包圍圓

1.2 改進(jìn)的隨機(jī)增量算法

Mark de Berg曾給出一種比較典型易于理解的隨機(jī)增量算法(randomized incremental algorithm, 簡(jiǎn)記為 RIA)[3]。 其主要思想是：第一，隨機(jī)打亂點(diǎn)集中所有點(diǎn)的順序；第二，以序列中前2個(gè)點(diǎn)構(gòu)造最小包圍圓D；第三，依次搜索其余的點(diǎn)，若某個(gè)點(diǎn)v在D外，則重新構(gòu)造最小包圍圓D'，使D'飽含D中的所有點(diǎn)且以v為邊界點(diǎn)。重復(fù)執(zhí)行第3步，直到求出最小包圍圓。

這個(gè)算法的關(guān)鍵在于第3步，以v作為邊界點(diǎn)構(gòu)造最小包圍圓，從而增加了構(gòu)造約束，減少了自由度。該算法的內(nèi)存耗用少，速度快。在隨機(jī)點(diǎn)集的條件下，期望運(yùn)行時(shí)間為O(n)。但是，若原始輸入序列是有序的，則打亂點(diǎn)集的順序也是需要耗費(fèi)時(shí)間的。

1.3 最遠(yuǎn)點(diǎn)優(yōu)先漸近算法

2000年汪衛(wèi)等提出一種準(zhǔn)確且快速的點(diǎn)集最小包圍圓算法[4]，即最遠(yuǎn)點(diǎn)優(yōu)先漸近算法，簡(jiǎn)記為DFAA。該算法的主要步驟是：第一，在點(diǎn)集中任取3個(gè)點(diǎn):A、B、C；第二，以這3個(gè)點(diǎn)構(gòu)造最小包圍圓D；第三，在點(diǎn)集P中查詢距離D的圓心最遠(yuǎn)的點(diǎn)v；若v在D內(nèi)則算法終止；否則，第四，在{A，B，C，v}中選取3個(gè)點(diǎn)，構(gòu)造包含這4個(gè)點(diǎn)的最小包圍圓D'，轉(zhuǎn)第二步驟，其中選取的這3個(gè)點(diǎn)盡可能是邊界上的點(diǎn)。

該算法實(shí)際上是一個(gè)確定性算法。主要的困難和時(shí)間耗費(fèi)在第四步。事實(shí)上，根據(jù)引理1，這一步是可以改進(jìn)的，因?yàn)樾录尤氲狞c(diǎn)v必定是新的最小圓的邊界點(diǎn)。于是這一步可以修改為：

以 v為邊界點(diǎn)，并在{ A，B，C }中選取 2個(gè)點(diǎn)，構(gòu)造包含這4個(gè)點(diǎn)的最小包圍圓D'，轉(zhuǎn)第二步驟，其中選取的這3個(gè)點(diǎn)盡可能是邊界上的點(diǎn)。

修改后的算法判斷會(huì)減少，從而加快運(yùn)行時(shí)間。第 3節(jié)的數(shù)值實(shí)驗(yàn)以修改后的算法（記為DFAA+）作為對(duì)比。該算法的時(shí)間復(fù)雜度為中R是所求的最小圓的半徑，d為點(diǎn)集中不在圓周上但距圓周最近的點(diǎn)到圓周的距離。實(shí)際應(yīng)用中，該算法時(shí)間復(fù)雜度是線性級(jí)的。

1.4 對(duì)偶決策算法

2005年Frank Nielsen提出一個(gè)快速近似的最小包圍圓算法[1]，這個(gè)算法通過(guò)求解一系列的對(duì)偶決策問(wèn)題(dual piercing Decision Problems)來(lái)實(shí)現(xiàn)，簡(jiǎn)記為DPs。該算法的主要思想是：第一，計(jì)算所有點(diǎn)在x軸上的投影區(qū)間[min x, max x]；第二，計(jì)算所有點(diǎn)到第1個(gè)點(diǎn)的距離最大值d1；第三，以4為初始半徑，以 ε =8為誤差控制，搜索區(qū)間為[maxx- r, minx+r]構(gòu)造對(duì)偶決策，并進(jìn)行迭代求解。其中，ε0為用戶指定的誤差控制閾值。

該算法優(yōu)點(diǎn)是不但能夠求出平面上點(diǎn)集的最小包圍圓，也能求出圓盤集的最小包圍圓。算法時(shí)間復(fù)雜度為，其中ε為最小包圍圓的誤差控制閾值，即該算法是一個(gè)近似算法。該算法的速度較快，也屬于線性階的，此外，算法基本屬于確定性算法，其最壞時(shí)間復(fù)雜性比平均時(shí)間復(fù)雜性略差。但是該算法設(shè)計(jì)比較復(fù)雜，內(nèi)存耗用比上述兩種算法大。

上面這3個(gè)常用算法以隨機(jī)增量算法影響比較大，我們的算法主要是對(duì)這個(gè)隨機(jī)增量算法進(jìn)行改進(jìn)，使其成為確定性算法，并加快求解時(shí)間。

2 較遠(yuǎn)點(diǎn)對(duì)定義初始包圍圓的增量算法

文獻(xiàn)[3]介紹的隨機(jī)增量算法試圖通過(guò)生成點(diǎn)集的隨機(jī)順序來(lái)避免最壞時(shí)間復(fù)雜性，從而優(yōu)化求解過(guò)程。事實(shí)上，這個(gè)目的可以通過(guò)調(diào)整距離較遠(yuǎn)的 2個(gè)點(diǎn)作為輸入的前 2個(gè)點(diǎn)而得以解決。之所以不用相距最遠(yuǎn)的2個(gè)點(diǎn)，是因?yàn)榍蠼庀嗑嘧钸h(yuǎn)的點(diǎn)對(duì)比較耗時(shí)。我們改進(jìn)算法的主要步驟是：

Step 1 計(jì)算點(diǎn)集P的軸定向包圍盒，并記錄分別屬于不同邊的4個(gè)邊界點(diǎn)，設(shè)為,，如圖4所示。軸定向包圍盒的邊界點(diǎn)或許超過(guò)4個(gè)，為了減少算法比較和內(nèi)存耗用，每條邊記錄1個(gè)邊界點(diǎn)。

圖4 計(jì)算點(diǎn)集的包圍盒信息

Step 2 計(jì)算這個(gè)軸定向包圍盒的寬(Bw)和高(Bh)。

Step 4 構(gòu)造包含p1,p2的最小圓。之后的步驟用第1.2節(jié)介紹的改進(jìn)的隨機(jī)增量算法。

根據(jù)性質(zhì)3易知，p1,p2確定的最小包圍圓是整個(gè)點(diǎn)集的最小包圍圓的子集。從這 4步 可以看出，本文的改進(jìn)算法是對(duì)改進(jìn)的隨機(jī)增量算法的初始包圍圓進(jìn)行了特定的初始化，使得初始包圍圓比較大，而計(jì)算這種軸定向包圍盒的時(shí)間復(fù)雜度是O(n)的，因而迭代次數(shù)減少，計(jì)算時(shí)間減少。更重要的是，這樣可以避免點(diǎn)集的最壞輸入順序，也不需要對(duì)輸入點(diǎn)集生成隨機(jī)順序。我們把這個(gè)算法稱為較遠(yuǎn)點(diǎn)對(duì)定義初始包圍圓的增量算法, 簡(jiǎn)記為FIIA。

3 實(shí) 驗(yàn)

數(shù)值驗(yàn)證實(shí)驗(yàn)是在個(gè)人臺(tái)式電腦上進(jìn)行。電腦的主要配置是：Intel(R) Core(TM)2 Extreme,CPU X9650@3.0GHz, 內(nèi)存為3.0G。

為了對(duì)比本文分析的3個(gè)經(jīng)典算法和本文的改進(jìn)算法，設(shè)計(jì)了4組數(shù)據(jù)：矩形域隨機(jī)點(diǎn)集、圓域隨機(jī)點(diǎn)集、共線隨機(jī)點(diǎn)集和共線有序點(diǎn)集。其中，前2個(gè)數(shù)據(jù)為二維區(qū)域隨機(jī)點(diǎn)集。

矩形域隨機(jī)點(diǎn)集的采樣區(qū)域?yàn)?/p>

采樣點(diǎn)選取為此區(qū)域內(nèi)的服從均勻分布的隨機(jī)數(shù)對(duì)。

圓域的隨機(jī)點(diǎn)集采樣區(qū)域?yàn)?/p>

共線隨機(jī)點(diǎn)集和共線有序點(diǎn)集都是來(lái)自于直線上的點(diǎn)，直線方程為

其中，本次實(shí)驗(yàn)的參數(shù)k=0.4。這2個(gè)點(diǎn)集的差別在于共線隨機(jī)點(diǎn)集的點(diǎn)序是隨機(jī)的，而共線有序點(diǎn)集是按照x坐標(biāo)遞增采樣。相鄰2個(gè)采樣點(diǎn)之間的間隔引入隨機(jī)數(shù)。這4個(gè)數(shù)據(jù)的采樣點(diǎn)個(gè)數(shù)和求取最小包圍圓的平均實(shí)驗(yàn)時(shí)間列在表1。其中平均實(shí)驗(yàn)時(shí)間為實(shí)驗(yàn)重復(fù)進(jìn)行 50次的平均運(yùn)行時(shí)間。表1中的RIA表示改進(jìn)的隨機(jī)增量算法(見(jiàn)第1.2節(jié))， DFAA+為改進(jìn)第四步后的最遠(yuǎn)點(diǎn)優(yōu)先漸進(jìn)算法(見(jiàn)第1.3節(jié))，DPs表示對(duì)偶決策近似算法(見(jiàn)第1.4節(jié))， FIIA為本文提出的較遠(yuǎn)點(diǎn)對(duì)定義初始包圍圓的增量算法(見(jiàn)第2節(jié))。表

1中各個(gè)數(shù)據(jù)的最優(yōu)時(shí)間用加粗的字表示。從表1可以看出，在本文羅列的3種經(jīng)典算法中，在對(duì)偶決策近似算法(DPs)時(shí)間開(kāi)銷最大。最遠(yuǎn)點(diǎn)優(yōu)先漸進(jìn)算法(DFAA+)最好。本文較遠(yuǎn)點(diǎn)對(duì)定義初始包圍圓的增量算法(FIIA)是對(duì)隨機(jī)增量算法(RIA)的改進(jìn)，時(shí)間效率大大提高，尤其是點(diǎn)集為共線的情況下，效果更加顯著。

表1 實(shí)驗(yàn)數(shù)據(jù)信息和平均運(yùn)行時(shí)間

實(shí)驗(yàn)數(shù)據(jù)的截圖如圖5所示，因?yàn)?個(gè)算法算出的圓心和半徑相同，故實(shí)驗(yàn)結(jié)果的截圖相同，因而也說(shuō)明各個(gè)算法的正確性。

圖5 實(shí)驗(yàn)數(shù)據(jù)及其最小包圍圓

實(shí)驗(yàn)中最小包圍圓的空間擴(kuò)展過(guò)程也可以顯示不同方法的收斂速度。這里我們把RIA算法和我們的FIIA算法進(jìn)行對(duì)比，如圖6所示。圖6中的實(shí)驗(yàn)包含 50個(gè)隨機(jī)點(diǎn)，每個(gè)子圖下方的數(shù)字表示前k個(gè)點(diǎn)確定的最小包圍圓。圖6中的第1行3個(gè)圖顯示RIA算法的最小包圍圓的動(dòng)態(tài)擴(kuò)展過(guò)程，第2行是我們的FIIA算法的運(yùn)行結(jié)果。

圖6 RIA和FIIA算法前k個(gè)點(diǎn)確定的最小包圍圓, (a)-(c)為RIA算法結(jié)果；(d)-(e)為FIIA算法結(jié)果。

對(duì)比2行的k值可以看出，RIA算法在前41個(gè)點(diǎn)時(shí)可以求得最小包圍圓。而我們的 FIIA算法，由于預(yù)處理中選取了距離較大的2個(gè)點(diǎn)作為前2個(gè)輸入點(diǎn)，因此收斂速度快很多，算法在計(jì)算到前 22個(gè)點(diǎn)時(shí)就求得了最小包圍圓?？梢?jiàn)，我們的改進(jìn)算法在收斂速度方面有明顯的優(yōu)勢(shì)。

4 結(jié) 論

關(guān)于離散點(diǎn)集的最小包圍圓問(wèn)題，本文首先概述了點(diǎn)集最小包圍圓的幾個(gè)主要性質(zhì)，這對(duì)于理解或構(gòu)造最小包圍圓算法有直接的影響。接著本文對(duì)隨機(jī)增量算法、最遠(yuǎn)點(diǎn)優(yōu)先漸近算法、對(duì)偶決策算法等當(dāng)前比較常用、比較典型的算法進(jìn)行分析和對(duì)比實(shí)驗(yàn)，結(jié)果表明過(guò)去的這3種算法中，汪衛(wèi)等 2000年構(gòu)造的最遠(yuǎn)點(diǎn)優(yōu)先漸近算法在時(shí)間效率方面最高。其間我們對(duì)最遠(yuǎn)點(diǎn)優(yōu)先漸近算法進(jìn)行了細(xì)微的改進(jìn)，減少了枚舉次數(shù)。

本文主要對(duì)隨機(jī)增量算法改進(jìn)，即用軸定向包圍盒邊界上的較遠(yuǎn)點(diǎn)對(duì)，作為隨機(jī)點(diǎn)集序列的前兩個(gè)元素，實(shí)現(xiàn)隨機(jī)增量算法的輸入點(diǎn)順序的優(yōu)化?；谶@一改進(jìn)，本文提出的這個(gè)算法稱為較遠(yuǎn)點(diǎn)對(duì)定義初始包圍圓的增量算法(FIIA)。我們的這個(gè)新算法是確定性算法，不再需要對(duì)點(diǎn)集的順序進(jìn)行隨機(jī)化處理，并且求取最小包圍圓的速度顯著提高。在工程實(shí)踐中，點(diǎn)集的軸向包圍盒往往在讀入數(shù)據(jù)時(shí)就已經(jīng)算好，因此，其結(jié)果能直接取代本算法的前兩步驟而獲得更好的時(shí)間性能。

[1]Frank N, Richard N. A fast deterministic smallest enclosing disk approximation algorithm [J].Information Processing Letters, 2005, 93(6): 263-268.

[2]Emo W. Smallest enclosing disks (balls and ellipsoids)[C]// Maurer H. (Ed.), New Results and New Trends in Computer Science, Lecture Notes in Computer Science, Heidelberg: Springer-Verlag,1991: 359-37.

[3][荷蘭]Mark de Berg, Marc van Kreveld, Mark Overmars, et al. 計(jì)算幾何: 算法與應(yīng)用(第2版)[M].鄧俊輝譯. 北京: 清華大學(xué)出版社, 2005: 99-103.

[4]汪 衛(wèi), 王文平, 汪嘉業(yè). 求一個(gè)包含點(diǎn)集所有點(diǎn)的最小圓的算法[J]. 軟件學(xué)報(bào), 2000, 11(9):1237-1240.