Convex Polygon Tree for Indexing Field-of-Views

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.