海量點(diǎn)云Out-of-CoreR樹(shù)構(gòu)建及拓?fù)浣彶樵?xún).pdf

1、性能良好的R樹(shù)空間索引與局部型面特征參考數(shù)據(jù)對(duì)于曲面重建具有極其重要的意義。目前主流的R樹(shù)因構(gòu)建參數(shù)單目標(biāo)串行優(yōu)化導(dǎo)致子樹(shù)選取與結(jié)點(diǎn)分裂結(jié)果并不理想，當(dāng)點(diǎn)云非均勻分布、k值過(guò)小時(shí)，k近鄰點(diǎn)集作為局部參考數(shù)據(jù)并不能有效體現(xiàn)局部型面特征，且由于點(diǎn)云數(shù)據(jù)規(guī)模趨于海量，甚至超出主存容限，目前的R樹(shù)構(gòu)建及k近鄰查詢(xún)機(jī)制將無(wú)法使用。本文基于多目標(biāo)優(yōu)化改進(jìn)R樹(shù)中的子樹(shù)選取與結(jié)點(diǎn)分裂算法，利用主元分析擴(kuò)展搜索包圍球?qū)近鄰點(diǎn)集優(yōu)化以獲取拓?fù)浣忺c(diǎn)集，并

2、基于Out-of-Core策略，結(jié)合數(shù)據(jù)庫(kù)SQLite實(shí)現(xiàn)R樹(shù)索引Out-of-Core分級(jí)存儲(chǔ)機(jī)制與拓?fù)浣廜ut-of-Core查詢(xún)機(jī)制。主要研究?jī)?nèi)容如下：
　　(1)提出R樹(shù)形位多目標(biāo)聚類(lèi)構(gòu)建算法，將子樹(shù)選取視為多目標(biāo)優(yōu)化，其中將周長(zhǎng)增量、重疊度增量?jī)?yōu)化指標(biāo)作為決策向量，根據(jù)上溢結(jié)點(diǎn)子結(jié)點(diǎn)在各軸向的形位分布選取分裂軸，對(duì)候選分裂解以重疊度為指標(biāo)進(jìn)行聚類(lèi)過(guò)濾，并將周長(zhǎng)之和最小解作為結(jié)點(diǎn)分裂結(jié)果，從而避免了指標(biāo)因單目標(biāo)串行優(yōu)化而

3、導(dǎo)致 R樹(shù)性能下降的情況，使得結(jié)點(diǎn)分布與數(shù)據(jù)分布更具一致性，R樹(shù)性能有所提高。
　　(2)提出R樹(shù)索引的Out-of-Core構(gòu)建策略，將數(shù)據(jù)庫(kù)SQLite與R樹(shù)構(gòu)建相結(jié)合實(shí)現(xiàn)索引結(jié)點(diǎn)存儲(chǔ)于主存與數(shù)據(jù)點(diǎn)存儲(chǔ)于輔存的分級(jí)存儲(chǔ)機(jī)制，從而有效解決了因點(diǎn)云數(shù)據(jù)規(guī)模過(guò)大甚至超出主存限制的情況。
　　(3)提出主元分析導(dǎo)向自適應(yīng)擴(kuò)展的拓?fù)浣彶樵?xún)算法，利用過(guò)目標(biāo)點(diǎn)的第二主元平面分割k近鄰點(diǎn)集，根據(jù)小點(diǎn)集與近鄰點(diǎn)集點(diǎn)數(shù)比例與預(yù)設(shè)閾值的大小

4、確定是否擴(kuò)展搜索包圍球，使得每個(gè)目標(biāo)點(diǎn)實(shí)現(xiàn)自適應(yīng)拓?fù)浣彶樵?xún)，從而有效提高查詢(xún)效率，并設(shè)置搜索包圍球半徑的上限值，從而避免邊界、棱邊處點(diǎn)的無(wú)限查詢(xún)與相鄰曲面點(diǎn)的越界查詢(xún)，使得獲取的拓?fù)浣忺c(diǎn)集能夠有效體現(xiàn)局部型面特征。
　　(4)提出拓?fù)浣彽腛ut-of-Core查詢(xún)策略，首先在主存中獲取近鄰葉結(jié)點(diǎn)，然后利用數(shù)據(jù)庫(kù) SQLite從輔存中將近鄰葉結(jié)點(diǎn)包含的數(shù)據(jù)點(diǎn)讀入主存，繼而獲取目標(biāo)點(diǎn)的近鄰點(diǎn)。對(duì)于空間近鄰葉結(jié)點(diǎn)查詢(xún)，以目標(biāo)點(diǎn)與結(jié)