Index-based optimization of convex hull and minimum bounding circle queries

摘要

Systems, methods, and other embodiments associated with index-based optimization of geometric figured-related queries are described. In one embodiment, a method includes receiving two points selected from a corpus of spatial data. A hierarchical index on the data is accessed to choose candidate nodes. The index is a hierarchical arrangement of nodes arranged in paths from root node entries to leaf node entries such that each node is contained in all nodes in a path leading to the node. The method includes determining a spatial relationship between the two points and the candidate nodes in the index. The candidate nodes are a proper subset of the nodes in the index, such that the spatial relationship is not determined between the two points and some non-candidate nodes. A candidate node is selected based on the determined angles for processing related to construction of a geometric figure describing the spatial data.

主权项

1. A non-transitory computer storage medium storing instructions executable by a processor of a computer that when executed cause the computer to:
receive two points of data selected from a corpus of spatial data; access a hierarchical index on the corpus of spatial data to choose candidate nodes, wherein the hierarchical index comprises a hierarchical arrangement of one or more nodes arranged in paths from root node entries to leaf node entries; determine a spatial relationship between the two points and the candidate nodes in the hierarchical index, where the candidate nodes comprise a proper subset of the nodes in the hierarchical index, such that the spatial relationship is not determined between the two points and non-candidate nodes; and based, at least in part, on the determined spatial relationships, select a candidate node for construction of a geometric figure describing the corpus of spatial data; wherein the instructions further comprise instructions that when executed by the processor cause the computer to choose candidate nodes by: at each level in the hierarchical index, starting with the root node entries as the candidate nodes and until a leaf node entry is selected:
determining respective angles between a line segment having the two points as endpoints and respective candidate nodes in the level;selecting a candidate node as a path node, based at least in part, on the determined angles;choosing child nodes of the path node in a next level as candidate nodes, such that child nodes of the candidate nodes not selected as the path node are not chosen as candidate nodes in the next level; andwhen a leaf node entry is selected as a path node, selecting the leaf node entry for the construction of the geometric figure.