空間數(shù)據(jù)庫平面線段集幾何問題研究.pdf

1、在計算機技術(shù)蓬勃發(fā)展的時期,空間數(shù)據(jù)庫在計算機視覺、圖像識別、環(huán)境保護、計算幾何、地理信息系統(tǒng)(GIS)以及數(shù)字地球等領(lǐng)域被廣泛地應(yīng)用。平面線段集幾何問題是空間數(shù)據(jù)庫幾何問題中具有重要應(yīng)用價值的一個內(nèi)容。
　　 平面線段集幾何問題可以有針對性地解決把空間物體抽象為線段的情形。在實際應(yīng)用中,許多問題都可以歸結(jié)為平面線段集的凸殼問題；在圖形學、科學計算可視化等領(lǐng)域經(jīng)常需要解決平面線段集的三角剖分問題,平面線段集三角剖分算法的重要部分

2、是降低算法的復(fù)雜度和形成高質(zhì)量的三角網(wǎng)格；在近鄰查詢中經(jīng)常會遇到平面線段集近鄰查詢問題,在平面線段集的近鄰查詢中有效的索引平面線段,可以大大加快查詢的速度。
　　 本文完成了以下三個方面的研究:
　　 1.平面線段集的凸殼問題。對簡單多邊形鏈、平面線段集所具有的不同于點集的性質(zhì)進行研究,提出了一種求解簡單多邊形鏈凸殼的新算法和一種求解平面線段集凸殼的新算法。
　　 2.平面線段集的三角剖分問題。系統(tǒng)的分析空間數(shù)據(jù)

3、庫平面線段集三角剖分的算法,總結(jié)各種不同算法的優(yōu)缺點,結(jié)合線段集凸殼,提出了新的平面線段集與平面點線集三角剖分算法。
　　 3.平面線段集的近鄰查詢問題。研究R樹、R+樹、R*樹、四叉樹在索引平面線段集時的優(yōu)缺點,并對缺點進行改進,提出了一種新的平面線段集索引結(jié)構(gòu)即RP-樹。在散亂的互不相交的大量平面線段集中應(yīng)用此索引結(jié)構(gòu)可以提高求解線段集最近鄰問題的效率。本文以RP-樹為基礎(chǔ)提出了一個新的時間復(fù)雜度為O(logk n)的平面線