标签: quadtree

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

public static Rectangle BoundingRectangle(Point p, int magnitude)
{
    Rectangle bounds = new Rectangle()
    {
        X = (p.X & ~((1 << magnitude) - 1)),
        Y = (p.Y & ~((1 << magnitude) - 1)),
        Width = (1 << magnitude),
        Height = (1 << magnitude)
    };
    return bounds;
}

[注意,点(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)解决方案.

例子:

Rectangle(X,Y,1,1) -> Rectangle(X,Y,1,1)
Rectangle(0,0,2,2) -> Rectangle(0,0,2,2)
Rectangle(1,1,2,2) -> Rectangle(0,0,4,4)
Rectangle(1,1,3,3) -> Rectangle(0,0,4,4)
Rectangle(0,5,2,2) -> …

Quadtrees用作游戏和其他地方的优化,用于实体的空间组织http://en.wikipedia.org/wiki/Quadtree.

有没有用于HTML5 Canvas的四叉树的例子？

我正在尝试使用和理解D3可视化库(http://mbostock.github.com/d3/),我正在查看他们的力导向代码,看起来他们正在使用四叉树来计算粒子上的力.代码是

      var k = kc * quad.count * dn * dn;
      node.px -= dx * k;
      node.py -= dy * k;

它看起来似乎是quad.count是四叉树节点中的粒子数.但是在https://github.com/mbostock/d3/blob/master/d3.geom.js#L696中查看他们的四叉树代码,我找不到任何参考,以及如何计算它.我问,因为我想修改一些东西,或许改变每个节点的"权重"或"收费".count

我正在尝试在我正在制作的游戏中使用四叉树进行碰撞检测,但我不确定如何处理可能在不同四边形之间移动的对象？

我能想到的唯一方法是每帧清除整个树,然后在那里添加所有内容,但这似乎可以获得cpu密集而且效率不高.你是否检查每一帧的每一个物体,看它是否已移出它当前四边形的界限,如果是,那么将它移除并读取它？这看起来似乎效率非常低,因为你每帧都要对每个移动物体进行碰撞检查.

此外,关于四边形但与在其中移动的对象无关,如何在同一个四边形中处理多个对象？我读过的关于它们的大多数网站都说你应该在一个四边形中只有一个,也许两个,如果你得到的更多,那么就把它们推到树上.如果你有一个像的情况下这样？你有三个圆圈,它们都在它们下方的水平边缘,所以它们不能再往下走了,但是有三个都在同一级别,人们说你不应该有.

我已经实现了 n 个点的四叉树结构以及返回给定矩形内的点数组的方法。我似乎无法找到一种算法来有效地找到最接近另一个给定点的点。我错过了一些明显的东西吗？我认为递归解决方案是正确的方法吗？

我正在使用 Objective C，但伪代码就可以了。此外，我实际上存储了经纬度数据，并且点之间的距离沿着一个大圆。

编辑： 这是我的树插入和细分代码

- (BOOL)insert:(id<PASQuadTreeDataPoint>)dataPoint {

    BOOL pointAdded = false;

    // If the point lies within the region
    if(CGRectContainsPoint(self.region, dataPoint.point)) {

        // If there are less than 4 points then add this point
        if(self.dataPoints.count < kMaxPointsPerNode) {
            [self.dataPoints addObject:dataPoint];
            pointAdded = true;
        }
        else {

            // Subdivide into 4 quadrants if not already subdivided
            if(northEast == nil) [self subdivide];

            // Attempt to add the point to one of the 4 subdivided quadrants
            if([northEast insert:dataPoint]) return …

我想以类似于此示例的方式在地图上显示标记,但我有更多标记,我想使用"原生"Google地图.

到目前为止,我发现只有一个看起来能够做到这一点的库:android-maps-utils.但经过测试后发现,当有大约35000个标记时,它会出现严重的性能问题.(甚至java.lang.OutOfMemoryError).所以我想知道还有哪些其他选择.从头开始滚动我自己的解决方案可能是我想做的最后一件事.

我想,这个库根本不可用于非常大的标记计数,因为它将它们全部保存在RAM中.例如,在从文件中读取当前不可见标记时,最好过滤掉它们,并在每次摄像机移动后进行.(double从二进制文件中读取35k对DataInputStream非常快,所以现在这不是什么大问题.我想这可以进一步加速.)另外,我可以为不同的缩放级别准备预处理的集群集.文件,因为标记不会经常更改.
但是从头开始实现这一点(特别是 - 适当的集群)看起来很多工作.也许我错过了已经做过的事情？

更新

为此,我尝试使用android-maps-extensions.它工作得更好,但它也将所有标记保存在内存中,当显示大约35k标记时,它会在完全缩小时导致大约20MB的内存消耗,并且在放大时会导致大约24MB.另外大约7MB并且会出现崩溃...所以我想我需要在RAM中保留尽可能少的数据.有没有像这样工作的图书馆？

我是 ElasticSearch 的新手，我想了解使用 geohashes 和四叉树之间的区别。参考文献中写道：

• GeohashPrefixTree - 使用 geohash 作为网格方块。Geohashes 是纬度和经度交织的位的 Base32 编码字符串。所以哈希值越长，它就越精确。添加到 geohash 的每个字符代表另一个树级别，并向 geohash 添加 5 位精度。geohash 代表一个矩形区域，有 32 个子矩形。Elasticsearch 中的最大级别数为 24。
• QuadPrefixTree - 使用四叉树作为网格方块。与 geohash 类似，四叉树将纬度和经度的位交错，生成的哈希值是位集。四叉树中的树级别表示该位集中的 2 个位，每个坐标对应一个位。Elasticsearch 中四叉树的最大级别数为 50。

我不明白其中的区别，例如，如果我采取以下观点： Latitude / Longitude = 42.9123456, 21.799986 geohash 是srxs05fq8。谁能解释一下如何计算四叉树表示？

此外，什么时候选择其中一种更好？

我正在寻找一种算法来查找四叉树的邻居,在示例图像中,我得到了红色节点,如何找到蓝色节点.有任何想法吗？

我正在尝试使用 Barnes-Hut 树算法编写用于模拟 n 体问题的代码。我计划在未来使用 CUDA，因此希望我的四叉树数据结构不由堆对象组成。

作者从 Martin Burtscher 和 Keshav Pingali 的论文“基于树的 Barnes Hut n-Body 算法的高效 CUDA 实现”（抱歉找不到链接）中指出：

动态数据结构如树通常由堆对象构建，其中每个堆对象包含多个字段，例如子指针和数据字段，并且是动态分配的。因为堆对象的动态分配和访问往往很慢，所以我们使用基于数组的数据结构。如果数组元素是具有多个字段的对象，则无法合并对数组的访问，因此我们使用多个对齐的标量数组，每个字段一个，如图 6.6 所示。因此，我们的代码使用数组索引而不是指向树节点的指针。

我了解对齐标量数组的部分（即并行计算中的 SOA 与 AOS 习惯用法），但不幸的是，作者没有解释如何使用数组构造四叉树。

我的问题是如何使用数组实现四叉树数据结构（使用插入空间点的方法）？我知道如何使用节点结构和子节点指针等以传统方式实现四叉树。有人可以提供详细说明如何使用数组执行此操作的参考。甚至关于如何使用数组实现二叉树（或任何树）的信息在这里也可能有用。

我已经实现了一种批量加载点四叉树的方法.但对于某些输入,它无法正常工作,例如,如果有许多点具有相同的x坐标或y坐标.示例数据集将是:

test = [(3, 1), (16, 1), (11, 4), (5, 4), (9, 6), (5, 10),
        (1, 15), (11, 5), (11, 15), (12, 16), (19, 17)]
tree = create(test)

问题发生在以下几点:(11,4),(11,5),(11,15)和(5,10),(5,4).

这是create功能:

def create(point_list, presorted=False):
    if not point_list:
        return QuadNode()

    if not presorted:
        point_list.sort(key=lambda p: [p[0],p[1]])

    median = len(point_list) >> 1

    relevantPoint = point_list[median]
    relevantYCoordinate = relevantPoint[1]

    node = QuadNode(data=relevantPoint)

    leftBins = point_list[:median]
    rightBins = point_list[median + 1:]

    nwBins = [bin for bin in leftBins if …