[發(fā)明專利]一種Voronoi Diagram與虛擬網(wǎng)格結(jié)合的高效空間最近鄰查詢方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310470050.1
• 申請(qǐng)日: 2013-10-10
• 公開（公告）號(hào): CN103559209A
• 公開（公告）日: 2014-02-05
• 發(fā)明（設(shè)計(jì)）人: 張重生
• 申請(qǐng)（專利權(quán)）人: 河南大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 鄭州聯(lián)科專利事務(wù)所(普通合伙) 41104
• 代理人: 劉建芳;李伊寧

1.一種Voronoi?Diagram與虛擬網(wǎng)格結(jié)合的高效空間最近鄰查詢方法，其特征在于，包括以下步驟：

A:使用Voronoi?Diagram劃分二維空間中的數(shù)據(jù)點(diǎn)，形成N個(gè)Voronoi?Cell，N為數(shù)據(jù)點(diǎn)個(gè)數(shù)，每個(gè)Voronoi?Cell為一個(gè)凸多邊形且僅包含1個(gè)數(shù)據(jù)點(diǎn)；

B:使用虛擬網(wǎng)格將二維空間劃分為若干個(gè)等大的正方形網(wǎng)格單元，確定網(wǎng)格單元的邊長，并對(duì)虛擬網(wǎng)格進(jìn)行編號(hào)；

C:設(shè)計(jì)計(jì)算虛擬網(wǎng)格單元和Voronoi?Cell之間的對(duì)應(yīng)關(guān)系的方法，并將該對(duì)應(yīng)關(guān)系存儲(chǔ)在一個(gè)哈希表中；

D:計(jì)算查詢點(diǎn)位置所在的網(wǎng)格單元，并確定查詢點(diǎn)位置所對(duì)應(yīng)的網(wǎng)格單元的編號(hào)；

E:根據(jù)步驟D中計(jì)算出的網(wǎng)格單元編號(hào)，在步驟C中所建立的存儲(chǔ)網(wǎng)格單元與Voronoi?Cell對(duì)應(yīng)關(guān)系的哈希表中，查找查詢點(diǎn)位置所在的網(wǎng)格單元所對(duì)應(yīng)的Voronoi?Cell，并從中計(jì)算選擇距離查詢點(diǎn)位置最近的數(shù)據(jù)點(diǎn)返回給用戶。

2.根據(jù)權(quán)利要求1所述的Voronoi?Diagram與虛擬網(wǎng)格結(jié)合的高效空間最近鄰查詢方法，其特征在于，所述的步驟B包括以下步驟：

B1:使用虛擬網(wǎng)格將二維空間劃分為若干個(gè)等大的正方形網(wǎng)格單元，通過公式（1）確定網(wǎng)格單元的邊長，其中，l為網(wǎng)格單元邊長，d為空間中所有兩點(diǎn)之間距離的最小值，ξ=10^-9；

B2:令R為數(shù)據(jù)集中的所有數(shù)據(jù)點(diǎn)所構(gòu)成的最小邊界矩形，以R的左下角的頂點(diǎn)(x₀,y₀)為出發(fā)點(diǎn)，建立虛擬網(wǎng)格，并從坐標(biāo)(x₀,y₀)所在的網(wǎng)格單元開始，從左到右、自下而上遞增地對(duì)網(wǎng)格單元進(jìn)行編號(hào)；計(jì)算坐標(biāo)點(diǎn)(x,y)所在的網(wǎng)格單元編號(hào)的公式為：

id=m*(ceil(y-y0l)-1)+ceil(x-x0l)-1;---(2)]]>

其中，id為坐標(biāo)點(diǎn)(x,y)所在的網(wǎng)格單元編號(hào)，m為網(wǎng)格的每一行所包含的網(wǎng)格單元的數(shù)量，ceil為上取整函數(shù)。

3.根據(jù)權(quán)利要求2所述的Voronoi?Diagram與虛擬網(wǎng)格結(jié)合的高效空間最近鄰查詢方法，其特征在于，所述的步驟C包括以下步驟：

C1:計(jì)算與每個(gè)Voronoi?Cell的各邊相交的網(wǎng)格單元：對(duì)于每一個(gè)Voronoi?Cell的任意一條邊的兩個(gè)端點(diǎn)e₀和e₁，計(jì)算邊e₀→e₁與縱向網(wǎng)格線和橫向網(wǎng)格線的交點(diǎn)；按照e₀到e₁方向，按照橫坐標(biāo)值的大小關(guān)系有序排列上述交點(diǎn)及e₀和e₁兩個(gè)頂點(diǎn)所組成的點(diǎn)的集合；對(duì)排序之后的集合中的所有點(diǎn)依次計(jì)算集合中所有相鄰兩點(diǎn)的中點(diǎn)，對(duì)每個(gè)中點(diǎn)使用步驟C中的公式(2)計(jì)算該中點(diǎn)所在的網(wǎng)格單元的編號(hào)，中點(diǎn)所在的網(wǎng)格單元所組成的集合即為與邊e₀→e₁相交的網(wǎng)格單元；

C2:計(jì)算Voronoi?Cell包含的網(wǎng)格單元：與任意一個(gè)Voronoi?Cell的各邊所相交的網(wǎng)格單元圍成的區(qū)域所包含的所有網(wǎng)格單元，即為Voronoi?Cell包含的網(wǎng)格單元；

C3:將與Voronoi?Cell相交和Voronoi?Cell包含的網(wǎng)格單元和該Voronoi?Cell的對(duì)應(yīng)關(guān)系存儲(chǔ)在一個(gè)哈希表中，哈希表的鍵key即為網(wǎng)格單元編號(hào)，哈希表的值value即為該網(wǎng)格單元對(duì)應(yīng)的Voronoi?Cell的編號(hào)。