How can I use `boost::geometry::index::rtree` to find every neighbor inside a surrounding sphere?

Question

I need to solve the following task: Say we have a two-dimensional point class

class point2
{
public:
    double& operator()(std::size_t i) { return m_x[i]; }
    double const& operator()(std::size_t i) const { return m_x[i]; }
    
private:
    std::array<double, 2> m_x;
};

and a std::vector<point2> points. Now I want to randomly add points to points and in each iteration perform a computation on every point already in points which has an Euclidean distance smaller than a given epsilon to the newly added point:

std::random_device rd; std::mt19937 g{ rd() }; std::uniform_real_distribution<> u;

for (std::size_t i = 0; i < /* ... */; ++i)
{
    point2 x;
    x[0] = u(g);
    x[1] = u(g);
    
    /* do something (which modifies `x`) with every y in points
     * whose Euclidean distance from x is smaller than epsilon */

    points.push_back(x);
}

I obviously need some kind of geometry data structure if I want to do this with high performance. I've stumbled across boost::geometry::index::rtree, but unfortunately it is hard to see for me how I actually would need to use this.

So, how would I need to do that?

First of all, I guess I need to "register" my custom point class:

namespace boost
{
    namespace geometry
    {
        namespace traits
        {
            BOOST_GEOMETRY_DETAIL_SPECIALIZE_POINT_TRAITS(point2, 2, double, boost::geometry::cs::cartesian)

            template<>
            struct access<point2, 0>
            {
                static inline double get(point2 const& p) { return p[0]; }
                static inline void set(point2& p, double const& value) { p[0] = value; }
            };

            template<>
            struct access<point2, 1>
            {
                static inline double get(point2 const& p) { return p[1]; }
                static inline void set(point2& p, double const& value) { p[1] = value; }
            };
        }
    }
}

Now I'm quite lost. I've seen this posting, but what should my surrounding box be? (It should consist of a single point).

Moreover, am I wrong or can we only search for a box (i.e. not a sphere as I need to do; as described above) inside such a tree? If so, is there a better data structure available (not necessarily inside boost)?

How can I use `boost::geometry::index::rtree` to find every neighbor inside a surrounding sphere?

0 Answers0