apratt@atari.UUCP (Allan Pratt) (04/13/88)
In college, a friend and I evolved a structure we called a sparse quad-tree. At first, we didn't know there was such a thing as a quad-tree, and when I learned of them the first thing I heard was that it was harder to delete a node than to to rebuild the tree without it. Our modified quad-tree has two types of nodes: those which are in the tree proper (information-carrying nodes) and those which exist only as decision points in the structure, differentiating between two or more information-carrying nodes. (We call these "pseudo-nodes.") The tree is bounded, because the notion "halfway from the origin to the edge" is used in the implementation, but I believe this restriction could be removed. The result is not the most efficient tree for a given map, but it is usually good, and easy to remove nodes from. The goal of the structure was to map moving objects in a plane, in real time (for a 2D game). This meant that adding and removing nodes had to be quick. In addition, this structure allows a query of the form, "List all nodes within a rectangle bounded by (X1,Y1),(X2,Y2)" to be answered quickly (by throwing away 1/4 of the map at each step, of course, but for a *region* of interest, not just a point). My question is this: is this useful? Does anybody care? Could this be the quick-removal quad-tree everybody has been waiting for? If this posting does no more than reveal my ignorance of the real quad-tree data structure, I'm sorry. If anyone can comment on the usefulness of this structure, or wants more information (including source code in C), I would love to get an informed opinion. ============================================ Opinions expressed above do not necessarily -- Allan Pratt, Atari Corp. reflect those of Atari Corp. or anyone else. ...ames!atari!apratt