李世林， 李紅軍

(北京林業(yè)大學(xué)理學(xué)院，北京 100083)

改進(jìn)的最小包圍球隨機(jī)增量算法

李世林， 李紅軍

(北京林業(yè)大學(xué)理學(xué)院，北京 100083)

三維空間中離散點(diǎn)集的最小包圍球，在碰撞檢測(cè)、計(jì)算幾何和模式識(shí)別等領(lǐng)域都有廣泛應(yīng)用。為了更好地理解和構(gòu)造最小包圍球算法，首先對(duì)最小包圍球的性質(zhì)進(jìn)行分析。然后，基于對(duì)隨機(jī)增量算法的分析，提出了構(gòu)造較大初始包圍球和減少迭代過(guò)程中最小包圍球更新次數(shù)兩種策略。依據(jù)后一種策略提出的方法稱為隨機(jī)點(diǎn)組-重算最遠(yuǎn)點(diǎn)算法。計(jì)算機(jī)隨機(jī)生成數(shù)據(jù)和現(xiàn)實(shí)三維模型采樣數(shù)據(jù)的多組實(shí)驗(yàn)結(jié)果表明，隨機(jī)點(diǎn)組-重算最遠(yuǎn)點(diǎn)算法相比于之前的經(jīng)典算法能夠有效地提高時(shí)間效率。

最小包圍球；隨機(jī)增量算法；隨機(jī)點(diǎn)組-重算最遠(yuǎn)點(diǎn)算法

對(duì)于三維空間中的離散點(diǎn)集P，求解其最小包圍球(minimum enclosing ball，MEB)以尋找一個(gè)半徑最小的球，其包含P中所有的點(diǎn)，球體有許多良好的性質(zhì)[1]，因此在計(jì)算機(jī)圖形學(xué)和計(jì)算幾何中，與離散點(diǎn)集的凸包圍多面體[2]相比，包圍球常作為邊界，可以更快地進(jìn)行近似的碰撞檢測(cè)、范圍界定和形狀分析。在空間數(shù)據(jù)庫(kù)中，MEB的求解可用于建立空間數(shù)據(jù)索引，以便提高查詢速度[3]。同時(shí)MEB問(wèn)題在模式識(shí)別[4]、計(jì)算幾何[5]、機(jī)器學(xué)習(xí)[6]等領(lǐng)域也有廣泛應(yīng)用。模型局部的包圍球可以用于模型裁剪[7]或者重采樣，因這些領(lǐng)域處理的數(shù)據(jù)集通常都是大規(guī)模的，所以提高M(jìn)EB算法運(yùn)行效率是很有必要的。

MEB問(wèn)題可以追溯到19世紀(jì)中期，Sylvester[8]在1857年提出了最小包圍圓問(wèn)題，并在1860年，給出了求解該問(wèn)題的一種近似線性算法[9]。之后人們開始系統(tǒng)地研究該問(wèn)題，比如最近的基于α-殼的最小包圍圓求解算法[10]，并研究從二維平面到三維空間再到更高維空間的算法；1982年，Megiddo[11]首次給出了一種理論上的線性時(shí)間算法，其時(shí)間復(fù)雜度是最小的，但算法本身的實(shí)現(xiàn)卻很復(fù)雜；1991年，Welzl[12]提出了一種簡(jiǎn)單快捷的隨機(jī)算法，其時(shí)間復(fù)雜度是線性級(jí)的，并指出該算法易于推廣到高維空間的 MEB和最小包圍橢球(minimum enclosing ellipsoid)中。后來(lái)，Berg等[5]對(duì)該方法進(jìn)行了進(jìn)一步的改進(jìn)，稱之為隨機(jī)增量算法(randomized incremental algorithm，RIA)，該算法是求解MEB問(wèn)題有代表性的經(jīng)典算法。分析該算法可看出，影響求解的時(shí)間效率主要因素是MEB更新的次數(shù)，因此提高算法效率的策略有2種：①構(gòu)造較大的初始 MEB；②修改迭代過(guò)程中的選點(diǎn)規(guī)則。在給出這兩種策略對(duì)應(yīng)的具體算法之前，為便于理解和構(gòu)造算法，先概述MEB的性質(zhì)。

1　離散點(diǎn)集的最小包圍球及其性質(zhì)

定義1. 點(diǎn)集P的MEB定義為：

其中， o*為最優(yōu)球心，r*為最優(yōu)半徑，表示Euclidean范數(shù)。

2012年，文獻(xiàn)[13]給出一系列有關(guān)最小包圍圓的性質(zhì)，這里對(duì)應(yīng)給出三維空間中MEB的有關(guān)性質(zhì)，這將有助于RIA的理解和實(shí)現(xiàn)。

性質(zhì)1. 三維空間中，有限離散點(diǎn)集的MEB是唯一的。

此性質(zhì)的證明見文獻(xiàn)[12]。

若P中只有一個(gè)點(diǎn)p1，則MEB是退化的，半徑為0，球心為點(diǎn)p1。

性質(zhì)2. 非退化的MEB可以由2～4個(gè)邊界點(diǎn)定義。

證明. 點(diǎn)集P的MEB的構(gòu)成有3種情況：

(1) 點(diǎn)集 P中距離最遠(yuǎn)的兩個(gè)點(diǎn)(p1,p2)作為邊界點(diǎn)，p1,p2兩點(diǎn)之間距離的一半作為球半徑，兩點(diǎn)連線段的中點(diǎn)作為球心。

(2) 點(diǎn)集P中任意3個(gè)點(diǎn)求其最小包圍圓，其中最大的圓半徑為r，圓心為o，確定該圓的那 3個(gè)點(diǎn)(p1,p2,p3)，若點(diǎn)集P中的任何一點(diǎn)與o之間的距離都小于r，則點(diǎn)集 P的 MEB的球心為o，半徑為r，邊界點(diǎn)是p1,p2,p3。

(3) 若有4個(gè)邊界點(diǎn)，那么點(diǎn)集P的MEB為這4個(gè)點(diǎn)所構(gòu)成的空間四面體的外接球。由空間幾何的知識(shí)可知，空間四面體的包圍球是唯一的，若邊界點(diǎn)多于4個(gè)，那么邊界點(diǎn)集中任意4個(gè)點(diǎn)所確定的MEB是等同的，都可以歸納為4個(gè)邊界點(diǎn)。

性質(zhì)3. 若點(diǎn)集P的MEB是由p1,p2,p3,p44個(gè)邊界點(diǎn)確定，那么這4個(gè)點(diǎn)的MEB是其所構(gòu)成的空間四面體的外接球。

引理1. 設(shè)點(diǎn)集P的子集的 MEB為Di：

(1) 若點(diǎn)pi+ 1∈ Di，則點(diǎn)集的 MEB為Di+1= Di；

(2) 若點(diǎn)pi+ 1? Di，則點(diǎn)pi+1必定是在點(diǎn)集 P′的MEB即Di+1的邊界上。

引理1是RIA的遞增思想，其證明可參考文獻(xiàn)[5]。

證明. 由性質(zhì) 3的條件可知，任意 3個(gè)點(diǎn)所確定的MEB都不包含第4個(gè)點(diǎn)。設(shè)p1,p2,p3所確定的MEB是球o，p4?o，由引理1可知，點(diǎn)p4是在點(diǎn)集的MEB的邊界上。同理p1,p2,p3也在其邊界上，又因?yàn)樗拿骟w的外接球是唯一的，所以該4個(gè)點(diǎn)的MEB是這4個(gè)點(diǎn)所構(gòu)成空間四面體的外接球 。

2　較大初始最小包圍球的隨機(jī)增量算法

Berg等[5]給出一種易于理解的RIA，該算法的思想與動(dòng)態(tài)規(guī)劃問(wèn)題中動(dòng)態(tài)維護(hù)最優(yōu)解有相似之處。根據(jù)文獻(xiàn)[5]中關(guān)于平面點(diǎn)集最小包圍圓 RIA的描述，容易給出三維空間MEB的RIA。

RIA還有很大的改進(jìn)空間，初始點(diǎn)對(duì)的選取直接影響到整個(gè)算法的迭代次數(shù)。傳統(tǒng)RIA只是隨機(jī)選取了兩個(gè)點(diǎn)作為初始MEB的直徑，盡管可以從平均意義上獲得比較好的時(shí)間效率且能避免最差的情況，但是迭代次數(shù)卻很大。本文采用較遠(yuǎn)兩點(diǎn)構(gòu)造較大初始 MEB，以便減少后續(xù)迭代過(guò)程中MEB的更新次數(shù)。

步驟1. 構(gòu)造較大初始MEB。在點(diǎn)集P中任取點(diǎn)p1，找出距離p1最遠(yuǎn)的點(diǎn)pi，再找出距離pi最遠(yuǎn)的點(diǎn)pj，以點(diǎn)pi,pj的連線作為直徑，構(gòu)造初始MEB，記為D2。此時(shí)的初始MEB大小相對(duì)于RIA更接近最優(yōu)的 MEB D的大小，迭代中重新構(gòu)造MEB的次數(shù)會(huì)變得更少，所以理論上改進(jìn)后的RIA效率比原始算法更高。

后續(xù)步驟采用經(jīng)典RIA，迭代更新當(dāng)前MEB。

步驟2. 設(shè)MEB D2的兩個(gè)點(diǎn)分別為p1,p2, 令i=3轉(zhuǎn)到步驟3。

步驟3. 檢驗(yàn)點(diǎn)pi，如果pi在包圍球Di-1中，那么MEB不變，即Di=Di-1；否則需根據(jù)性質(zhì)3重新構(gòu)造MEB Di。

步驟4. 令i=i+1，若i≤n，則轉(zhuǎn)到步驟3，否則算法終止，輸出Dn的半徑和球心。

顯然，步驟1的時(shí)間復(fù)雜度為O(n)，步驟2為O(1)，步驟 3與步驟 4構(gòu)成循環(huán)，時(shí)間復(fù)雜度為O(n)，因此該方法確定初始點(diǎn)對(duì)的時(shí)間復(fù)雜度也是O(n)。由于新的改進(jìn)算法在步驟1選取較大的包圍球，所以步驟3中的MEB重新構(gòu)造的次數(shù)會(huì)大大減少，因此新的算法能夠有效地提高時(shí)間效率，稱該算法為較大初始MEB的RIA，記為iRIA。

3　隨機(jī)點(diǎn)組-重算最遠(yuǎn)點(diǎn)算法

通過(guò)修改RIA迭代過(guò)程中的選點(diǎn)規(guī)則，提出了一種新算法，稱為隨機(jī)點(diǎn)組-重算最遠(yuǎn)點(diǎn)算法(random point group - recalculation the farthest point，R-RCF)。

3.1算法介紹

步驟1. 將P中各點(diǎn)打亂成一個(gè)隨機(jī)排列p1,p2,···,pn。

步驟2. 作前4個(gè)點(diǎn)p1, p2,p3,p4確定的MEB。根據(jù)性質(zhì)2和性質(zhì)3，球的邊界可能通過(guò)這4個(gè)點(diǎn)(4點(diǎn)的外接球)；也可能只通過(guò)其中的3個(gè)點(diǎn)(3點(diǎn)的外接圓構(gòu)成球的最大截圓)，但包含第4點(diǎn)；還可能只通過(guò)其中的兩個(gè)點(diǎn)，后一種情況球邊界上的兩點(diǎn)一定是位于球的一條直徑的兩端。令i=5，轉(zhuǎn)到步驟3。

步驟3. 考察點(diǎn)pi，如果該點(diǎn)位于球外部，轉(zhuǎn)到步驟4。否則，令i=i+1，若i≤n，執(zhí)行步驟3；若i＞n，執(zhí)行步驟5。

步驟4. 根據(jù)引理1，在p1,p2,p3,p4中任意選擇3個(gè)點(diǎn)，加上pi，構(gòu)造包含這5個(gè)點(diǎn)的MEB，且半徑是所有滿足條件所構(gòu)造的MEB中最小的，此時(shí)確定該MEB的4個(gè)點(diǎn)記為新的 p1,p2,p3,p4，令i=i+1，若i≤n，執(zhí)行步驟3；若i＞n，執(zhí)行步驟5。

步驟5. 在點(diǎn)集P中找出距離MEB的球心最遠(yuǎn)點(diǎn)F。若F點(diǎn)已在球內(nèi)或球邊界上，則該球即為所求的球，算法結(jié)束。否則，執(zhí)行步驟6。

步驟6. 以F為邊界點(diǎn)，在點(diǎn)集｛p1, p2, p3, p4｝中選擇3個(gè)點(diǎn)和點(diǎn)F一起構(gòu)造新的MEB，使得這5個(gè)點(diǎn)都在球內(nèi)，且半徑是所構(gòu)造的MEB中最小的，此時(shí)選擇的3個(gè)點(diǎn)和點(diǎn)F記作新的 p1, p2,p3,p4，轉(zhuǎn)到步驟5。

R-RCF將求解MEB問(wèn)題分為2部分進(jìn)行：①動(dòng)態(tài)更新最優(yōu)解利用了RIA的核心思想，該算法的優(yōu)點(diǎn)是每次迭代所需的計(jì)算量遠(yuǎn)遠(yuǎn)小于RIA，但缺點(diǎn)是每次更新最優(yōu)解會(huì)遺漏少部分已經(jīng)位于上一步的MEB內(nèi)部的點(diǎn)。②重算遺漏部分則是利用了最遠(yuǎn)點(diǎn)依次選取算法的思想[14]，且相對(duì)于最遠(yuǎn)點(diǎn)依次選取算法，該部分迭代次數(shù)更少，同時(shí)又重算了動(dòng)態(tài)更新中所遺漏的部分，彌補(bǔ)了動(dòng)態(tài)更新最優(yōu)解的缺點(diǎn)。本文稱該算法為R-RCF。

3.2算法分析

3.2.1算法重算部分的必要性

由于R-RCF算法在步驟4動(dòng)態(tài)更新最優(yōu)解的過(guò)程中會(huì)遺漏少部分已經(jīng)包含在球內(nèi)部的點(diǎn)，所以該算法加入了步驟5和步驟6，對(duì)步驟4動(dòng)態(tài)更新最優(yōu)解的過(guò)程中所遺漏的區(qū)域進(jìn)行重算。為了更形象地說(shuō)明該問(wèn)題，以二維平面最小包圍圓為例進(jìn)行分析。

如圖1所示，ci是點(diǎn)ABC所確定的最小包圍圓，當(dāng)遍歷到點(diǎn)D時(shí)，由于點(diǎn)D不在ci里，所以需要更新最小包圍圓，ci+1是滿足算法步驟 4的圓，此時(shí)s區(qū)域內(nèi)遍歷過(guò)的點(diǎn)已經(jīng)不包含于更新后的最小包圍圓中，要想使其重新位于最小包圍圓中，就需要對(duì)該區(qū)域進(jìn)行重算。該算法根據(jù)參考文獻(xiàn)[14]中算法的步驟3，采用重算最遠(yuǎn)點(diǎn)的方法進(jìn)行重算，同時(shí)該算法動(dòng)態(tài)更新最優(yōu)解的思想恰是參考RIA，且利用邊界點(diǎn)動(dòng)態(tài)更新最優(yōu)解。

圖1　R-RCF更新最優(yōu)解時(shí)遺漏s區(qū)域的點(diǎn)

3.2.2算法收斂性

本節(jié)要證明上述 R-RCF算法一定能終止，且最后一次求得的MEB就是包含點(diǎn)集P中所有點(diǎn)的MEB。

引理2. 算法步驟4和步驟6所生成的MEB的半徑是遞增的。

證明. 設(shè)步驟4生成的包含A, B, C, D 4點(diǎn)的MEB為B1，半徑為 r1；當(dāng)考慮球外的點(diǎn)E后，生成的包含A, B, C, D, E 5點(diǎn)的MEB記為B2，半徑為r2，顯然B2包含A, B, C, D 4點(diǎn)?？紤]到B2的構(gòu)造，會(huì)有B2≠B1。若r1=r2，與空間離散點(diǎn)集的 MEB的唯一性存在矛盾；若r1＞r2，與點(diǎn)A, B, C, D的MEB為 B1也存在矛盾；所以r1＜r2，即更新后的MEB半徑比原MEB的半徑大。

定理1. 上述R-RCF算法是收斂的，且最后一次得到的MEB是包含點(diǎn)集P中所有點(diǎn)的MEB。

證明. 因?yàn)樵邳c(diǎn)集P中任取4個(gè)點(diǎn)、3個(gè)點(diǎn)或2個(gè)點(diǎn)所生成的MEB的個(gè)數(shù)是有限的。由引理2可知，算法進(jìn)行過(guò)程中所生成的MEB半徑是遞增的，經(jīng)過(guò)有限次迭代后，可求得這些最小球中半徑最大的一個(gè)。從算法步驟5可知，只有當(dāng)點(diǎn)集P中所有點(diǎn)都在由4個(gè)點(diǎn)、3個(gè)點(diǎn)或2個(gè)點(diǎn)生成的MEB內(nèi)部時(shí)，算法結(jié)束，因而最后得到的MEB會(huì)是包含點(diǎn)集P中所有點(diǎn)的MEB。

4　實(shí)驗(yàn)驗(yàn)證

上述算法的實(shí)驗(yàn)是在筆記本電腦上進(jìn)行的，計(jì)算機(jī)配置是 Intel(R) Core(TM) i3-2310M CPU @ 2.10 GHz處理器和 6 GB內(nèi)存，程序運(yùn)行環(huán)境MATLAB R2012a。實(shí)驗(yàn)針對(duì)RIA，iRIA和R-RCF的時(shí)間效率進(jìn)行對(duì)比，實(shí)驗(yàn)數(shù)據(jù)分為兩類：計(jì)算機(jī)隨機(jī)生成點(diǎn)集(簡(jiǎn)稱為隨機(jī)點(diǎn)集)和現(xiàn)實(shí)對(duì)象采集的三維點(diǎn)集(簡(jiǎn)稱為采樣點(diǎn)集)。

4.1實(shí)驗(yàn)比較

為了對(duì)比在不同規(guī)模下的數(shù)據(jù)求取MEB的時(shí)間效率，設(shè)計(jì)了10組點(diǎn)集，點(diǎn)數(shù)n分別是100，200，300，400，500，1 000，2 000，3 000，4 000，5 000，每組數(shù)據(jù)分別進(jìn)行500次實(shí)驗(yàn)。隨機(jī)點(diǎn)集的生成范圍有2種，矩形域隨機(jī)點(diǎn)集和球形域隨機(jī)點(diǎn)集。

實(shí)驗(yàn) 1. 是矩形域隨機(jī)點(diǎn)集，隨機(jī)點(diǎn)按照均勻分布產(chǎn)生于一個(gè)單位正方體，如下式：

表 1是在矩形域上采樣所得出的實(shí)驗(yàn)數(shù)據(jù)，Red1表示iRIA相對(duì)于RIA的時(shí)間壓縮比，Red2表示R-RCF相對(duì)于RIA的時(shí)間壓縮比。從表1可看出，本文提出的 iRIA算法在時(shí)間代價(jià)方面能壓縮 8%以上，且隨著點(diǎn)數(shù)的增加，時(shí)間效率的提升越來(lái)越高。而本文提出的 R-RCF算法在時(shí)間代價(jià)方面能壓縮66%以上，這將大幅度地提高求解MEB的時(shí)間運(yùn)行效率。MEB的實(shí)驗(yàn)效果如圖2(a)所示。

表1　矩形域上不同點(diǎn)數(shù)的平均運(yùn)行時(shí)間比較

實(shí)驗(yàn)2. 針對(duì)球形域隨機(jī)點(diǎn)集進(jìn)行，隨機(jī)點(diǎn)按照均勻分布產(chǎn)生于一個(gè)平移后的單位球。

球形域上MEB的求取效果如圖2(b)所示。實(shí)驗(yàn)結(jié)果見表2。從時(shí)間效率上看，本文所提出的iRIA算法由于第一步計(jì)算較遠(yuǎn)的兩個(gè)點(diǎn)增加了不少時(shí)間，同時(shí)，由于球形域點(diǎn)集形狀對(duì)稱的特點(diǎn)，本文改進(jìn)后的 iRIA算法并不能有效地減少迭代次數(shù)，所以總時(shí)間代價(jià)上表現(xiàn)的略差些。但是本文提出的R-RCF算法在計(jì)算球形域點(diǎn)集的MEB在時(shí)間代價(jià)上能壓縮71%以上。

圖2　離散點(diǎn)集最小包圍球計(jì)算結(jié)果

表2　球形域上不同點(diǎn)數(shù)的平均運(yùn)行時(shí)間比較

在表2中，由于RIA和iRIA的運(yùn)行時(shí)間相差并不大，故進(jìn)行了方差未知均值相等(H0:μ1=μ2)的假設(shè)驗(yàn)證。當(dāng)取顯著性水平為0.05時(shí)，接受H0，即認(rèn)為此兩種算法針對(duì)球形區(qū)域的時(shí)間效率無(wú)顯著差異。

4.2采樣點(diǎn)集的最小包圍球

在三維游戲制作或者三維激光測(cè)量中，需獲得各種形狀的點(diǎn)云數(shù)據(jù)。為了驗(yàn)證RIA、iRIA和R-RCF針對(duì)不同復(fù)雜數(shù)據(jù)的時(shí)間效率，將進(jìn)行MEB計(jì)算，針對(duì)6個(gè)現(xiàn)實(shí)對(duì)象采集的三維點(diǎn)集，分別為網(wǎng)絡(luò)公開數(shù)據(jù)庫(kù)(http://visionair.ge.imati.cnr.it/ontologies/shapes/)人手、花瓶和佛像模型的采樣點(diǎn)集，以及實(shí)驗(yàn)室掃描數(shù)據(jù)：樹1、樹2和場(chǎng)景模型，如圖3所示。

圖3　現(xiàn)實(shí)三維模型采集數(shù)據(jù)的最小包圍球

6組數(shù)據(jù)的點(diǎn)數(shù)和3種算法的時(shí)間及其效率比較見表3，其中運(yùn)行時(shí)間是實(shí)驗(yàn)重復(fù)30次的平均運(yùn)行時(shí)間。從表3看出，本文提出的改進(jìn)算法iRIA的平均運(yùn)行時(shí)間比RIA快10%～33%，R-RCF比RIA 快51%～93%。具體來(lái)說(shuō)，iRIA與RIA之間的比較效果：對(duì)于比較“修長(zhǎng)”的點(diǎn)集數(shù)據(jù)模型，如人手模型、樹1模型和樹2模型，iRIA的程序運(yùn)行效率比RIA提高了22%以上，這是因?yàn)閷?duì)于該類的點(diǎn)集數(shù)據(jù)模型，iRIA算法改進(jìn)的初始值能大大減少求解MEB的迭代次數(shù)，這與矩形域隨機(jī)點(diǎn)集得出的結(jié)論一致；而對(duì)于一些比較“飽滿”的點(diǎn)集數(shù)據(jù)模型，如花瓶模型、佛像模型和場(chǎng)景模型，iRIA的程序運(yùn)行效率比RIA提高的程度明顯低于“修長(zhǎng)”的點(diǎn)集數(shù)據(jù)模型，這與球形域隨機(jī)點(diǎn)集得出的結(jié)論一致。從表3中的實(shí)驗(yàn)結(jié)果可以看出，針對(duì)不同形狀的采樣點(diǎn)集，iRIA算法的運(yùn)行效率普遍高于RIA。R-RCF與RIA之間的比較效果：對(duì)于比較“飽滿”的點(diǎn)集數(shù)據(jù)模型，R-RCF的程序運(yùn)行效率比RIA提高了89%以上?？梢?，針對(duì)不同形狀的大規(guī)模點(diǎn)集，本文提出的新算法R-RCF的運(yùn)行效率遠(yuǎn)高于原始算法，同時(shí)，對(duì)于“飽滿”的點(diǎn)集數(shù)據(jù)模型，效果尤其明顯，這將為計(jì)算離散點(diǎn)集的MEB的工程應(yīng)用節(jié)省大量的時(shí)間。

表3　3種算法針對(duì)激光掃描點(diǎn)云數(shù)據(jù)的平均運(yùn)行時(shí)間比較

5　結(jié) 束 語(yǔ)

針對(duì)三維空間中求取離散點(diǎn)集MEB問(wèn)題，為便于構(gòu)造求解MEB的算法，本文先概述了三維空間中離散點(diǎn)集的MEB的幾條主要性質(zhì)。在分析求解MEB的RIA的基礎(chǔ)上，提出一種稱為較大初始MEB的 RIA，這種算法通過(guò)在第一階段選取較遠(yuǎn)點(diǎn)對(duì)構(gòu)造初始 MEB，有效地減少了第二階段的MEB更新次數(shù)，提高了算法的時(shí)間效率。同時(shí)，本文又提出了一種新算法，稱之為R-RCF，該算法通過(guò)減少迭代過(guò)程中MEB的更新次數(shù)，大幅度提高了時(shí)間效率。通過(guò)隨機(jī)數(shù)據(jù)和現(xiàn)實(shí)三維模型采樣數(shù)據(jù)等多組實(shí)驗(yàn)驗(yàn)證，結(jié)果表明，與原始RIA相比，本文提出的R-RCF算法能大幅度的提高時(shí)間效率。本文算法分析詳細(xì)，有助于學(xué)生或者工程技術(shù)人員在算法實(shí)現(xiàn)過(guò)程中較好地處理相關(guān)細(xì)節(jié)。

此外，因?yàn)樽钚“j(luò)長(zhǎng)方體比MEB更加接近物體表面，所以參考本文的研究思路和二維空間中最狹長(zhǎng)包絡(luò)矩形的求解原理及方法[15]，研究三維空間的最小包絡(luò)長(zhǎng)方體的快速計(jì)算是未來(lái)的一個(gè)研究方向。

[1] Hu P, Xu D, Li H. A normalization method of moment invariants for 3D objects on different manifolds [J]. Computer Aided Drafting, Design and Manufacturing, 2014, 24(2): 15-22.

[2] 唐磊, 施侃樂(lè), 雍俊海, 等. 模型適應(yīng)的凸包圍多面體并行生成算法[J]. 中國(guó)科學(xué): 信息科學(xué), 2014, 44(12): 1515-1526.

[3] Samet H. The design and analysis of spatial data structures [M]. New Jersey: Addison Wesley Press, 1990: 86-89.

[4] 來(lái)疆亮, 王守覺. 最小球覆蓋幾何算法及其在模式識(shí)別中的應(yīng)用[J]. 模式識(shí)別與人工智能, 2006, 19(2): 271-276.

[5] Berg M D, Jreveld M V. Overmars M, et al. 計(jì)算幾何:算法與應(yīng)用[M]. 鄧俊輝, 譯. 北京: 清華大學(xué)出版社, 2005: 99-103.

[6] Ben-Hur A, Horn D, Siegelmann H T, et al. Support vector clustering [J]. Journal of Machine Learning Research, 2001, 2(2): 125-137.

[7] 耿博, 張慧娟, 王衡, 等. 離散曲面的近似 Poisson盤采樣[J]. 中國(guó)科學(xué): 信息科學(xué), 2012, 42(6): 703-716.

[8] Sylvester J J. A question on the geometry of situation [J]. The Quarterly Journal of Pure and Applied Mathematics, 1857, (1): 79.

[9] Sylvester J J. On Poncelet’s approximate linear valuation of surd forms [J]. Philosophical Magazine, 1860, 20(132): 203-222.

[10] 張勇, 陳強(qiáng). 一種基于計(jì)算幾何方法的最小包容圓求解算法[J]. 工程圖學(xué)學(xué)報(bào), 2007, 28(3): 97-101.

[11] Megiddo N. Linear-time algorithms for linear programming in R3 and related problems [J]. Siam Journal of Computing. IEEE, 1983, 12(4): 329-338.

[12] Welzl E. Smallest enclosing disks (balls and ellipsoids) [J]. Lecture Notes in Computer Science, 1991, 555(1): 359-370.

[13] 李紅軍, 張曉鵬. 離散點(diǎn)集最小包圍圓算法分析與改進(jìn)[J].圖學(xué)學(xué)報(bào), 2012, 33(2): 34-38.

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

[15] 周敏, 鄭國(guó)磊, 陳樹林. 二維圖形最狹長(zhǎng)包絡(luò)矩形的求解原理及方法[J]. 圖學(xué)學(xué)報(bào), 2013, 34(4): 46-53.

An Im proved Random ized Incremental A lgorithm for Generating M inimum Enclosing Ball of Discrete Point Set

Li Shilin,Li Hongjun

(College of Science, Beijing Forestry University, Beijing 100083, China)

The minimum enclosing ball (MEB) of discrete point set in the 3D space has been w idely used in many fields, such as collision detection, computational geometry, pattern recognition and so on. In order to better understand and construct MEB, its character is analyzed firstly. A fter analyzing the classical randomized incremental algorithm, we propose two strategies to improve time efficiency. One strategy is to construct a bigger initial enclosing ball and another strategy is to decrease the number of updating MEB. Based on the second strategy, a new algorithm called random point group-recalculation farthest point is proposed. Multi-group experimental results, whose data are both random ly generated by computer and realistic 3D model sampling, show that the random point group-recalculation farthest point algorithm can effectively improve the time efficiency compared with the classical algorithms.

minimum enclosing ball; randomized incremental algorithm; random point grouprecalculation farthest point

TP 391

10.11996/JG.j.2095-302X.2016020166

A

2095-302X(2016)02-0166-06

2015-09-24；定稿日期：2015-10-03

國(guó)家自然科學(xué)基金項(xiàng)目(61372190)

李世林(1992–)，男，山東青島人，碩士研究生。主要研究方向?yàn)橛?jì)算幾何。E-mail：lishilin_2015@bjfu.edu.cn

李紅軍(1969–)，男，湖南郴州人，副教授，博士。主要研究方向?yàn)橛?jì)算機(jī)圖形學(xué)和計(jì)算幾何等。E-mail：lihongjun69@bjfu.edu.cn