Research Of Spatial Index Method Based On The Convex Polygon Approach

Generally speaking, the spatial targets dealt with by GIS have irregular shapes. If some of the spatial operations (eg. adjacent, contain, etc.) are based on their exact position and extension, the amount of calculation will be extremely large. Therefore, some approximate methods, taking the method of least constraint rectangle as an example, are often used to express the spatial targets with irregular shapes. The approximate expression method of spatial targets can simplify some spatial query course and avoid some unnecessary calculation so that the query efficiency can be effectively improved.Convex polygons are taken to approximate the spatial targets in this paper. A convex polygon is a non-null and finite convex set in Euclidean space Rd. For a subset in Rd, if a section of line connected by any two points included in this set is included entirely in the same set, then the set is called to be a convex set. The research showed that as to any spatial target, its corresponding convex polygon must be included in its corresponding minimum bounding rectangle. Therefore, convex polygons can define targets'positions much more exactly, and reduce overlap regions among different steric targets so that steric query can be realised with more efficiency.Firstly, the classical R-tree's index structures and its characteristics are analysed as well as its shortcomings.Secondly, further research on the best arithmetic method to calculate any polygon's convex hull is made. A new method to calculate plane point set's convex hull is proposed, and a new algorithm to calculate any two convex polygon'intersection and union is obtained. And their time complexity is given.In addition, the index structure tree based on convex polygon has been reseached: CP- tree. The CP-tree's index structure and search operation and generation are studied.Finally, the binary tree and the quadtree index structures based on convex polygon approach are presented. Moreover the corresponding query algorithm, node insertion and node deletion algorithms are given.The overlap regions among nodes in the spatial index method based on convex polygon approach are reduces, therefore steric query can be done more effectively.