无限无标度四叉树叫什么？
2D 空间索引问题：
本质上是一个无限*四叉树的数据结构，其节点既不包含绝对坐标，也不包含绝对尺度——其中每个节点的坐标系已标准化为单位平方 (0,0) -(1,1)，其中顶层节点不是绝对固定的？
当然，它是一个四叉树——但是它是什么类型的四叉树呢？ （有通用名称吗？我在文献中见过几十种类型的四叉树命名和定义，但不是这个特定的。）
为了渲染场景，你会得到一些起始节点（不一定是根），它的大小以像素为单位，及其在屏幕上的位置。然后，您可以使用当前变换矩阵缩放节点内的所有对象的坐标，将其推入堆栈并在沿着树向下移动时减半。因此，节点的绝对坐标仅可通过渲染期间的临时工作变量获得，并且不包含在数据结构本身内。
如果节点内的对象移出节点（例如，单位方块之外），则将其传递给父节点以重新分配给另一个节点。如果一个对象变得碎片化（例如，一颗小行星被子弹击中），较小的部分将被传递到子节点，子节点必须适当缩放坐标以维持每个节点内的单位平方归一化。
这里与空间索引中使用的传统四叉树实现的主要区别在于，对象的坐标始终相对于包含它们的节点的坐标系。这种相对主义不仅适用于位置，也适用于尺度。
* 由于缺乏绝对坐标而无限大；当用于绝对定位时，即使是双精度浮点坐标也会对位置和大小产生限制。
2D spatial indexing question:
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?
It's a quadtree, of course -- but what type 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.)
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.
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.
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.
* Infinite for the lack of absolute coordinates; even double-precision floating-point coordinates impart limits on position and size when used for absolute positioning.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
是的，这是一个呃..“包裹网格嵌套四叉树”？如果您用于网格坐标，则只能使用最高和最低的 int32 值。
Yeah it's a uh.. "wrapped-grid-nested quadtree"? You're only limited to the highest and lowest int32 value if that's what you're using for grid-coords.
顾名思义，你有一个四叉树网格。在每个整数坐标方格之间，您似乎在网格的该部分上构建了一个四叉树。
You have a grid of quadtrees from what it sounds like. Between each square of integer coordinates you seem to be constructing a quadtree on that part of the grid.