基于泰森多邊形的數(shù)據(jù)區(qū)域索引與檢索系統(tǒng)

2萬字 73頁 包括外文翻譯，原創(chuàng)作品，通過查重系統(tǒng)


摘 要
荷蘭氣候?qū)W家AR26;HR26;Thiessen為解決用離散氣象站降雨量計算平均降雨量提出了泰森多邊形。泰森多邊形因為其優(yōu)良的特性應(yīng)用在各個領(lǐng)域，其中最為普遍的是最近鄰點的判斷，在平面上所有站點的泰森多邊形生成的情況下，不需要再計算比較目標(biāo)查詢點與各個站點之間的距離，可以直接判斷目標(biāo)查詢點位于哪一個泰森多邊形中，該泰森多邊形對應(yīng)的離散點即為目標(biāo)查詢點的最近鄰點。
本文旨在研究考慮利用泰森多邊形的空間劃分特性，設(shè)計實現(xiàn)區(qū)間索引機制，主要工作包括：
（1）實現(xiàn)泰森多邊形的圖形化展示；
（2）考慮采用高效的算法實現(xiàn)平面上任意點最近鄰的有效檢索；
（3）計算平面內(nèi)給定矩形區(qū)域所覆蓋的泰森多邊形。
通過上述工作得出以下結(jié)論：
（1）泰森多邊形在區(qū)間索引上的應(yīng)用是可行的，可以有效提高檢索效率；
（2）在實現(xiàn)泰森多邊形的過程中，利用一些優(yōu)化算法可以降低時間復(fù)雜度，提高圖形的生成效率，在最近鄰查詢方面也通過優(yōu)化算法減小計算量提高了查詢的效率。

關(guān)鍵詞：Delaunay三角網(wǎng);泰森多邊形;最近鄰;區(qū)域查詢