Research On The GA-based Formal Solving And Computing Method For Dynamic Topological Relations

Topological relations are the important cornerstone of GIS expression and computation, as well as the key component of topological data model, spatial index, spatial analysis and data expression and visualization. Existing topological relations expression is realized largely based on the point set topological theory and set operations. In the process of expression and computation, topological relations between objects are usually expressed by such abstract objects as boundaries, interior and exterior, which will result in problems of complex computation and topological ambiguity in expression and computation of topological relations. In existing topological relations expression and computation, it is difficult to integrate directly original geometric objects and attributes into topological relation computing model, which leads to the poor dynamic adaptability of the topological relation computing model. The lack of formal expression and computation model for dynamic topological relations is one of the limitations of spatio-temporal GIS development.The lack of formal and algebraic expressing method for geometric objects and their motion is one of the reasons of the difficulty in dynamic topological relations expression and computation. Conventional GIS is mainly based on Euclidean geometry. In the framework of Euclidean geometry, it is difficult to directly express different geometric objects in an algebraic, formal and unified way and to describe the motion of geometric objects by unified operators. For example, the translation, rotation and scaling operations in Euclidean space are realized by matrixes computation. The lack of formal describing and algebraic expressing tools for objects and their motion results in difficulties of expressing and computing dynamic topological relations in the Euclidean space. Finding a new type of mathematic tool that can integrate geometry and algebra and express the motion of objects effectively is a workable solution to break through the bottleneck of present dynamic topological relation expression and computation.Aiming at the problems of formal expression and computation for dynamic topological relations, the geometric algebra (GA) theory, which preserves the geometric dimension construction relations and geometric measurement relations, is introduced in the paper. On the basic of the multi-level expressing model for geometric objects, the hierarchical expressing model for multidimensional objects is built by constructing the conformal geometric algebra (CGA) space. Thus the multi-vector expression for simple geometric objects and the unified expression for dimension constructing relation, geometric measurement relation and function structure description relation are realized. In CGA, the translation, scaling and rotation operations are expressed by unified Versor operator, which can also be applied in the multi-vector expression of geometries. The Versor based motion expression is dynamic and adaptive.Based on the Versor operator, the expression for simple geometric objects and their motion is constructed. The formal computation for topological relations of simple geometric objects is realized based on Meet and other operators. According to the hierarchical expressing model of objects, the RCC-8 based topological relation judging method for plane-plane objects is designed, and the formal expression of objects and unified computation of different dimensional objects are integrated effectively, which provides theoretical support for researching dynamic topological relation change. In this paper, the basic rules and constraints of topological relation change are built firstly by integrating the properties of rigid motion. And then the qualitative judging rules for topological relations change are constructed by expressing translation and rotation trajectories of motion and analyzing the topological permutation of trajectories and static objects referring to the minimum bounding rectangle judging method. Based on the translater and rotor operators, the solving of critical values and dividing of topological intervals are realized. Finally, the solving model for topological change series of moving objects is constructed.In the case studies, taking triangle as an example, the solving process of topological series of objects is analyzed. The result shows that the GA based plane object expression can support effectively the computation for dynamic topological relations, which verifies the practicability of our solving rules for topological series and intervals and provides references for the unified expression and analysis of other complex objects.