问题标签 [quadtree]

我最近了解了二进制空间分区树及其在 3d 图形和碰撞检测中的应用。我还简要阅读了有关四叉树和八叉树的材料。你什么时候会在 bsp 树上使用四叉树，反之亦然？它们可以互换吗？如果我有足够的信息来填写这样的表格，我会很满意：

什么是 A、B 和 C？

我正在尝试确定一种存储一组对象的快速方法，每个对象都有一个 x 和 y 坐标值，以便我可以快速检索某个矩形或圆形内的所有对象。对于小型对象集（约 100 个），简单地将它们存储在列表中并遍历它的简单方法相对较快。然而，对于更大的群体来说，这预计会很慢。我也尝试将它们存储在一对 TreeMaps 中，一个按 x 坐标排序，一个按 y 坐标排序，使用以下代码：

这也有效，并且对于较大的对象集更快，但仍然比我想要的慢。部分问题还在于这些对象四处移动，并且需要重新插入此存储中，这意味着将它们从树/列表中删除并重新添加到树/列表中。我不禁认为那里必须有更好的解决方案。我正在用 Java 实现它，如果它有什么不同的话，尽管我希望任何解决方案都将以有用的模式/算法的形式出现。

多年来，我一直在网上寻找四叉树/四叉树节点实现。有一些基本的东西，但没有什么能让我真正用它来玩游戏。

我的目的是将对象存储在游戏中以处理诸如碰撞检测之类的事情。我不能 100% 确定四叉树是最好的数据结构，但从我所读到的数据来看。我已经编写了一个红黑树，但我真的不知道性能是否足以适合我的游戏（这将是像 Ankh 这样的冒险第三人称游戏）。

我将如何用 C++ 编写一个基本但完整的四叉树类（或八叉树）？您将如何使用四叉树进行碰撞？

我想创建一个大型 GPS 坐标数据库，可以通过说“返回 [此坐标] 'n' 米内的所有坐标”来查询。

我想知道如何在Sqlserver2008中实现四叉树索引？

我想编写一个 .net 模块来调用使用四叉树的查询，以便我可以如此快速地检索对象。

如何实现上述功能？

提前致谢

我有以下类似四叉树的结构，其中每个单元格可以是内部节点或叶子。如果是叶子，它可以存储颜色。如果它是一个内部节点，它存储指向四个子节点（可以是叶节点或内部节点）的指针：

如果单元格是内部节点，则不需要存储颜色。如果它是一片叶子，那么它就不需要存储指向孩子的指针。因此颜色和孩子们应该共享相同的记忆（联合）

有一个函数 split() 将叶子转换为内部节点，并为当前单元格当前具有相同颜色的子节点（叶子）创建：

现在我正在调试函数 split()。我在线上设置了一个调试点

所以现在：调试器停在这一行，我观察成员值。我做了一个过程步骤，以便执行该行（指令光标现在位于下一行）。执行完这行代码之后，children[0] 的指针值还是一样的！相反，children[2] 的指针值发生了变化（连同浮点值 b）

有人可以向我解释这种行为吗？我究竟做错了什么？

谢谢！

我正在尝试实现用于碰撞检测的矩形四叉树（而不是点）。

由于某种原因，并不总是检测到重叠/交叉/碰撞。我怀疑这与插入的对撞机查找附近对撞机的方式有关（参见 Quadtree.as 的“碰撞 A”和“碰撞 B”部分）。谁能确定为什么会发生这种情况？

下面是我的四叉树代码，以及其他几个类，当它们一起编译时，当我说“四叉树”“不准确”时，它们会告诉你我的意思。您只需要查看 Quadtree.as，但是将它与其他类一起编译应该可以帮助您理解我的问题。

谢谢！

四叉树.as：

主要作为：

测试对象.as：

对撞机.as：

TestCollider.as:

二维空间索引问题：

您将什么称为本质上是无限*四叉树的数据结构，其节点既不包含绝对坐标也不包含绝对比例——其中每个节点的坐标系已归一化为单位平方 (0,0)-(1,1 ), 哪个顶级节点不是绝对固定的？

当然，它是一个四叉树——但它是什么类型的四叉树？（有一个通用名称吗？我在文献中看到了几十种命名和定义的四叉树，但不是这个特定的。）

为了渲染一个场景，你会得到一些起始节点（不一定是根节点）、它的像素大小以及它在屏幕上的位置。然后，您通过使用当前变换矩阵缩放其坐标来绘制节点内的所有对象，您将其压入堆栈并在沿着树向下时减半。因此，节点的绝对坐标仅在渲染期间通过临时工作变量可用，并且不包含在数据结构本身中。

如果一个节点内的对象移动到节点之外（例如，在单位正方形之外），您将它传递给父节点以重新分配给另一个节点。如果一个物体变得碎片化（例如，一颗被子弹击中的小行星），较小的部分将传递给子节点，子节点必须适当地缩放坐标以保持每个节点内的单位平方归一化。

这里与空间索引中使用的传统四叉树实现的主要区别在于对象的坐标始终相对于包含它们的节点的坐标系。这种相对主义不仅适用于位置，也适用于规模。

* Infinite 缺少绝对坐标；当用于绝对定位时，即使是双精度浮点坐标也会限制位置和大小。

我有一个充满大量圆圈（Ellipse2D）的面板。圆圈存储在二维数组（行和列）中。

我的目标是当我将鼠标拖到圆圈上时能够“绘制”圆圈。我最终会想要使用选择形状来改变选择形状中包含的所有圆圈的颜色。

我正在使用鼠标拖动侦听器，它不断扫描整个二维数组并检查当前点是否在圆圈内。像这样：

上面的代码有效，但它真的很慢（1000+ 圈），因为它正在检查每一个对象。

肯定有更好的办法。我读过一些关于四叉树的文章，但我不确定四叉树是否比我需要的马力更大。

谢谢

我根据以下一些评论进行了以下更改。Circles 现在是一个线性 ArrayList。draw 方法只是简单地填充圆圈。进行此更改将速度提高了两个数量级。现在效果好多了。虽然，我仍然可以以适中的速度扫过面板并错过几圈。所以我可能需要进一步优化。

我的某个项目似乎需要使用四叉树，这是我以前从未使用过的。从我所读到的内容来看，它们应该允许显着的性能增强，而不是对问题的蛮力尝试。这些python模块中的任何一个都好吗？

• 四叉树 0.1.2 <=否：无法在 Python 3.1 中执行
• QuadTree <= Yes：处理矩形时很简单
• quadtree.py <= No：不支持所需操作

编辑 1：有谁知道比 pygame wiki 中提供的更好的实现？

编辑 2：这里有一些其他人可能会发现对 Python 中的寻路技术有用的资源。

• 游戏实体导航
• 抓住小猫

我正在尝试使用四叉树（四叉树）来保存给定 BMP 中的信息。
我正在努力弄清楚如何在给定任何 BMP 的情况下构建树。

基本上结构是这样的，每片叶子代表一个像素。每个节点有 4 个指针，每个指针指向图像中剩余的四个象限之一。因此每个节点将当前图片分成4个部分。当你在叶子上时，你就在一个特定的像素上。

我不确定如何构建一棵树来映射某个图像。假设图像的尺寸是二次方，我该怎么办。我知道递归函数可能最优雅地做到这一点，但我正在努力弄清楚如何跟踪我将在图像中的位置。

这是在 C++ 中，目前我的 quadtree.h 文件包含一个 Node* 根，其中一个节点被定义为具有像素元素和 4 个指向其他节点的指针的结构。每个内部节点（非叶节点）应该保存它导致的所有 4 个 RGB 值的平均值。

我正在尝试制作一个算法，但我认为我可能需要在 .h 文件中包含一个或两个结构。有没有更好/更干净的方法来解决这个问题？