Boost geometry 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。现在，当您尝试插入一个与 a 框具有相同几何形状的新输入框时，您调用 nearest prediacte，结果数为 1。输入几何与 a 之间的 distance 为 0，但 distance(input,b) 也为 0。 nearest 仅限 return 一盒 - 哪一盒？你不知道，如果它 returns b 框，你将 a 的副本插入 Rtree.

安全方法可以如下：

获取新的输入框
计算其质心
从 rtree 中获取所有包含输入质心的框
遍历 returned 框并调用 equals 函数对（来自 rtee 的框，输入框）

要做到这一点，您可以使用 contains predicate which uses boost::geometry::within 方法。作为 contains/within 的输入，你传递点 - 质心，如果它被编译器丢弃（我不确定它是否可以取点），你可以将 point-centroid 扩展到小盒子中进行编译。

Boost geometry rtree 查找迭代器以精确匹配框

Boost geometry rtree find iterator for exact match of box

c++

boost

boost-geometry