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

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


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

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