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

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

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