近幾年,空間數(shù)據(jù)庫(kù)查詢(xún)技術(shù)在智能識(shí)別系統(tǒng)、地理信息系統(tǒng)等領(lǐng)域具有越來(lái)越主要的地位。在空間數(shù)據(jù)庫(kù)中,近鄰查詢(xún)是重要查詢(xún)類(lèi)型之一,但現(xiàn)有的最近鄰查詢(xún)并不能滿足現(xiàn)實(shí)需求,所以最近鄰查詢(xún)的研究方向已由理想情況過(guò)渡到復(fù)雜的障礙環(huán)境,由于現(xiàn)有的近鄰研究并沒(méi)有針對(duì)地理方向的解決方法,因此本文重點(diǎn)解決在空間數(shù)據(jù)庫(kù)中基于歐式環(huán)境、障礙環(huán)境的方向最近鄰查詢(xún)方法。首先,針對(duì)已有的最近鄰查詢(xún)方法,無(wú)法直接進(jìn)行某一指定地理方向空間的最近鄰查詢(xún)問(wèn)題,提出了方向最近鄰查詢(xún)方法。研究時(shí)分別從查詢(xún)點(diǎn)為靜態(tài)、查詢(xún)點(diǎn)做勻速運(yùn)動(dòng)的兩個(gè)情況進(jìn)行研究。在查詢(xún)點(diǎn)為靜態(tài)情況下,首先利用平面直角坐標(biāo)系與東西南北方向相結(jié)合的方式,提出了相應(yīng)的剪枝方法及算法;再根據(jù)Voronoi多邊形的最小外接矩形的性質(zhì),進(jìn)行具體的查詢(xún)并給出算法。在查詢(xún)點(diǎn)做勻速運(yùn)動(dòng)的情況下,首先利用平面直角坐標(biāo)系、東西南北方向與圓形相結(jié)合的方式,確定了查詢(xún)范圍;再根據(jù)運(yùn)動(dòng)軌跡與Voronoi圖的位置關(guān)系,利用Voronoi圖的性質(zhì)進(jìn)行具體的查詢(xún)。進(jìn)一步,由于現(xiàn)有的最近鄰查詢(xún)方法,無(wú)法在障礙環(huán)境下直接進(jìn)行某一指定地理方向空間的最近鄰查詢(xún)問(wèn)題,進(jìn)而提出了障礙環(huán)境下的方向最近... 

【文章來(lái)源】：哈爾濱理工大學(xué)黑龍江省

【文章頁(yè)數(shù)】：55 頁(yè)

【學(xué)位級(jí)別】：碩士

【部分圖文】：

查詢(xún)方向?yàn)闁|北方向的示意圖

哈爾濱理工大學(xué)工學(xué)碩士學(xué)位論文-8-圖2-2障礙環(huán)境下的Voronoi圖Fig.2-2Voronoidiagraminobstaclespace定義2.4阻礙。在Voronoi圖中，存在數(shù)據(jù)點(diǎn)pi，令點(diǎn)pi某個(gè)一階臨接Voronoi多邊形所對(duì)應(yīng)的數(shù)據(jù)點(diǎn)為pj。若在Voronoi圖中存在Oi，使得Dpipj∩Oi≠，則稱(chēng)數(shù)據(jù)點(diǎn)pi與數(shù)據(jù)點(diǎn)pj被阻礙，記為pi—|pj；否則稱(chēng)稱(chēng)數(shù)據(jù)點(diǎn)pi與數(shù)據(jù)點(diǎn)pj未被阻礙，記為pi—pj。定義2.5障礙距離。若數(shù)據(jù)點(diǎn)pi與數(shù)據(jù)點(diǎn)pj被阻礙，則稱(chēng)數(shù)據(jù)點(diǎn)pi到數(shù)據(jù)點(diǎn)pj的最近距離為障礙距離，記為OD(pi,pj)。定義2.6阻礙階數(shù)。若數(shù)據(jù)點(diǎn)pi與數(shù)據(jù)點(diǎn)pj被阻礙，且障礙距離OD(pi，pj)的長(zhǎng)度僅與一個(gè)障礙物有關(guān)，則稱(chēng)數(shù)據(jù)點(diǎn)pi與數(shù)據(jù)點(diǎn)pj被一階阻礙；若障礙距離OD(pi，pj)的長(zhǎng)度與k(k≥2)個(gè)障礙物有關(guān)，則稱(chēng)數(shù)據(jù)點(diǎn)pi與數(shù)據(jù)點(diǎn)pj被k階阻礙。2.3最近鄰查詢(xún)的基本方法傳統(tǒng)的最近鄰方法是基于R樹(shù)的深度優(yōu)先遍歷方法。隨后，國(guó)內(nèi)外就最近鄰查詢(xún)提出了很多方法，比如廣度優(yōu)先算法、采樣方法、對(duì)偶變換方法以及相對(duì)距離變換方法等。本節(jié)主要介紹比較典型的本文應(yīng)用的最近鄰查詢(xún)的基本方法。2.3.1基于Voronoi圖的查詢(xún)方法Voronoi圖是空間幾何的重要分支之一。它以某種距離作為度量，對(duì)平面進(jìn)行區(qū)域劃分。Voronoi圖的特性可以解決求最近點(diǎn)、最大空?qǐng)A、最小樹(shù)、n個(gè)平面點(diǎn)的凸包等問(wèn)題。

哈爾濱理工大學(xué)工學(xué)碩士學(xué)位論文-11-如圖3-1所示，查詢(xún)點(diǎn)q的所在的位置為運(yùn)動(dòng)的起點(diǎn)，運(yùn)動(dòng)的終點(diǎn)為z，查詢(xún)點(diǎn)q的運(yùn)動(dòng)方向?yàn)闁|北方向。當(dāng)查詢(xún)點(diǎn)q在起點(diǎn)時(shí)，采用傳統(tǒng)的最近鄰查詢(xún)時(shí)，根據(jù)歐氏距離得出的最近鄰應(yīng)為數(shù)據(jù)點(diǎn)p1，此時(shí)的運(yùn)動(dòng)距離為（Dqp1+Dp1z）；采用現(xiàn)有的方向最近鄰進(jìn)行查詢(xún)時(shí)，可能得出的方向最近鄰集為{p4，p5，p6，p7}。根據(jù)本章所提算法可以直接得出方向最近鄰結(jié)果為數(shù)據(jù)點(diǎn)p2，結(jié)果僅有一個(gè)數(shù)據(jù)點(diǎn)，且此時(shí)的運(yùn)動(dòng)距離為（Dqp4+Dp4z），（Dqp4+Dp4z）＜（Dqp1+Dp1z）。當(dāng)查詢(xún)點(diǎn)q運(yùn)動(dòng)時(shí)，根據(jù)所在的位置不同，得出的方向最近鄰不同，當(dāng)查詢(xún)點(diǎn)q移動(dòng)到q"時(shí)，此時(shí)的方向最近鄰結(jié)果為數(shù)據(jù)點(diǎn)p8；當(dāng)查詢(xún)點(diǎn)q移動(dòng)到q""時(shí)，此時(shí)的方向最近鄰結(jié)果為數(shù)據(jù)點(diǎn)p3；當(dāng)查詢(xún)點(diǎn)q移動(dòng)到q"""時(shí)，此時(shí)的方向最近鄰結(jié)果為數(shù)據(jù)點(diǎn)p7。圖3-1查詢(xún)方向?yàn)闁|北方向的示意圖Fig.3-1Whenthequerydirectionisnortheast3.2靜態(tài)查詢(xún)點(diǎn)下的方向最近鄰查詢(xún)?cè)诓樵?xún)點(diǎn)為靜態(tài)時(shí)的方向最近鄰查詢(xún)過(guò)程中，由于查詢(xún)某一指定方向上的最近鄰，其余方向上的數(shù)據(jù)集點(diǎn)是不需要考慮的，所以，本節(jié)提出的靜態(tài)查詢(xún)點(diǎn)下的方向最近鄰查詢(xún)包括兩個(gè)步驟，即數(shù)據(jù)預(yù)處理過(guò)程和方向最近鄰查詢(xún)過(guò)程。數(shù)據(jù)預(yù)處理過(guò)程通過(guò)建立平面直角坐標(biāo)系對(duì)數(shù)據(jù)集點(diǎn)的坐標(biāo)進(jìn)行正負(fù)判斷和比較，進(jìn)而得出所需方向的鄰近點(diǎn)集，這樣可以減少后續(xù)過(guò)程中計(jì)算量，縮短計(jì)算時(shí)間，并給出了剪枝算法。在方向最近鄰查詢(xún)過(guò)程中，通過(guò)構(gòu)造Voronoi圖和Voronoi多邊形的最小外接矩形，利用Voronoi圖的性質(zhì)，給出算法得到準(zhǔn)確的查詢(xún)結(jié)果。

【參考文獻(xiàn)】：
期刊論文
[1]障礙空間中不確定對(duì)象的組k最近鄰查詢(xún)方法[J]. 萬(wàn)靜,唐貝貝,孫健,何云斌,李松.  哈爾濱理工大學(xué)學(xué)報(bào). 2019(03)
[2]面向時(shí)間依賴(lài)路網(wǎng)的連續(xù)k近鄰查詢(xún)[J]. 李佳佳,李雨現(xiàn),夏秀峰,王波濤,劉向宇.  計(jì)算機(jī)科學(xué)與探索. 2019(05)
[3]障礙環(huán)境中線段組最近鄰查詢(xún)方法研究[J]. 郭瑩瑩,張麗平,李松.  計(jì)算機(jī)科學(xué). 2018(06)
[4]障礙環(huán)境下線段反k最近區(qū)域查詢(xún)方法研究[J]. 張麗平,任玲玲,郝曉紅,李松.  計(jì)算機(jī)科學(xué)與探索. 2018(10)
[5]路網(wǎng)環(huán)境下的最近鄰查詢(xún)技術(shù)[J]. 鮑金玲,王斌,楊曉春,朱懷杰.  軟件學(xué)報(bào). 2018(03)
[6]空間數(shù)據(jù)庫(kù)中基于Voronoi圖的線段組最近鄰查詢(xún)[J]. 郭瑩瑩,張麗平,李松.  小型微型計(jì)算機(jī)系統(tǒng). 2017(10)
[7]障礙空間中基于Voronoi圖的組反k最近鄰查詢(xún)研究[J]. 張麗平,劉蕾,郝曉紅,李松,郝忠孝.  計(jì)算機(jī)研究與發(fā)展. 2017(04)
[8]一種基于密度網(wǎng)格索引的k-最近鄰查詢(xún)算法[J]. 章登義,李想.  電子學(xué)報(bào). 2017(02)
[9]路網(wǎng)中線段反k最近鄰查詢(xún)研究[J]. 張麗平,郭瑩瑩,李松,李爽,樊瑞光.  計(jì)算機(jī)科學(xué)與探索. 2017(06)
[10]空間數(shù)據(jù)庫(kù)中基于Voronoi圖的組反k最近鄰查詢(xún)[J]. 張麗平,劉蕾,李松,于嘉希.  計(jì)算機(jī)科學(xué)與探索. 2016(10)



本文編號(hào)：3137547