Two-dimensional spatial index question:
What do you call a data structure, which is essentially infinite * quadtree, whose nodes contain neither absolute coordinates, nor absolute scales at which the coordinate system of each node was normalized to a unit square (0,0) - (1,1) which top level node is not fixed absolutely?
This is a quadrant, of course, but what type of quadri? (Is there a common name? I saw dozens of types of quadrants named and defined in the literature, but not in this particular one.)
To render the scene, you are provided with an initial node (not necessarily a root), its size in pixels and its location on the screen. Then you draw all the objects inside the node by scaling their coordinates using the current transformation matrix, which you click on the stack and reduce in half as you go down the tree. Thus, the absolute coordinates of the nodes are available only when using temporary working variables during rendering and are not contained in the data structure itself.
If an object inside a node moves outside the node (for example, outside the unit square), you pass it to the parent object for reassignment to another node. If the object becomes fragmented (for example, an asteroid that hits the bullet), the smaller parts are passed to the child nodes, which must scale the coordinates accordingly to maintain normalization of the unit square in each node.
The main difference here from the traditional quadtree implementations used in spatial indexing is that the coordinates of the objects always refer to the node coordinate system within which they are contained. This relativism applies not only to position, but also to scale.
* Infinitely for the absence of absolute coordinates; even double-precision floating-point coordinates result in position and size limitations when used for absolute positioning.
quadtree spatial-index 2d coordinates recursive-datastructures
Todd lehman
source share