问题标签 [quadtree]

I've implemented a working QuadTree. It subdivides 2-d space in order to accomodate items, identified by their bounding box (x,y,width,height) on the smallest possible quad (up to a minimum area).

My code is based on this implementation (mine is in Lua instead of C#) : http://www.codeproject.com/KB/recipes/QuadTree.aspx

I've been able to successfully implement insertions and deletions. I've turn now my attention to the update() function, since my items' position and dimensions change over time.

My first implementation works, but it is quite naïve:

Yup, I basically remove and reinsert every item every time they move.

This works, but I'd like to optimize it a bit more; after all, most of the time, moving items still remain on the same quadTree node.

Is there any standard way to deal with this kind of update?

In case it helps, my code is here: https://github.com/kikito/middleclass-ai/blob/master/QuadTree.lua

I'm not looking for someone to implement it for me; pointers to an existing working implementation (even in other languages) would suffice.

我有一个问题：给定一个包含 0 或 1 的数组 nxm，我需要将 0 值分组为矩形。一开始，我用的是一个简单的四叉树，但是树的同一层的不同节点具有相同的值。我不完全确定 R-tree 是否适用于我的问题或其他数据结构，因为我只会在预计算步骤中使用此结构，仅此而已。

ps：我正在处理 2D 图像

我怎样才能在 PHP 中创建一个四叉树，甚至可能吗？

我想要一个“网格状”布局。

所以每个“节点”都有4个“出口”——北、南、东、西。

有没有人有一些四叉树的示例 PHP 代码，因为我找不到任何专门针对 PHP 的文档 :(

我会成为你最好的朋友......（可能还有一些代表）。

我正在编写一个基于整数的四叉树结构，它从节点开始构建，而不是向下构建。为此，我需要发现包含我所有元素的下一个最大节点。如果我定义了一个预先存在的节点，然后尝试在该节点的边界之外添加一个项目，它需要创建一个更大的节点来包含它们。我有（我认为很聪明的）代码用于在单点周围找到边界框：

[请注意，点 (0,0) 周围的框在位置 (0,0) 处是大小为 (1,1) 的框， 而不是在位置 (-.5,-.5)，因为它都是基于整数的]

这将始终（据我所知）返回一个适合作为节点的四叉树的框。例如，new Rectangle(0,0,2,2)可以接受，就像 一样new Rectangle(2,2,2,2)，但new Rectangle(1,1,2,2)不会。

我的问题是我不知道如何为一个矩形而不是一个点来完成这个。我能想到的唯一解决方案是循环通过数量增加的盒子，但我确信必须有一些我无法想到的 O(1) 解决方案。

例子：

执行：

我一直在使用 jQuery，并且在 javascript 中得到了四叉树的代码：

然而，这对我来说只是一个 3d 数组，我是不是很愚蠢？^.^

我有一个包含 20k+ 个经纬度城市的数据库，我需要针对这个数据集进行很多最近点查询（哪个城市最接近某个纬度、经度点）。

我想 R-Tree 或 QuadTree 将是一个完美的数据结构，但我无法找到一个有效的 ruby​​ 实现。你知道任何？

我目前正在开发一种 2D 射击类型的游戏，并且我正在使用四叉树进行碰撞检测。我编写了一个工作四叉树，可以正确地将我的演员推入它们在树中所属的节点/叶子中。但是，我有一些问题。

首先，我如何实际使用我的四叉树来选择一个对象应该针对哪些其他对象测试碰撞？我不确定这是如何完成的。

这就引出了第二个问题。假设我在节点中有一个对象不是另一个节点的邻居，但是该对象足够大以至于它跨越了几个节点，我如何检查实际的碰撞，因为我猜树可能认为它不是足够接近以与“远处”节点中的对象发生碰撞？不完全适合节点的对象是否应该保留在父节点中？

在我的游戏中，大多数物体大小不一，并且四处移动。

我已经阅读了大量关于四叉树的博客/文章，但大多数只是解释了如何构建一棵树，而这并不是我真正想要的。

欢迎任何帮助/信息。

请解释四叉树并提供用于插入和搜索的简单代码（最好是 C 语言）。

想象一个四叉树定义如下：

构造函数允许您创建格式不正确的四叉树。bad1应该只是 C 255 并且bad2也无效，因为它的右下四叉树（出于同样的原因，它应该是Q (C 0) (C 255) (C 244) (C 64).

到现在为止还挺好。检查其良好形式只是递归检查其内部四叉树的问题。基本情况是当所有内部四叉树都是叶子时，所有颜色不应该都是相等的。

问题：我可以避免为叶子和四叉树的所有可能组合键入所有匹配项吗？

如果我的问题很奇怪，请耐心等待，但这是我第二天的 Haskell 无缝学习！

如何只写flipv一次将其应用于 list 的每个元素[se, sq, nw, ne]，将结果（当然不是作为列表）提供给Q构造函数？

编辑：注意这实际上是错误的，因为指针应该是：NW NE SW SE。