逆向工程中空間索引結(jié)構(gòu)的研究與優(yōu)化.pdf

1、逆向工程是近年來先進(jìn)制造技術(shù)領(lǐng)域的研究熱點(diǎn)和前沿性課題，其已經(jīng)發(fā)展為CAD/CAM系統(tǒng)中的一個相對獨(dú)立的分支。產(chǎn)品的逆向包括三維點(diǎn)云數(shù)據(jù)的采集、曲面重建、模型優(yōu)化及變形設(shè)計、數(shù)控刀軌生成等過程，其中各個過程所處理的空間數(shù)據(jù)具有散亂、數(shù)據(jù)量大等特點(diǎn)，且數(shù)據(jù)的拓?fù)溧徑P(guān)系查詢是逆向工程中的基本操作，故合理組織和索引散亂的空間數(shù)據(jù)是十分必要的。但現(xiàn)有的索引結(jié)構(gòu)在逆向工程中應(yīng)用具有局限性，且大部分是靜態(tài)索引，無法實(shí)現(xiàn)動態(tài)的增刪數(shù)據(jù)，索引對象單一

2、，對復(fù)雜的空間數(shù)據(jù)無能為力，故研究高效穩(wěn)定的空間索引結(jié)構(gòu)以提高空間查詢能力和效率是逆向工程設(shè)計迫切需要解決的問題。
　　針對索引結(jié)構(gòu)在逆向工程應(yīng)用的重要性以及目前索引結(jié)構(gòu)存在的問題，基于R*-樹提出了適用于逆向工程的索引結(jié)構(gòu)——R*-S樹，其采用新的優(yōu)化準(zhǔn)則對R*-樹進(jìn)行優(yōu)化。R*-S樹采用結(jié)點(diǎn)的MBR(最小外界矩形)的外接球的重疊度和體積評價結(jié)點(diǎn)的優(yōu)良，提高了建樹質(zhì)量。本課題基于R*-S樹在逆向工程中的應(yīng)用進(jìn)行了研究和優(yōu)化，主要

3、目標(biāo)是減少R*-S樹的結(jié)點(diǎn)重疊度及死區(qū)的體積，提高結(jié)點(diǎn)的內(nèi)聚性和R*-S樹的查詢效率，主要研究內(nèi)容及成果如下：
　　1.對現(xiàn)有結(jié)點(diǎn)分裂算法選軸分裂和基于最小生成樹的分裂算法進(jìn)行了闡述，并給出實(shí)例效果，分析了它們在R*-S樹中應(yīng)用的優(yōu)點(diǎn)以及缺陷。
　　2.基于現(xiàn)有的結(jié)點(diǎn)分裂算法分析知結(jié)點(diǎn)分裂的本質(zhì)是聚類問題，因此嘗試基于聚類思想進(jìn)行結(jié)點(diǎn)分裂，首先對聚類的基本概念及其經(jīng)典算法k-均值算法進(jìn)行了深入的闡述；隨后基于k-均值算法對R

4、*-S樹的結(jié)點(diǎn)進(jìn)行聚類，以實(shí)現(xiàn)結(jié)點(diǎn)的分裂；最后設(shè)計了對比實(shí)驗(yàn)，經(jīng)實(shí)例驗(yàn)證，該算法在建樹時間、結(jié)點(diǎn)的重疊度、k-近鄰查詢方面都具有顯著的優(yōu)越性，能較為真實(shí)的反應(yīng)結(jié)點(diǎn)的空間分布，提高結(jié)點(diǎn)的內(nèi)聚性和減少結(jié)點(diǎn)的重疊度，提高R*-S樹的查詢效率。
　　3.針對k-均值算法具有容易陷入局部最優(yōu)解和需要手動輸入?yún)?shù)k的問題，而遺傳算法具有較強(qiáng)的全局搜索能力，能彌補(bǔ)k-均值的缺陷，提出了基于遺傳多目標(biāo)優(yōu)化的結(jié)點(diǎn)自適應(yīng)聚類算法?；谶z傳多目標(biāo)優(yōu)化的