Multi-dimensional tree structure for the spatial sorting of geometric objects.

摘要

A computer program controlled method of processing geometric objects constructs a binary tree data structure 10 associated with bounding boxes of geometric objects. For each bound of a bounding box there is found a median (X) of all corresponding bounds, such as left sides associated with the bounding boxes. Next, all of the bounding boxes having a minimum bounding value less than X are placed on a left sub-tree 12 of the tree. All of the bounding boxes having a minimum bounding value greater than X are placed on a right sub-tree 14 of the tree. At the root are placed values that represent the maximum of that dimension's values in the left sub-tree and the minimum of that dimension's values in the right sub-tree. Boxes assigned to the left sub-tree and to the right sub-tree are similarly processed using a next bound such as the right sides. Searching the binary tree data structure in response to a query interval or box determines all of the boxes overlapping the Q box by comparing a lesser Q box bound with the left sub-tree's maximum value and by comparing a larger Q box bound with the right sub-tree's minimum value. The comparison generates information specifying if further search is carried out on the left sub-tree, the right sub-tree or on both sub-trees. Steps of the method are accomplished a plurality of times with successive bounds and recycling as required until the leaves of the tree are reached.