Boost几何rtree查找迭代器以精确匹配盒子

Question

将新框插入 rtree 时，我想首先检查树中是否已存在相同的框。如果是，我只想获取该值，否则我需要插入一个新值。最好的（即最有效的）方法是什么？

我可以通过调用

nearest(box,1)

，然后检查相等性来做到这一点：

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <boost/geometry/index/rtree.hpp>

namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;

typedef bg::model::point<double, 1, bg::cs::cartesian> TPoint;
typedef bg::model::box<TPoint> TBox;
typedef std::pair<TBox, void*> TPair;
typedef bgi::rtree<TPair, bgi::quadratic<16>> TTree;

TTree::const_query_iterator findExact(const TTree& tree, const TBox& box)
{
    auto it = rtree.qbegin(bgi::nearest(box, 1));
    if(it == rtree.qend() || !bg::equals(it->first, box))
        return rtree.qend();
    return it;
}

这真的是执行此查询的最佳（即性能最高）方法吗？

Answer 1

这不是安全的方法。我很容易想象一种可能行不通的情况：

插入新框之前有 2 个框的 Rtree 的状态：

(0,2) --- (1,2)
  |    b    |
(0,1) --- (1,1)
  |    a    |
(0,0) --- (1,0)

所以我们有 2 个盒子

a

和

b

。现在，当您尝试插入与

nearest

框具有相同几何形状的新输入框时，您可以使用 1 作为结果数来调用

a

prediaacte。输入几何体和

distance

之间的

a

为 0，但 0 也适用于

distance(input,b)

。

nearest

仅限退回一盒 - 哪一盒？你不知道，如果它返回

b

框，则将

a

的重复项插入到 Rtree 中。

安全的方法可以如下：

1. 获取新的输入框
2. 计算其质心
3. 从 rtree 中获取包含输入质心的所有框
4. 迭代返回的框并在对（来自 rtee 的框，输入框）上调用

   equals

   函数

为此，您可以使用 contains predicate ，它使用 boost::geometry::within 方法。作为

contains/within

的输入，你传递点 - 质心，如果它被编译器丢弃（我不确定它是否可以取点），你可以将点 - 质心扩展到小盒子中进行编译。

Answer 2

这可以通过组合三个查询

covered_by

、

covers

和

satisfies

来有效实现：

const auto it = rtree.qbegin(
    bgi::covered_by(box) && 
    bgi::covers(box) &&
    bgi::satisfies([box](const TPair& item) { return item.first == box; }));

• covered_by

  ：完全匹配目标框内的较小框。

• covers

  ：匹配目标框完全位于其中的较大框。

• satisfies

  ：仅强制完全匹配。

请注意，仅使用

satisfies

会导致检查每个元素，从而得到

O(N)

而不是

O(log N)

。并且组合

covered_by

和

covers

可以让搜索提前中止，即使目标框中有许多较小的框。

satisfies

只是最终检查，以防出现一些舍入错误。

Rtree查询文档

由文档涵盖