Directional Computation and Reasoning with Contiguous Convex Polygons

There are many models for the computation of directional relationship between spatial objects,such as the famous cone-shaped model,project model and qualitative triangle model.But,because of the complexity of semantic of directional relationship and configuration of spatial objects,computational result of directional relationship between two random spatial objects is not always consistent with people's perception.Putting aside the difficulties of directional relationship computation between random spatial objects,the authors focus their researches on contiguous convex polygons,which is an important content in GIS of 2D space.The model of directional computation used in this paper is cone-shaped direction model. The convex polygon is a special kind of polygon.It can be replaced with its MBR in directional relationship computation.Depending on the analyses to the special characteristics of convex polygons and cone-shaped direction model,the authors provide two algorithms to computing direc-tional relationship between contiguous convex polygons.The first algorithm provides a method to determine whether a given directional relationship is true between two contiguous polygons.But there are at most three directional relationships will be true according to the first algorithm,and not all of them are consistent with people's perception.In order to obtain the best directional relationship,a flag variable is introduced to the second algorithm,which has been used to compute directional relationship between spatial objects in this paper. Directional relationship can be composed according to the table of directional composition provided in this paper.For example,let A,B,C be three spatial objects,and directional constraints A E B and B E C exist,then directional constraint A E,SE,NE C can be obtained by the directional composition table,which is very important to integrating directional reasoning system with topologic reasoning system.The authors provide an integration method with voronio diagram. Voronoi diagram is an important geometric construction,and polygons in voronoi diagram are bogus contiguous convex polygons.According to the algorithm for directional relationship computation,directional relationship between discrete spatial objects including area objects,line objects and point objects in the voronoi diagram can be obtained.And,because the contiguous topologic relationship between objects had been provided in the voronoi diagram,topologic relationship system and directional reasoning system can be integrated into a voronoi diagram,with which spatial reasoning system will be more powerful.For instances,depending on topologic constraints A EC B and B EC C,we can get no topologic information between A and C.If directional constraints A E B and B E C are also given,then topologic constraints A DC,EC,PO C can be obtained.This result is important,because it can be used to simplify the computational complexity of topologic reasoning,which is the most important spatial relationship in GIS.