Boost R-tree – как эффективно отбирать случайный элемент ⇐ C++

[Anonymous]

Я использую R-дерево библиотеки Boost для хранения значений в 2D-пространстве. Я пытаюсь найти способ эффективной выборки случайных значений из R-дерева.
До сих пор я пробовал два метода, оба из которых имеют недостатки. Прежде всего, нужно создать случайную точку в пределах дерева, а затем найти ближайшего соседа:

Код: Выделить всё

namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;
typedef bg::model::point point;
typedef bg::model::box
 box;
typedef std::pair value;

struct indiv {
int ID;
double someVal;
};

value randValueNN() {

std::vector randPointVec;

bg::model::box bounds;
bounds = tree.bounds();

boost::random::uniform_real_distribution distX(bounds.min_corner().get(), bounds.max_corner().get());
boost::random::uniform_real_distribution distY(bounds.min_corner().get(), bounds.max_corner().get());

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-дереве, который был бы беспристрастным и быстрым?

Подробнее здесь: https://stackoverflow.com/questions/783 ... fficiently