标签: quadtree

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

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

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

我该如何实现上述功能？

提前致谢

请解释四叉树并提供简单的代码(最好用C语言)进行插入和搜索.

我理解四边形树如何在方形图像上工作(通过分割图像直到该部分是单个颜色,存储在叶节点中).

如果图像的一维长度超过另一维,会发生什么情况,最终可能会将2x1像素区域作为最小的子单元,这使得难以使用四叉树分割方法来存储单一颜色.你会如何解决这个问题？

我读过很多文章,但似乎都没有回答这个问题.或者也许我只是不理解.我正在尝试构建一个四叉树,以便它可以代表一个图像.叶节点用于保持像素,非叶节点将保持其子节点的平均值像素.

我的问题是:

叶子节点只保存像素是如何工作的？为什么其他节点没有像素？我们如何知道细分原始根节点以表示给定图像的次数？我们只是细分它的n时间,n高度和宽度(正方形)在哪里？

编辑:那么如何跟踪叶节点,所以我知道何时在该位置添加像素？现在我有一个帮助函数,为我划分区域,跟踪宽度和高度.

所有,

有几个使用Python实现四叉树的例子,但我的问题是,是否有人知道用纯python编写的类,如单个.py文件,我可以轻松地包含在我的项目中？这里列出了三个最受欢迎的软件包这些四树库中的任何一个都不错吗？但由于运行它们所需的所有依赖项,我没有运气使用它们.我真的想要一些重量轻,使用起来相对简单的东西.我想通过传递整个地球的边界来调用脚本并从那里开始工作.myMethod((-180,-90,180,90))

谢谢,亚当

在二维空间模拟中跟踪代理的一些好的数据结构是什么？

我已经看到一些对四叉树(我理解)和kd树(我不太了解)的引用.

我正在寻找一个代理人可以有效地说出的话,"我知道我的位置,我想知道哪些代理人在我附近(在我自己的某个半径范围内)."

非常感谢示例(伪代码很好).

我在Java工作.

我一直在研究这个:

https://github.com/mikechambers/ExamplesByMesh/blob/master/JavaScript/QuadTree/src/QuadTree.js

我相信我理解四棵树的一般想法,虽然我有两个关于它们如何工作的问题,以及上面的实现:

1. 你不得不每隔几毫秒重建整个树吗？在Javascript中这不是很慢吗？

2. 如果我有这样的东西:http://davzy.com/screenshots/skitched-20120318-180324.png,那么它很容易找到同一个四边形中的其他点,但我有一个矩形,击中3个不同的四边形,是有没有办法让它显示为所有3个四边形的孩子？

3. 在上面的例子中,它说这个Node.prototype._classConstructor = Node;,我只是好奇发生了什么.我认为原型是一种定义函数或变量以供将来在类中使用的方法,所以我不确定这行是做什么的.

我将编写一个KDTree的模板化实现,现在它只能作为四叉树或八叉树用于BarnesHut实现.

这里的关键点是设计,我想指定树被定义为模板参数的维数,然后简单地声明一些常用方法,它们会自动表现出正确的方式(我认为当时需要一些模板专业化).

我想专门化模板,以便有2 ^ 2(四叉树)或2 ^ 3(八叉树)节点.

有人有一些设计理念吗？我想避免继承,因为它限制我做动态内存分配而不是静态分配.

这里N可以是2或3

template<int N>
class NTree
{
public:
    NTree<N>( const std::vector<Mass *> &);
    ~NTree<N>()
    {
       for (int i=0; i<pow(2,N); i++)
          delete nodes[i];
    }
 private:
    void insert<N>( Mass *m );
    NTree *nodes[pow(2,N)]; // is it possible in a templatized way?
};

另一个问题是四叉树有4个节点但是2维,八叉树有8个节点,但是3维,即节点数是2^dimension.我可以通过模板元编程指定吗？我想保留4号和8号,这样循环展开器可以更快.

谢谢!

我正在实现一个体素八叉树raycaster,剩下的唯一的事情是重新排列数据以填充八叉树的叶级别,以便可以对数据进行平均以构建树的较低级别.

为了方便起见,我最初想的是2D(四叉树).我的数据如图中左侧所示,我现在能够像右边那样重新排列.例子是8x8.

但是,我意识到我需要按节点顺序排序数据,如下图所示:

换句话说,我想从一个数组对应的索引这样的索引:

[0  1  2  3  4  5  6  7  8  9 ... 63]

到具有此顺序数据的数组:

[0  1  4  5  16 17 20 21 2  3 ... 63]

对于8x8四叉树的例子.

我无法弄清楚该怎么做.我的主要问题是处理任意树大小.如果我事先知道大小,我可能会硬编码一组嵌套循环,但它显然不是一个伟大或优雅的解决方案.我在想可能有一种递归方式来实现它.

这就是我用图1中描述的方式对数据进行排序的快速和脏的草图.它基本上是通过跟踪原始数据中的四个位置,然后在新阵列填满时将它们向前移动.据我所知,这个工作正常,但不能扩展到我的需要:

 int w = 8; 
  int[] before = new int[w*w*w];
  int[] after = new int[w*w*w];
  for (int i=0; i<w*w*w; i++) {
    before[i] = i;
  }
  int toFill = 0;
  int front = 0;
  int back = w;
  int frontZ = w*w;
  int backZ = w*w …

最简单的方法是删除和插入对象，但可能还有更快的方法。（如果我想太多了，我应该用简单的方法来做，请告诉我）

这是关于我的四叉树的一些注释

• 正在移动的对象是 AABB，并且可能比最小的四叉树节点还要大。
• 创建子四叉树时，不会删除对象。这意味着根四叉树有一个指向四叉树内每个对象的指针。
• 这些对象作为指针存储在四叉树外部的向量中。

到目前为止，每次对象移动时，它都会调用根四叉树上名为 Update() 的函数。它包含其自身以及在移入参数之前的过去的边界框。但我不确定如何实现该功能。

将整个代码发布到我的 QuadTree 会使我的帖子变得很长，因此我创建了一个GitHub 存储库以便于阅读。

编辑：对于任何寻找答案的人来说，这似乎是通过删除和删除对象来更新对象，并且从他在评论中所做的测试来看，这是相当有效的。