[發(fā)明專利]一種快速求解高維海量數(shù)據(jù)的凸包的方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201710508616.3
• 申請(qǐng)日: 2017-06-28
• 公開（公告）號(hào): CN107330048A
• 公開（公告）日: 2017-11-07
• 發(fā)明（設(shè)計(jì)）人: 劉潤(rùn)宗;唐遠(yuǎn)炎
• 申請(qǐng)（專利權(quán)）人: 重慶大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 北京同恒源知識(shí)產(chǎn)權(quán)代理有限公司11275
• 代理人: 趙榮之

1.一種快速求解高維海量數(shù)據(jù)的凸包的方法，其特征在于：包括以下步驟：

S1.把N維數(shù)據(jù)集中的每個(gè)數(shù)據(jù)視為一個(gè)點(diǎn)，求解數(shù)據(jù)集中的若干極值點(diǎn)；

S2.求解這些極值點(diǎn)構(gòu)成的初始凸包；

S3以點(diǎn)集重心為球心，求解該初始凸包的內(nèi)接球體；

S4利用該內(nèi)接球體排除冗余的內(nèi)部點(diǎn)；

S5對(duì)剩余的點(diǎn)，則利用其與初始凸包各個(gè)面的位置關(guān)系，判斷該點(diǎn)是否在初始凸包內(nèi)部，如果在內(nèi)部則刪除它；否則，把它加入離它最遠(yuǎn)的異側(cè)面對(duì)應(yīng)的外部點(diǎn)集；

S6在外部點(diǎn)集中求出離各個(gè)面最遠(yuǎn)的點(diǎn)，這些點(diǎn)也是凸包的頂點(diǎn)；新的凸包頂點(diǎn)與其所對(duì)應(yīng)的所有水平邊構(gòu)建多面體，刪除位于多面體內(nèi)部的點(diǎn)及異側(cè)面，把其余點(diǎn)加入該多面體的其它面中離它最遠(yuǎn)的異側(cè)面對(duì)應(yīng)的外部點(diǎn)集；

S7重復(fù)步驟S6，遞歸地求解出整個(gè)點(diǎn)集合的凸包。

2.根據(jù)權(quán)利要求1所述的一種快速求解高維海量數(shù)據(jù)的凸包的方法，其特征在于：所述步驟S2具體為：按N個(gè)極值點(diǎn)確定一個(gè)N-1維的超平面，求解由步驟S1中所述的極值點(diǎn)確定的滿足以下條件的所有超平面：所有極值點(diǎn)均位于該超平面的同一側(cè)；如果多個(gè)面位于同一超平面，則合并這些面；余下的面構(gòu)成點(diǎn)集的初始凸包。