ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2022, Vol. 59 ›› Issue (3): 706-719.doi: 10.7544/issn1000-1239.20200689

Previous Articles    

Convex Polygon Tree for Indexing Field-of-Views

Miao Xue1, Guo Xi1,2, Wang Zhaoshun1, Xie Yonghong1,2   

  1. 1(School of Computer & Communication Engineering, University of Science and Technology Beijing, Beijing 100083);2(Beijing Key Laboratory of Knowledge Engineering for Materials Science(University of Science and Technology Beijing), Beijing 100083)
  • Online:2022-03-07
  • Supported by: 
    This work was supported by the National Natural Science Foundation of China (61602031), the Fundamental Research Funds for the Central Universities (FRF-BD-19-012A, FRF-IDRY-19-023), and the National Key Research and Development Program of China (2017YFB0202303).

Abstract: Smart device, such as smart phones, can record their geographical positions and optical parameters into image files when capturing photos and videos. We can extract and use the information to restore the sector-shaped geographical area, which is known as the field-of-view (FOV). We store the images together with their FOVs in order to support the spatial queries on images. Typically, a user circles a region on the map as a query, and the computer returns the images which capture the region. In fact, the query is to find the FOVs that intersect with the query region. To make FOV queries fast, an index should be built. However, the existing indexes exploit the sector-shaped feature inadequately. We design a convex polygon tree to index pentagons which are the approximations of sectors. Each tree node is a k\+*-convex polygon, which encloses a set of polygons. The number of sides of the polygon must be no more than k, and the difference between the polygon and its elements should be minimized. We propose a submerging algorithm to compute such k\+*-convex polygons. To build a convex polygon tree, we insert FOVs iteratively. Each time we select a best leaf node for insertion. The selection criteria are to make the dead space and the increasing space as small as possible, and to make the overlap area between the old node and the FOV as large as possible. We also propose an FOV query algorithm based on the proposed convex polygon tree. The experimental results show that the convex polygon tree performs better than the existing indexes.

Key words: spatial query, field-of-view (FOV), convex polygon, tree structure, sector-shaped

CLC Number: