计算机应用
計算機應用
계산궤응용
COMPUTER APPLICATION
2014年
2期
406-410
,共5页
张丽平%李松%赵纪桥%郝晓红
張麗平%李鬆%趙紀橋%郝曉紅
장려평%리송%조기교%학효홍
空间数据库%Voronoi图%最近邻查询%单纯型连续近邻链%受限区域
空間數據庫%Voronoi圖%最近鄰查詢%單純型連續近鄰鏈%受限區域
공간수거고%Voronoi도%최근린사순%단순형련속근린련%수한구역
spatial database%Voronoi diagram%nearest neighbor query%Simple Continues Near Neighbor Chain (SCNNC)%constrained region
由于已有的最近邻查询方法无法直接处理受限区域内的单纯型连续近邻链查询问题,针对受限区域和障碍物的复杂性,详细研究了受限区域内无障碍物和有障碍物环境下的单纯型连续近邻链查询方法,分别提出了VOR_NB_CRSCNNC算法和VOR_CB_CRSCNNC算法.算法基于计算几何中的Voronoi图和判定圆域对空间数据对象进行预先筛选和计算,每次查询仅需考虑落在数量较少的Voronoi多边形和判定圆域内的数据点,预先过滤掉大量数据,减少每次计算涉及的数据量.理论研究和实验分析表明,所提出的算法在查询过程中减少了数据逐一判断的冗余计算,受受限区域形状的影响较小,较大程度提高了查询效率.
由于已有的最近鄰查詢方法無法直接處理受限區域內的單純型連續近鄰鏈查詢問題,針對受限區域和障礙物的複雜性,詳細研究瞭受限區域內無障礙物和有障礙物環境下的單純型連續近鄰鏈查詢方法,分彆提齣瞭VOR_NB_CRSCNNC算法和VOR_CB_CRSCNNC算法.算法基于計算幾何中的Voronoi圖和判定圓域對空間數據對象進行預先篩選和計算,每次查詢僅需攷慮落在數量較少的Voronoi多邊形和判定圓域內的數據點,預先過濾掉大量數據,減少每次計算涉及的數據量.理論研究和實驗分析錶明,所提齣的算法在查詢過程中減少瞭數據逐一判斷的冗餘計算,受受限區域形狀的影響較小,較大程度提高瞭查詢效率.
유우이유적최근린사순방법무법직접처리수한구역내적단순형련속근린련사순문제,침대수한구역화장애물적복잡성,상세연구료수한구역내무장애물화유장애물배경하적단순형련속근린련사순방법,분별제출료VOR_NB_CRSCNNC산법화VOR_CB_CRSCNNC산법.산법기우계산궤하중적Voronoi도화판정원역대공간수거대상진행예선사선화계산,매차사순부수고필락재수량교소적Voronoi다변형화판정원역내적수거점,예선과려도대량수거,감소매차계산섭급적수거량.이론연구화실험분석표명,소제출적산법재사순과정중감소료수거축일판단적용여계산,수수한구역형상적영향교소,교대정도제고료사순효솔.
