Qualitative Motion Reasoning Based on Voronoi Diagram

Qualitative motion reasoning is an important approach to spatial commonsense reasoning. In this paper, we propose a qualitative motion reasoning method based on Voronoi diagrams. The method adopts the vicinity relationship to represent qualitative position and qualitative path. Specifically, the qualitative position is represented by the edges of the Voronoi diagram region the moving point falls in, and the qualitative path is represented by the series of qualitative positions the moving point passes through. Furthermore, a qualitative motion reasoning algorithm is designed and implemented. With the initial Voronoi diagram and the numbers of edges of all Voronoi regions at different moments, the algorithm can update the dynamic Voronoi diagram, work up the qualitative path, and identify the moving point. Experiment results illuminate that the method is promising.