一般来说,GIS所处理的空间目标具有不规则的形状,若基于它们的精确位置和扩展来实现某些空间操作(如相邻,包含等),其计算量会非常庞大。因此,一些近似的方法,如最小约束矩形法等,常常被用来表达具有不规则形状的空间目标。空间目标近似表达方法可以简化某些空间查询过程,避免一些不必要的计算,从而可以有效地提高查询效率。本文采用凸多边形(convex polygon)来近似表达空间目标,凸多边形是d维欧氏空间Rd中一个非空、有限的凸集。对Rd中的一个集合,如果这个集合中的任意2个点,连接这2个点的线段被完全包含在该集合中,则该集合被称作凸集。研究表明,对于任意一个空间目标而言,这个目标对应的凸多边形必然包含在该目标对应的最小约束矩形中。因此,凸多边形能够更精确地定义空间目标的位置,减少不同空间目标之间的重叠区域,从而可以更有效地实现空间查询。首先,本文分析了经典的R-树查询方法,以及R*-树,R+-树的索引结构及其各自的特点和缺点。其次,进一步的研究求任意多边形的的凸包的最优算法,提出了求平面点集凸壳的一种新算法,求任意两个凸多边形交与并的凸壳新算法,分析其时间复杂度。此外,研究了基于凸多边形的索引结构树:CP-树,研究CP-树的索引结构,以及搜索运算和生成运算。最后,建立一种新的基于凸多边形逼近的二叉树,四叉树结构,提出其查询,插入以及删除算法。基于凸多边形逼近的空间索引方法,减少了不同空间目标之间的重叠区域,从而可以更有效地实现空间查询。