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

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

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

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