问题标签 [quadtree]

我正在考虑使用 HashMap 作为 QuadTree 的支持结构。我相信我可以使用 Morton 测序来唯一识别我感兴趣的区域的每个方格。我知道我的 QuadTree 的高度最多为 16。根据我的计算，这将导致一个 65,536 x 65,536 的矩阵，它最多应该给我 4,294,967,296 个单元格。有谁知道 HashMap 的元素是否太多？我总是可以使用 Tree 编写 QuadTree，但我认为使用 HashMap 可以获得更好的性能。

高度 1 == (2x2) == 4 的莫顿序列

高度 2 == (4x4) == 16 的莫顿序列

高度 3 == (8x8) == 64 的莫顿序列

最大高度为 3 的树的 Morton 测序示例。

这是我所知道的：

• 我将在已知的矩形区域上获取纬度/经度的数据。
• 数据不会完全覆盖整个区域，并且可能会在该区域的某个地方合并成块。（更糟糕的情况是所有 4,294,967,296 个单元格中的数据）
• 数据的分辨率最终将该区域分解为 65k x 65k 的矩形。
• 我也知道我可能会收到 10 到 1 个查询来插入/更新数据。

我有一个 QuadTree，可以通过在节点中放置对象来细分它。我还有一个用 OpenGL 制作的四边形行星。问题是我不知道如何将它们放在一起。QuadTree 如何存储有关地球的信息？我是否将顶点存储在叶子四叉树节点中？如果是这样，我如何在不破坏纹理和法线的情况下将顶点数据分成 4 组。如果是这种情况，我是否使用索引？

所以简而言之，我的问题是：

我如何将我的顶点数据存储在四叉树中，以便我可以分割地球上的地形，以便地球在更近的范围内变得更详细。我假设这是通过使用相机作为分割节点的对象来完成的。

我已经阅读了很多文章，其中大多数都没有涵盖这一点。Quadtree 是我的应用程序中最重要的东西之一，因为它可以让我同时渲染许多行星，同时仍然能够在陆地上获得良好的清晰度。我的星球的一张漂亮照片，它是高清太阳：

也可以在此处找到该星球的视频。

我已经设法在一个平面上实现了一个简单的四叉树，但是我一直有很多洞，因为我认为我的位置是错误的。这是这里的最后一篇文章 - http://www.gamedev.net/topic/637956-opengl-procedural-planet-generation-quadtrees-and-geomipmapping/你也可以在那里获得 src。任何想法如何解决它？

我正在寻找一种支持查找“n”个区域中的哪个包含点“p”的数据结构。我正在查看 Quadtree 和 R-tree，但我认为它们并不完全符合我的要求。

本质上，我希望能够向这棵树添加一些 3 维矩形区域，然后能够针对这棵树测试一个 3 维点并返回哪个区域最严格地约束该点。没有区域会有重叠的边界。

我目前使用的简单算法是针对每个矩形区域的每个维度简单地测试点“p”。

这在 O(n) 时间内运行，其中 n 是区域数。我希望搜索将 O(log n) 作为四叉树用于查找 2d 点的点。

我最近遇到了一种称为段树的新数据结构，然后读到它也可以扩展到二维，但我找不到一个好的来源来阅读它的实现细节和其他内容。我想从在编程竞赛中使用它的角度来了解它，而不是在图形领域。使用它可以解决的一些问题也很有用。有人可以指点我一个很好的来源来阅读它吗？谢谢

我正在做一个模拟，我需要能够处理更新每个循环的数千个潜在的数百万个对象。所有对象都需要具有称为（AI）的逻辑功能。但是根据对象的位置决定了逻辑的详细程度。例如：

[使用 100 个对象保持简单]

• 所有对象都有一个位置 (x,y)
• 20对象距离“兴趣点”位置 500 点。
• 50对象距离对象 500 点20（距离 1000 点）。
• 30对象距离兴趣点 100 点以内。

现在说这是一个详细的城市模拟，对象是虚拟公民。下午 6 点，每个人都该下班回家睡觉了。

所以我们遍历所有公民，但我希望他们做不同的事情。

• 最远的物体 (50) 下班回家睡觉直到早上。
• 较近的物体 (20) 下班回家，吃点东西，然后睡到早上。
• 最近的物体 (30) 下班回家，吃点东西，刷牙，然后睡到早上。

正如您所看到的，它们越接近兴趣点，逻辑就越详细。

我正在尝试找出迭代所有对象的最佳和最高效的方法是什么。用满手的物体，这将是相对容易的，但由于这需要有效地处理至少 500,000 个物体，我需要一些建议。

此外，我不确定是否应该在每个循环中遍历所有对象，或者最好在每个循环中遍历最近的对象，但每 10 个循环仅遍历更远的对象？

由于需要对象在靠近它们的其他对象之间进行交互的额外要求，我一直在想最好的方法可能是将它们组织成四叉树，但我不确定。似乎四叉树更适合静态内容，但我正在处理的对象，如前所述，有一个位置，需要移动到其他位置。我是否走在正确的思考轨道上？或者，还有更好的方法？

如果有人认为它相关，我也在使用 c++ 工作。

任何建议将不胜感激。

笔记：

1. 兴趣点定期变化，将其视为相机视图。
2. 对象是动态创建和销毁的

先说一下思路：

我想检查用户到指定路线的距离。路线由多个位置点组成（图中为点 a、b、c、d）。两个相邻点描述一个向量（图中蓝线ab、bc、cd）

现在到应用程序（特别是android，但这不是这个问题的一部分）用户的位置在他沿着路线旅行时被跟踪。对于我要检查的每个新位置，用户是否仍在路线上（或距离 X 内）。

我沿着路线画了 3 个可能的位置：

• 位置1没问题。我将垂线从点 1 下降到矢量 ab。这给了我这个向量上的一个位置点，我可以计算两点之间的距离（使用 android: Location.distanceTo()）

• 位置 2 当我处理向量时，它们没有开始也没有结束。黑线是向量ab的投影。计算最近距离将使我与向量 ab 的距离很近，但与向量 bc 的距离很远。事实上，我需要计算到 bc 的距离，因为这就是路线的前进方式。但是我怎么知道在我的算法中我需要选择哪个向量来计算距离？

• 位置 3 使我可以使用向量 ab 或 bc 进行计算。两者几乎同样接近。如何知道选择哪一个？

四舍五入：

我有一个带有位置点的数组：

我的应用程序正在跟踪用户的位置。我现在想将新位置与数组中的这条轨道进行比较。

有人知道解决问题的算法，还是有人可以帮助我解决算法？（伪代码就足够了）

//编辑：我刚读到四叉树算法。除了Soonts的实施之外，这也许是一种选择。

很抱歉在这个问题中没有使用任何术语，但基本上我正在研究创建一个使用二进制索引的 QuadTree，如下所示：

正如您在上面的两个插图中看到的那样，如果每个单元格都有一个二进制 ID（例如：1010、1011），那么每个奇数二进制索引控制 X 偏移量，每个偶数二进制索引控制 Y 偏移量。

例如，在2 级网格（16 个单元）的情况下，1010（单元#10）可以说在它的第 4和第 2索引处有 1，因此它们将执行两个 Y 偏移。第一个“1###”（在最左侧）表示一个单元格高度的偏移量，然后第二个“##1#”将另外偏移单元格高度的两倍。

如：

同样可以应用于 X 轴，只是它使用奇数代替（例如：#1#1）。

现在，当我初始化我的 QuadTree 时，我开始计算如果使用所有单元格和所有深度，它可能包含的最大节点。我用每个深度的 4 次方的总和计算了这个：

然后，我创建另一个循环（从0 迭代到 _totalNodes），它实例化节点并将其存储在一个长数组中。它将当前迭代整数传递给 Node构造函数，并将其存储为索引。

到目前为止，我已经能够通过确定它的索引的最高有效位来确定节点将存储在哪个深度（又名：级别）中：

但是现在，我一直在试图弄清楚如何将索引从二进制形式转换为实际的 Cell X 和 Y 位置。就像我上面说的，找到每个单元格的尺寸。这只是对整个索引进行一些逻辑操作的问题（或者“位代码”是我在代码中引用的名称）

如果您知道一个使用逻辑运算（二进制级别）将二进制索引值转换为 X 和 Y 位置的好示例，您能否在此处发布链接或解释？

谢谢！

这是我从中得到这个想法的参考（注意：不同的编程语言）：

L. Spiro 引擎 - http://lspiroengine.com/?p=530

虽然我不熟悉那篇文章中使用的语言，所以我不能真正遵循它并将其轻松转换为 ActionScript 3.0。

我正在尝试在 Heroku 上设计一个 Web 服务，该服务以固定的时间间隔从许多人那里收集 GPS 位置。除了在任何特定时刻跟踪每个人的位置之外，我还希望能够查询谁在某个范围/半径内。

我知道如何使用四叉树来做到这一点，但我只是想确保没有已经这样做的附加服务，这样我就不会重新发明轮子。

任何帮助，将不胜感激！

谢谢！

我当前的实体引擎使用四叉树循环遍历所有实体（一个数组），然后使用每个实体都有的 libgdx Rectangle 实例检查冲突。

我的 QuadTree（它很长，所以我认为 id 只是链接到它）

在 Entity 类中，我有一个 placeFree 方法：

screen.placeFree 方法：

要检查先发制人的碰撞，我这样做：

基本上 placeFree() 实际上将当前命中框的副本放置在一个新位置，并检查那里是否发生任何碰撞。我想要做的是在向左移动之前检查我的玩家左侧的区域是否没有碰撞。

我当前的问题是，如果我添加 3 个“Solid”（实体的子类）实例，它仅适用于添加的第一个实体。为什么会发生这种情况，我该如何解决？

这就是我的意思（红色框是正常的hitbox，绿色是先发制人的hitbox）。

在这张图片中，您可以看到先发制人的 hitBox 刚刚通过：

但是在这个中它不能，因为我首先添加了那个块（顺便说一句，我使用 placeFree(x,y-100) 更清楚地显示绿色框）：

我正在研究四叉树的复制构造函数。这是我到目前为止所拥有的：

我不确定我哪里出错了，但我收到内存泄漏，Valgrind 指出我有未初始化的值。请帮忙？

附加的是我的 buildTree 函数 - 我实际创建树的地方。我可能在这里做错了什么？