Qualitative Path Reasoning Based on Voronoi Diagram
WANG Xiao-Dong1,2,LIAO Shi-Zhong1
1.School of Computer Science and Technology,Tianjin University,Tianjin 300072 2.Department of Physics Electronic Engineering,Mudanjiang Normal University,Mudanjiang 157012
Abstract：Qualitative motion reasoning is important in qualitative spatial reasoning research. Based on Voronoi diagram and its dynamic changes,a qualitative representation and reasoning method for motion paths is proposed. Firstly,the spatial relations among generators of Voronoi diagram are described by adjacent relations,the spatial positions and their conceptual neighborhood are defined,and the motion path is qualitatively represented by the sequence of conceptual-neighboring qualitative positions. Then,a qualitative path reasoning algorithm with an observer perspective is designed and implemented by the changes in edges of the dynamic Voronoi diagram and the proposed heuristic algorithm of shortest path between two qualitative positions. Finally,the experimental result and analysis demonstrate the validity of the proposed methods.
[1] Muller P. A Qualitative Theory of Motion Based on Spatio-Temporal Primitives // Proc of the 6th International Conference on Principles of Knowledge Representation and Reasoning. Trento,Italy,1998: 131-143 [2] Wolter F,Zakharyaschev M. Spatio-Temporal Representation and Reasoning Based on RCC-8 // Proc of the 7th International Conference on Principles of Knowledge Representation and Reasoning. Breckenridge,USA,2000: 3-14 [3] Ouyang Jihong,Ouyang Dantong,Liu Dayou. Region Movement Model Based on Fuzzy Sets and RCC Theory. Journal of Jilin University: Engineering and Technology Edition,2007,37(3): 591-594 (in Chinese) (欧阳继红,欧阳丹彤,刘大有.基于模糊集及RCC理论的区域移动模型.吉林大学学报:工学版,2007,37(3): 591-594) [4] Hernandez D,Jungert E. Qualitative Motion of Point-Like Objects. Journal of Visual Languages Computing,1999,10(3): 269-289 [5] Musto A,Stein K,Eisenkolb A,et al. From Motion Observation to Qualitative Motion Representation // Proc of the Spatial Cognition II. Berlin: Springer-Verlag,2000: 115-126 [6] Van de Weghe N,Kuijpers B,Bogaert P,et al. A Qualitative Trajectory Calculus and the Composition of Its Relations // Proc of the 1st International Conference on GeoSpatial Semantics. Berlin: Springer-Verlag,2005: 60-76 [7] Bogaert P,Van de Weghe N,Cohn A G,et al. The Qualitative Trajectory Calculus on Networks // Proc of the International Conference on Spatial Cognition V-Reasoning,Action,Interaction. Bremen,Germany,2007: 20-38 [8] Delafontaine M,Cohn A G,Van de Weghe N. Implementing a Qualitative Calculus to Analyse Moving Point Objects. Expert Systems with Applications,2011,38(5): 5187-5196 [9] Gold C M. Problems with Handling Spatial Data-The Voronoi Approach. CISM Journal ACSGC,1991,45(1): 65-80 [10] Edwards G. The Voronoi Model and Cultural Space: Applications to the Social Sciences and Humanities // Proc of the LNCS 716: Spatial Information Theory: A Theoretical Basis for GIS. Elba Island,Italy,1993: 202-214 [11] Liao Shizhong,Shi Chunyi. An Unified Qualitative Representation Mechanism for Planar Shape and Arrangement. Journal of Computer Research and Development,1998,35(9): 14-19 (in Chinese) (廖士中,石纯一.平面形状和布置的一种统一的定性表示方法.计算机研究与发展,1998,35(9): 14-19) [12] Yan Haowen,Guo Renzhong. Theorization of Directional Relationship Description Based on Voronoi Diagram. Journal of Wuhan University: Information Science Edition,2002,27(3): 306-310 (in Chinese) (闫浩文,郭仁忠.用Voronoi图描述空间方向关系的理论依据.武汉大学学报:信息科学版,2002,27(3): 306-310) [13] Chen Jun,Zhao Renliang,Qiao Chaofei. Voronoi Diagram-Based GIS Spatial Analysis. Journal of Wuhan University: Information Science Edition,2003,28(S1): 33-37 (in Chinese) (陈 军,赵仁亮,乔朝飞.基于Voronoi图的GIS空间分析研究.武汉大学学报: 信息科学版,2003,28(S1): 33-37) [14] Yang Yongqing,Feng Jun,Wang Zhijian. Reasoning and Calculation of Spatial Direction Relationship between Complex Objects Based on Voronoi Diagram. Journal of Hohai University: Natural Sciences,2008,36(3): 415-417 (in Chinese) (杨永清,冯 钧,王志坚.基于Voronoi图的复杂对象空间方位关系的推理计算.河海大学学报:自然科学版,2008,36(3): 415-417) [15] Wang Xiao,Liu Yu,Gao Zhenji,et al. Landmark-Based Qualitative Reference System // Proc of the IEEE International Geoscience and Remote Sensing Symposium. Seoul,Korea,2005: 932-935 [16] Gong Yongxi,Liu Yu,Wu Lun,et al. Locality Description Based on Multiplicatively Weighted Voronoi Diagram and Landmarks. Geography and Geo-Information Science,2010,26(4): 21-26 (in Chinese) (龚咏喜,刘 瑜,邬 伦,等.基于带权Voronoi图与地标的空间位置描述.地理与地理信息科学,2010,26(4): 21-26) [17] Aurenhammer F,Klein R. Voronoi Diagrams // Sack J R,Urrutia J,eds. Handbook of Computational Geometry. Amsterdam,Holland: Elsevier,2000: 201-290 [18] Shi Chunyi,Liao Shizhong. Qualitative Reasoning Methods. Beijing,China: Tsinghua University Press,2002 (in Chinese)
2013, Vol. 26 
