四叉树性能：正方形与矩形？
对于我正在编写的游戏，我在非正方形地图上使用四叉树。四叉树用于查找给定最大半径（圆）内的相邻单位的冲突检测、要攻击的敌人、最近的基地等。
我想知道的是，如果将四边形树由矩形而不是正方形制成，是否存在性能问题？矩形地图不是将正方形地图划分为正方形，而是在四边形树中划分为大小相等的矩形。
矩形地图上的方形四叉树：将创建一个四叉树，填充整个地图，但左侧或底部有空白/未使用区域，具体取决于地图的方向（水平方向与垂直方向）。这将需要更多的方块来填充（？）在搜索过程中是否也会对性能产生影响？
与矩形地图匹配的矩形四边树：四边形树将完美地填充地图。但是，这样做会影响性能吗？鉴于我们搜索使用的半径将适合正方形而不是矩形，这可能会导致搜索速度变慢？此外，两个宽度
问：将四叉树转换为方形形式是否更好？我认为使用矩形中队树可能是可以的，但我不确定？
共有1个答案
我确信两种选择都可以。从你的例子来看，你的数据集似乎很小，只有几十个条目，也许有100个？
需要考虑的一些事情：
-
< li >正如您提到的:矩形需要x和y的单独“长度”。这种影响可能很小，但每增加一位信息都会降低结构的速度，因为需要将更多的数据移动到CPU并通过CPU。 < li >如果您在四叉树中存储(通常)直接位于矩形边框上的对象，您需要注意正确实现四叉树: < ul > < li >插入:在四个四边形的角上插入一个项目，它将插入哪个四边形？ < li >查询/查找:与插入相反，任何在边界上结束的搜索都可能(不必要地)搜索所有邻接的qaudrants，这可能是昂贵的。
总而言之，这个问题可能不太涉及正方形/矩形四边形，但是当数据通常位于象限边界上时，应该小心。
-
我目前正在为特别大的图像文件（有时在千兆像素）设计和开发定制的图像查看器。幸运的是，这些在分阶段分辨率层中以256x256瓦片的形式提供，然后在需要时传递给OpenGL。 瓷砖本身通过一个四叉树进行管理，这似乎是“几乎两幅图像的幂”的一个强有力的解决方案。然而，如果图像的宽高比非常大（例如，1千兆像素x 50000），模型就会因大量的空分片而变得不稳定。一次只能展示有限数量的瓷砖。 我正在使用Ja
-
四叉树是一个二维空间递归细分。它使用了平分划分实现，将每一个块平分成了四个同等大小的方块。每个点存在于一个唯一的节点中；如果同一位置包含多个点，那么这多个点中的其中一些点将存储于内部节点，而非叶子结点。四叉树可用于加速各种空间操作，例如计算正多边形的体积的Barnes-Hut近似算法或者冲突检验。 d3.geom.quadtree() 创建一个新的四叉树工厂使用默认的x访问器，y访问器及范围。返回
-
我已经实现了一个四叉树来对图形中的点进行排序。每当一个点落在已经包含一个点的象限内时，该象限就会再次细分，以允许每个点落入其自己的象限。每个节点都具有以下属性： 假设我想遍历存储在这棵树中的每个节点，并计算落在给定矩形边界内的点数，我将如何递归检查树中的每个节点（假设我已经有方法检查它们是否落在某个区域）？
-
矩形树图最先由Ben Shneiderman在1991年提出; 矩形树图会递归的对一块矩形区域进行切分, 以达到层级展示的效果. 正如分区布局中, 每个节点的大小都是显而易见的. 正方化的矩形树图使用近正方的矩形, 因此, 相比于传统的切块或切片图, 具有更好的可读性和节点大小易读性. 还有其他一些关于矩形树图的算法, 比如: Voronoi 和 jigsaw, 但是并不常用. 和其他 D3 类一
-
我读过一些关于将Square作为Rectangle类的继承类是不好的做法的文章，说这违反了LSP（Liskov替换原则）。我还是不明白，我用Ruby编写了一个示例代码： 谁能告诉我它出了什么问题？
-
本文向大家介绍数据结构中的四叉树，包括了数据结构中的四叉树的使用技巧和注意事项，需要的朋友参考一下 四叉树是被实现以有效地存储二维空间上的点的数据的树。在此树中，每个节点最多具有四个子节点。 我们可以从二维区域构建四叉树，实现以下步骤 当前的二维空间分为四个框。 如果盒子中包含一个或多个点，则构建一个子对象，在其中存储盒子的二维空间。 如果一个盒子不包含任何点，则不要为其建立子对象。 对每个孩子执