подсчитать частоту групп в векторе, используя rtree (или любой другой алгоритм)

R-деревья являются одними из самых полезных пространственная индексация структуры данных пока доказали свою полезность для конкретных областей и проблем. Тем не менее, это не повод воздерживаться от дидактики (в конце концов, то, что спрашивается, может быть упрощением реальной проблемы).

Если вы решите использовать R-деревья, вы выполняете декомпозицию домена. Как и в случае с кривыми заполнения пространства, вы можете упорядочить пространство под рукой, но все же элементы узла сохраняют пространственную близость (чем дальше вы уходите от корня).

Идеальным решением было бы построить ваши R-деревья таким образом, чтобы radius=5 области формируются, но это потребует пользовательской структуры данных и настройки алгоритмов STR или массовой загрузки и будет напоминать кластеризация алгоритм.

С boost::index доступно вы можете определить все окрестности, Я постараюсь уточнить код:

Обязательно включает

#include <vector>
#include <iostream>
#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;
using  point  = bg::model::point < float, 2, bg::cs::cartesian > ;

Auxiliaries

Boost R-Trees имеют query метод. Хотя он предназначен для выполнения типичных запросов, таких как kNN или перекрывающихся, вы можете кормить его пользовательские предикаты. Здесь мы разрабатываем тот, который возвращает true если точка, которую мы запрашиваем, до max_dist от base точка (обе переменные указаны при построении)

struct distance_pred
{
point const& _base;
double       _threshold;

distance_pred(point const& base, double max_dist)
: _base(base)
, _threshold(max_dist)
{
}
bool operator()(point const& p) const
{
auto d = boost::geometry::distance(_base, p);
return d && d < _threshold;
}
};

// just for output
std::ostream& operator<<(std::ostream &os, point const& p)
{
os << "{ " << p.get<0>() << ", " << p.get<1>() << " }";
return os;
}

выполнение

Для каждой точки мы запрашиваем те, которые лежат не более distance=5 Кроме

int main()
{
std::vector<point> cloud {
point(100, 150), point(101, 152), point(102, 151),
point(105, 155), point( 50,  50), point( 51,  55),
point( 55,  55), point(150, 250), point(190, 260)
};

bgi::rtree<point, bgi::quadratic<16>> rtree(cloud.begin(), cloud.end());

std::vector<point> hood;
for (auto &&p : cloud)
{
hood.clear();
std::cout << "neighborhood of point " << p << "\n-----------------\n\n";

rtree.query(bgi::satisfies(distance_pred(p, 5)), std::back_inserter(hood));

// Output the results -----------------------------------------
if (!hood.empty())
{
for (auto &&pt : hood) std::cout << '\t' << pt << std::endl;
}
else
{
std::cout << "\t... is empty\n";
}

std::cout << std::endl;
}
}

расширения

Если вы хотите что-то исключить, я считаю, кластеризация алгоритм будет более подходящим, и это выходит за рамки RTrees. Например, что если точки, которые вы исключили из-за того, что лежали близко к точке 1, оказались ближе к точке 2?

Тем не менее, если вы действительно хотите это сделать, это просто вопрос поддержки. Определить точку так

using  pointI  = std::pair<point, std::size_t>; // remember : geometric info first

и превратить вас в петлю

for (std::size_t i(0), i < cloud.size(); ++i)
{
if (cloud.end() != std::find(rec.begin(), rec.end(), i))
{ // you'll only be building neighorhoods for points that are not touched
// queries and recording performed on point2 types
}
}

Полный код демонстрирует проблемы в этой логике: много окрестностей остаются пустыми.

То же самое, что и выше, может быть достигнуто с гораздо меньшим количеством кода, но несколько более сложным (в основном мы помещаем запрос в лямбда-функцию и используем итераторы запросов для циклического просмотра результатов). демонстрация