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

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

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

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