基于凸多邊形逼近的空間索引方法研究.pdf

1、一般來說，GIS所處理的空間目標(biāo)具有不規(guī)則的形狀，若基于它們的精確位置和擴(kuò)展來實(shí)現(xiàn)某些空間操作（如相鄰，包含等），其計算量會非常龐大。因此，一些近似的方法，如最小約束矩形法等，常常被用來表達(dá)具有不規(guī)則形狀的空間目標(biāo)?？臻g目標(biāo)近似表達(dá)方法可以簡化某些空間查詢過程，避免一些不必要的計算，從而可以有效地提高查詢效率。 本文采用凸多邊形（convex polygon）來近似表達(dá)空間目標(biāo)，凸多邊形是d維歐氏空間Rd中一個非空、有限的凸集。

2、對Rd中的一個集合，如果這個集合中的任意2個點(diǎn)，連接這2個點(diǎn)的線段被完全包含在該集合中，則該集合被稱作凸集。研究表明，對于任意一個空間目標(biāo)而言，這個目標(biāo)對應(yīng)的凸多邊形必然包含在該目標(biāo)對應(yīng)的最小約束矩形中。因此，凸多邊形能夠更精確地定義空間目標(biāo)的位置，減少不同空間目標(biāo)之間的重疊區(qū)域，從而可以更有效地實(shí)現(xiàn)空間查詢。 首先，本文分析了經(jīng)典的R-樹查詢方法，以及R*-樹，R+-樹的索引結(jié)構(gòu)及其各自的特點(diǎn)和缺點(diǎn)。 其次，進(jìn)一步的研