3

我正在寻找一种空间索引的实现，它允许我快速计算和总结指定区域中包含的值。

更长的版本：我有很多对象要存储在空间索引中。它们每个都有它们在 n 维空间中的坐标以及一个额外的值。给定一个范围，我需要快速回答以下问题：（1）该范围内有多少对象以及（2）它们所有值的总和是多少。

我知道空间索引通常是使用 R-trees 实现的。当然，我可以简单地检索一个范围内的所有对象并每次总结它们。

但是，通过将包含在该节点下的所有元素的总和和计数存储在该节点内，似乎存在显着的加速机会。因此，一旦有问题的节点完全在查询范围内，就没有必要进一步下降树。

有谁知道支持这种“缓存”操作的 C++ 实现？

4

2 回答 2

3

Boost 有一个很好的R-tree implmentation，虽然我不认为你正在寻找的功能是内置的。

一种方法是修改节点的数据类型以包含一个附加字段来表示子树元数据（子数和子树总和），或者使节点成为当前类型和元数据的元组。每当您添加、编辑或删除一个节点时，这些函数都会调用一个更新函数，该函数将沿着父节点链向上移动，增加或减少元数据。

我怀疑如果您要批量加载数据，这会更容易，因为您只需两遍即可完成，一次遍历并计算每个节点的元数据，然后执行一系列插入'不执行更新功能。

如果您不打算批量加载，另一个常见的空间索引是quadtree。这种数据结构通常更适合频繁更新的空间数据，因为它不需要一直重新平衡。我使用四叉树而不是 R 树，并且发现它们非常灵活。

于 2014-10-23T01:40:18.520 回答
1

所以你在想的是一个被扩展的 R-tree。有趣的是，虽然我猜想从这种扩充中受益，但查询区域必须非常大 WRT 存储在 R-tree 中的节点和值的边界框。否则查询将被迫仍然始终检查叶节点（但会有开销 - 计数器，额外检查）。

事实上，正如 Justin R. 所说，Boost.Geometry R-tree 实现不会在节点中存储任何计数器，允许定义存储在节点中的附加数据或用户定义的查询，至少目前是这样（Boost 1.57）。

但是，可以优化此计数查询。不需要返回任何值、创建和填充临时容器等。相反，可以在查询期间即时计算值，例如在 C++11 中这样：

size_t counter = 0;
rtree.query(bgi::intersects(box),
            boost::make_function_output_iterator(
                [&](Value const&) {
                    counter++;
                }));
于 2015-01-09T02:35:04.113 回答