Я пытаюсь создать дерево boost r с алгоритмом упаковки, в котором будут храниться двумерные геометрические точки. Просто чтобы быть ясным, мне не нужен поиск kNN, мне нужно найти точки, которые находятся в стороне от горизонта точки, которая является членом того же дерева r (горизонт будет радиусом). То, что я нашел до сих пор, было примерами поиска на расстоянии с использованием случайной точки (не точки, которая является членом r-дерева). Я выполнил проверку расстояния и индекса, используя bg::index::satisfies, передав метод, который проверяет, отличается ли индекс и меньше ли расстояние, чем радиус. Также я использую внутри (поле), но я не уверен, что это правильный способ использования пространственного поиска дерева r для точки, которая является членом того же дерева r. Потому что, насколько я понимаю, точка в r-дереве знает индекс ящиков, в которых она содержится, поэтому не было бы способа запросить только точку и расстояние и все же не закончить поиск всего дерева !?
это мой код
#include "stdafx.h"
#include <boost/function_output_iterator.hpp>
#include <boost/geometry/index/rtree.hpp>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <vector>
#include <iostream>
namespace bg = boost::geometry;
namespace bgi = bg::index;
typedef bg::model::point <double, 2, bg::cs::cartesian> point;
typedef std::pair<point, std::size_t> pointI;
typedef bg::model::box<point> box;
typedef std::pair<point, unsigned> value;
bool CheckIndexAndDist(pointI i, pointI j, size_t dist);
std::vector<uint64_t> res;
struct StoreDataCallback
{
template <typename Value>
void operator()(Value const& v)
{
res.push_back(v.second);
}
};
int _tmain(int argc, _TCHAR* argv[])
{
std::vector<point> contourCenters; // has some value
std::vector<pointI> cloud;
int horizon = 3;
double dX = 0;
double length = 20;
double width = 20;
dX = length/10.0;
for(int i = 0; i < length; i++)
{
for(int j = 0; j < width; j++)
{
point p;
p.set<0>((-1.0 * length / 2.0) + dX + j * dX);
p.set<1>((-1.0 * width / 2.0) + dX + i * dX);
contourCenters.push_back(p);
}
}
size_t id_gen = 0;
std::transform(
contourCenters.begin(), contourCenters.end(),
back_inserter(cloud),
[&](point const& p) { return std::make_pair(p, id_gen++); }
);
bgi::rtree<pointI, bgi::quadratic<16> > rtree(cloud);
// spatial search
box query_box(point(cloud[10].first.get<0>() - 3.2*dX, cloud[10].first.get<1>() - 3.2*dX),point(cloud[10].first.get<0>() + 3.2*dX, cloud[10].first.get<1>() + 3.2*dX));
StoreDataCallback callback;
res.clear();
rtree.query(
bgi::within(query_box) &&
bgi::satisfies([&](value const& v) {return CheckIndexAndDist(v, cloud[10],3.015*dX);}),
boost::make_function_output_iterator(callback));
return 0;
}
bool CheckIndexAndDist(pointI i, pointI j, size_t dist)
{
if ( i.second != j.second && (bg::distance(i.first, j.first) < dist))
return true;
else
return false;
}





Also I use within(box), but I'm not sure that is the correct way
Это правильно, т.е. внутри предиката находится пространственный предикат, позволяющий R-дереву геометрически отфильтровывать точки во время запроса, а также проверяется удовлетворяет предикату. Если бы у Boost.Geometry была концепция круга/сферы, вы могли бы передать ее непосредственно в предикат внутри, и удовлетворение не было бы необходимо, но, поскольку это не так, вам нужно передать поле по кругу.
Официальный интерфейс не поддерживает тип запроса, который вы хотите выполнить. Чтобы сделать что-то другое, вам нужно будет реализовать свой собственный посетитель R-дерева и применить его к R-дереву с помощью boost::geometry::index::detail::rtree::utilities::view. Посмотрите эта тема для более подробной информации.
R-дерево не знает, где в его структуре находится точка. Поэтому, если вы хотите выбрать одну произвольную точку и получить все точки в некотором радиусе вокруг нее, вам все равно придется пройти R-дерево, чтобы найти, где она находится в первую очередь, а затем искать вокруг нее. Таким образом, этот вид поиска имел бы смысл, если бы вы хотели выполнить его для некоторого количества элементов, содержащихся в R-дереве, больше 1, потому что тогда фактически вам пришлось бы пройти часть R-дерева, но затем для каждого элемента вы бы выполнили поиск по радиусу локально. Крайний случай будет делать это для всех точек, обходя все R-дерево сверху вниз и локально возвращаясь вверх по структуре R-дерева для каждой точки, чтобы получить другие точки вокруг нее.