[Boost-users] Spatial search with boost r tree

Subject: [Boost-users] Spatial search with boost r tree
From: Bozo Vazic (bozo.vazic_at_[hidden])
Date: 2019-02-28 10:16:46

Hi all,

I'm trying to create a boost r tree with packing algorithm that will store 2D or 3D geometric points. This will be applied in side my peridynamic software for what we call "family search". Family search is basically a simple spatial search where each point of the peridynamic mesh (cloud of geometric points) needs to find all points inside it's horizon (horizon is for 2D a circle with a specific radius and for 3D it's a sphere with a specific radius).

What I've found so far were examples for distance search using a random point (not the point that is a r-tree member). I did a distance and index check using bg::index::satisfies by passing a method that checks if the index is different and is distance smaller than radius. Also I use within(box) to constrain my search, but I'm not sure that is the correct way to use r tree spatial search for the point that is a member of the same r tree. Because as far as I understand the point in the r-tree knows has the information of boxes in which it is contained, so wouldn't there be a way to query the tree member using using only the horizon value?

The reason why I'm asking this question is because I need to define most optimal spatial search so that query times don't take to long. This is important as I can have several million points that need to be constantly queried.

Thnx in advance for all the help.

Best Regads
Bozo

Here is my code for 2D search of only one point

#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;

    double length = 2000;
    double width = 2000;
    double dX = length/1000.0;
    double horizon = 3.015*dX;

    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;

    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;
}