问题标签 [quadtree]

我想在 QuadTree 上进行导航/A*。

我已经实现了四叉树，或者至少我认为是四叉树。同时，我看到了一些内部节点也包含元素的地方。使用我的内部节点仅链接到它们的子节点，并且元素存储在叶节点的集合中。虽然每个节点都链接到其父节点，但（当前）没有链接到邻居，也没有兄弟节点或其他分支的节点。元素是区域而不仅仅是点。

我在网格上也看过 A* 很长一段时间，甚至在 QuadTree 上也有过演示，但没有详细说明。

我想主要问题是我如何快速到达我的邻居？

我不确定我是否应该让叶子相互连接。但这将是一项艰巨的工作，因为随着元素更新它们的位置，树是动态的。它还需要一些用于链接的动态集合之王，因为根据节点大小，一个大叶子可以在一个方向（例如东）有很多小叶子。更新它的努力似乎相当巨大，即使目前不知道我会怎么做。

谢谢你

我已经在 J​​avascript 中实现了一个二维kd 树（在 GitHub 上查看），并且我将它与D3一起用于最近邻搜索。

我了解到 D3 中有一个四叉树实现，但也发现 API 文档稀少，谷歌搜索没有成果。如果可能的话，我宁愿使用一个广为人知的图书馆，也不愿使用我自己重新发明的轮子。

如何使用 D3 的四叉树执行最近邻搜索？通过最近的邻居，我的意思是：

• 用二维点填充四叉树
• 搜索最接近四叉树中不一定存在的新点的四叉树包含点

我使用四叉树作为数据结构来存储点。因为我需要快速找到某个区域的所有点。

但是我需要移动这些点。在我的 C++ 程序中。由于移动发生在所有点上，但对于不同方向的每个点，我目前破坏了我的四叉树并重建它，这会导致大量分配和删除。

因此，我的问题是这种问题是否有更好的数据结构？

我有以下要求：我有 n 点。

我需要快速获取给定特定区域的所有点。对于我的四叉树，这大约是 O(log(n))。然而，这个操作被称为 m 次，其中 m > n，因此它大约为 O(m*log(n))。

我需要移动所有点。目前，这大约运行 O(n*logn)。此方法只对所有 m 调用一次。

但是，我目前发现此解决方案不能令人满意。因为我总是破坏我的四叉树并重建它，这会由于分配而导致开销。

更新： 积分分布不均匀。有密集的位置，也有点少的位置。

这是一些简化的代码。这里存储的指针代码：

这是四叉树的界面

这里是 QuadTreeNode 的接口与 get 和 put 方法实现，以显示如何存储点。

我想在 C++ 中创建一个快速四叉树，但发现当我在函数中更改结构的值时，值会恢复。同样在递归函数中，我不会创建一些全局数据。我该怎么做呢？

四叉树和kd树的主要区别是什么？我知道他们在多个维度上分割点，但我不明白为什么我们会使用一个而不是另一个。我需要一个允许我计算给定区域中有多少点（2D 点）的结构。基本上，我正在尝试检测点簇。

我无法将四叉树中的一组子节点递归折叠到它们的父节点中。添加、删除和细分工作正常，但是当从树中删除足够多的元素时，树不会将未满的节点折叠到父节点中然后删除它们。

谢谢。

[编辑]

已解决的问题是最终代码。多谢你们。

我希望能够检查四叉树中包含在与区域相交的节点中的所有元素。但问题是，如果我调用Query一个只有高度为 2 的部分，则会发生堆栈溢出。

执行以下操作的更有效（且错误更少）的方法是什么？

我正在尝试使用 d3.js 绘制一个图，以实现节点之间的冲突。我尝试了以下 codigo.Pero 不起作用。

如果我删除碰撞检测绘制但重叠节点......

如果我删除碰撞检测工作但重叠节点。我需要帮助 ：（

我已经阅读了有关四叉树或 kd-tree 拆分和 mandelbrot 集的信息，但是当第一次拆分之前的矩形和框架位于 mandelbrot 集中或具有相同的迭代深度并且算法从平铺返回时怎么办？当矩形太大时，如何强制跳过填充矩形？

我试图在世界坐标中找到鼠标位置，但找不到正确的代码。目前我用它来确定光线：

这给了我射线的原点和方向。

但...

我使用带有高度图的自定义网格（不是来自 directX 的网格），分成四叉树，我不知道我的逻辑是否正确，我尝试使用截头锥来确定四叉树中的哪些节点是可见的，所以检查三角形的交点只在那些节点上，这里是这个代码：

注意* m_mousepos 是一个向量。

请问这段代码对吗？如果是，那么我的问题一定与四叉树有关。

谢谢！