基于Voronoi图的定性路径

doi:10.3778/j.issn.1002-8331.2009.21.056

计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (21): 193-196.DOI: 10.3778/j.issn.1002-8331.2009.21.056

基于Voronoi图的定性路径

王晓东^1，2，廖士中¹

1.天津大学计算机科学与技术学院，天津 300072
2.牡丹江师范学院物理系，黑龙江牡丹江 157012

收稿日期:2009-05-05 修回日期:2009-06-22 出版日期:2009-07-21 发布日期:2009-07-21
通讯作者: 王晓东

Qualitative path based on Voronoi diagram

WANG Xiao-dong ^1，2，LIAO Shi-zhong¹

1.School of Computer Science and Technology，Tianjin University，Tianjin 300072，China
2.Department of Physics，Mudanjiang Teachers College，Mudanjiang，Heilongjiang 157012，China

Received:2009-05-05 Revised:2009-06-22 Online:2009-07-21 Published:2009-07-21
Contact: WANG Xiao-dong

摘要/Abstract

摘要： 定性路径是定性空间推理的一个基本概念。给出了一个基于Voronoi图的定性路径表示与推理方法。该方法应用Voronoi图的邻近关系来表示定性位置和定性路径，即用运动点所在Voronoi区域的邻域来表示定性位置，用运动点所经过的定性位置序列来表示定性路径。设计并实现了一个定性路径推理算法，基于初始Voronoi图及不同时刻所有Voronoi区域的边数来动态更新Voronoi图邻近关系，可识别出运动点并找出定性路径。实验结果表明，该方法是可行的。

关键词: 定性空间推理, Voronoi图, 定性路径

Abstract: Qualitative path is a basic concept in qualitative spatial reasoning.A qualitative path representation and reasoning method based on Voronoi diagram is presented.The method uses the adjacent relationship to represent qualitative position and qualitative path.Specifically，the qualitative position is represented by the neighbors of the Voronoi diagram region the moving point lies in，and the qualitative path is represented by a series of qualitative positions the moving point passes through.Furthermore，a qualitative path reasoning algorithm is designed and implemented.With the initial Voronoi diagram and the number of edges of all Voronoi regions at different moments，the algorithm can update the dynamic Voronoi diagram，find the qualitative path，and identify the moving point.Experiment results illuminate that the method is promising.

Key words: qualitative spatial reasoning, Voronoi diagram, qualitative path

王晓东^1，2，廖士中¹. 基于Voronoi图的定性路径[J]. 计算机工程与应用, 2009, 45(21): 193-196.

WANG Xiao-dong ^1，2，LIAO Shi-zhong¹. Qualitative path based on Voronoi diagram[J]. Computer Engineering and Applications, 2009, 45(21): 193-196.

[1]	季长清1，2，肖鹏3，刘畅4，汪祖民2，西方2，邵寅博1，李泽宇2. 基于空间近邻查询的移动医疗呼叫算法[J]. 计算机工程与应用, 2019, 55(2): 206-212.
[2]	薛佳楣，张磊，玄子玉. Voronoi图划分实现位置数据发布隐私保护[J]. 计算机工程与应用, 2019, 55(10): 121-126.
[3]	朱杰1，鲁艺2，张辉明1. 突发威胁情况下的无人机航迹重规划[J]. 计算机工程与应用, 2018, 54(8): 255-259.
[4]	党小超1，2，马如仓1，郝占军1，2. 基于Voronoi的无线传感器网络栅栏覆盖策略[J]. 计算机工程与应用, 2018, 54(2): 91-96.
[5]	周屹1，杨泽雪1，2. 空间数据库中的线段k近邻查询研究[J]. 计算机工程与应用, 2015, 51(18): 131-134.
[6]	徐明，曹菡，唐多余. Hadoop下面元加权Voronoi图并行算法及应用[J]. 计算机工程与应用, 2015, 51(13): 59-62.
[7]	张丽平1，李松1，郝晓红2，郝忠孝1. 障碍物增减情况下的单纯型连续近邻链查询[J]. 计算机工程与应用, 2015, 51(11): 99-103.
[8]	余婧，曹菡，靳朋飞. Voronoi图k阶邻近并行矩阵迭代算法[J]. 计算机工程与应用, 2014, 50(6): 102-105.
[9]	滑斌杰，林立忠，柴忠良. 粗糙域Voronoi图离散生成算法研究[J]. 计算机工程与应用, 2013, 49(23): 191-194.
[10]	吴博1，2，文元桥1，2，肖长诗1，2. 一种内河海事无人艇路径规划算法设计与仿真[J]. 计算机工程与应用, 2013, 49(14): 241-246.
[11]	张仪彬1，吴刚1，彭雯秀2，陈彦如3. 不同交通网络速度的Voronoi图的结晶生成[J]. 计算机工程与应用, 2012, 48(36): 181-185.
[12]	张丽平，李松，郝忠孝. 球面上的最近邻查询方法研究[J]. 计算机工程与应用, 2011, 47(5): 126-129.
[13]	冯洪奎¹，鲍劲松^1，2，金烨^1，2. 广义Voronoi图求解多机器人运动规划[J]. 计算机工程与应用, 2010, 46(22): 1-3.
[14]	兰连意¹，张有会²，杨玉平³. 一般城市Voronoi图的结晶生成[J]. 计算机工程与应用, 2010, 46(10): 216-219.
[15]	康乐. 无人机三维航迹规划方法研究[J]. 计算机工程与应用, 2009, 45(33): 236-239.

基于Voronoi图的定性路径

Qualitative path based on Voronoi diagram

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics