Databases
StackOverflow2013
Postsdbo
POWhat is an infinite scaleless quadtree called?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWhat is an infinite scaleless quadtree called?
    primarykey
    data
    text
    <p>2D spatial indexing question:</p> <p>What do you call a data structure that is essentially an infinite* quadtree whose nodes contain neither absolute coordinates nor absolute scales -- in which the coordinate system of each node has been normalized to the unit square (0,0)-(1,1), and in which the top-level node is not fixed absolutely?</p> <p>It's a quadtree, of course -- but what <em>type</em> of quadtree is it? (Is there a common name? I've seen dozens of types of quadtrees named and defined in the literature, but not this particular one.)</p> <p>To render a scene, you are given some starting node (not necessarily the root), its size in pixels, and its location on the screen. You then draw all objects within the node by scaling their coordinates using a current transformation matrix, which you push on the stack and halve as you go down the tree. The absolute coordinates of the nodes are thus available only though temporary work variables during rendering, and are not contained within the data structure itself.</p> <p>If an object within a node moves outside of the node (e.g., outside the unit square), you pass it to the parent for reassignment to another node. If an object becomes fragmented (for example, an asteroid hit by a bullet), the smaller portions are passed down to children nodes, who must scale the coordinates appropriately to maintain the unit-square normalization within each node.</p> <p>The key difference here from traditional quadtree implementations used in spatial indexing is that the coordinates of objects are always relative to the coordinate system of the node within which they are contained. This relativism applies not only to position but also to scale.</p> <p>* Infinite for the lack of absolute coordinates; even double-precision floating-point coordinates impart limits on position and size when used for absolute positioning.</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USTodd Lehman
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POWhat is an infinite scaleless quadtree called?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POWhat is an infinite scaleless quadtree called?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POWhat is an infinite scaleless quadtree called?
      1. USVicente Reig
      1. VTFavorite
    1. COFred? (just kidding).
      singulars
      1. POWhat is an infinite scaleless quadtree called?
      1. USbmargulies
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload