Boost R-tree - 如何有效地采样随机元素

Question

我正在使用 boost 库 R-tree 将值存储在 2D 空间中。我正在尝试找到一种方法来有效地从 R 树中采样随机值。

到目前为止我已经尝试了两种方法来做到这一点，两者都有缺点。首先是在树的边界内生成一个随机点，然后找到最近的邻居：

namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;
typedef bg::model::point<double, 2, bg::cs::cartesian> point;
typedef bg::model::box<point> box;
typedef std::pair<point, indiv> value;

struct indiv {
    int ID;
    double someVal;
};


value randValueNN() { 

    std::vector<value> randPointVec;

    bg::model::box<point> bounds;
    bounds = tree.bounds();

boost::random::uniform_real_distribution<double> distX(bounds.min_corner().get<0>(), bounds.max_corner().get<0>());
    boost::random::uniform_real_distribution<double> distY(bounds.min_corner().get<1>(), bounds.max_corner().get<1>());

    point randPoint = point(distX(rng), distY(rng));

    tree.query(bgi::nearest(randPoint, 1), std::back_inserter(randPointVec));

    value result = randPointVec[0];

    return result;
};

这可以很好地工作并且非常快。但是，如果空间内存在点密度较高的区域，则不太可能选择靠近这些密集区域中心的值。 或者，我也尝试迭代 R 树来查找随机的第 n 个值：

value randValueIter() {

    int treeSize = tree.size();

    auto it = tree.begin();

    int randIndex = Crand::rand_int(1, treeSize);

    std::advance(it, randIndex);

    return *it;
};

这个方法虽然有效，但是比较慢。我想知道是否有更好的方法在 R 树中随机选择一个无偏且快速的值？

Answer 1

基本实现，使用Boost.Geometry的R树。

#include <boost/geometry/index/rtree.hpp>
#include <vector>
#include <random>

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

typedef bg::model::point<double, 2, bg::cs::cartesian> point;
typedef bg::model::box<point> box;
typedef std::pair<point, indiv> value;

struct indiv {
    int ID;
    double someVal;
};

// Function to randomly select an item from a vector with weighted probabilities
template<typename T>
const T& weighted_random_select(const std::vector<T>& items, const std::vector<double>& weights, std::mt19937& rng) {
    std::discrete_distribution<int> dist(weights.begin(), weights.end());
    return items[dist(rng)];
}

value hierarchical_random_sample(bgi::rtree<value, bgi::quadratic<16>>& tree) {
    std::mt19937 rng(std::random_device{}());
    auto node = tree.root();

    while (!node.is_leaf()) {
        std::vector<bgi::rtree< value, bgi::quadratic<16> >::node_type> children(node.children().begin(), node.children().end());
        std::vector<double> weights;
        for (const auto& child : children) {
            weights.push_back(static_cast<double>(child.second.count));
        }

        node = weighted_random_select(children, weights, rng);
    }

    // Now node is a leaf node, randomly select an element
    const auto& values = node.values();
    std::uniform_int_distribution<> dist(0, values.size() - 1);
    return values[dist(rng)];
}