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

A computing system comprising:

• a processor connected to at least a memory;
• a non-transitory computer storage medium connected to at least one data communication path to the processor and the memory;
• a hierarchical index on a corpus of spatial data, wherein the hierarchical index comprises a hierarchical arrangement of one or more nodes arranged in paths from root node entries to leaf node entries;
• node selection logic stored on the non-transitory computer storage medium and including instructions executable by the processor that cause the processor to:
• receive two points selected from the corpus of spatial data;
• access the hierarchical index to choose candidate nodes;
• determine a spatial relationship between the two points and the candidate nodes in the hierarchical index, wherein 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 some non-candidate nodes;
• and
• based, at least in part, on the determined spatial relationships, select a candidate node for constructing a geometric figure describing the corpus of spatial data;
• wherein the node selection logic is configured to choose candidate nodes by:
• at each level in the hierarchical index, starting with root node entries as 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 candidate nodes not selected as the path node are not chosen as candidate nodes in the next level;
• and
• when a leaf node entry is selected as a path node, selecting the leaf node entry for constructing the geometric figure.

A computer-implemented method performed by a computing device including at least a processor and a memory, the method comprising:

• receiving, by the processor, two points of data selected from a corpus of spatial data;
• accessing, by the processor, a hierarchical index on the corpus of spatial data to choose candidate nodes, where the hierarchical index comprises a hierarchical arrangement of one or more nodes arranged in paths from root node entries to leaf node entries;
• determining, by the processor, a spatial relationship between the two points and the candidate nodes in the hierarchical index, where the candidate nodes comprise a 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, selecting a candidate node for construction of a geometric figure describing the corpus of spatial data;
• wherein choosing candidate nodes comprises:
• at each level in the index, starting with root node entries as 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, wherein the child nodes of the candidate nodes not selected as the path node are not chosen as candidate nodes in the next level;
• and
• when a leaf node entry is selected as a path node, selecting the leaf node entry for the construction of the geometric figure.