count the frequency of groups in vector using rtree ( or any other algorithm )

Question

given following set of points in a vector {( 100, 150 ), ( 101, 152 ), ( 102, 151 ), ( 105, 155 ), ( 50, 50 ), ( 51, 55 ), ( 55, 55 ), ( 150, 250 ), ( 190, 260 ) }

I need to identify neighboring points and their count. Let us say the acceptable distance has been set as 5. Now I need following output: frequency of point ( 100, 150 ) with in 5 units is 4. frequency of point ( 50, 50 ) with in 5 units is 3 frequency of point ( 150, 250 ) within 5 units is 1 frequency of point ( 190, 260 ) within 5 units is 1

I have tried a RTree solution to this problem but couldn't determine the logic to exclude all neighboring points as candidates. Means Once I have identified there are four neighbors of ( 100, 150 ), I don't want to identify the neighbors of those neighbors. I would like to move on to next value. Here are the presumptions: 1. efficiency is the topmost concern 2. The vector is unsorted 3. the vector may contain thousands of points. I am using C++ and boost implementation of RTree. Please guide me how can I achieve the solution

Here is the code following code which does counts the number of neighbors of unique points in the vector. I need guidance on excluding neighbors of a point once they have been identified.

       include set, iostream, boost/geometry.hpp,       boost/geometry/geometries/point.hpp, boost/geometry/index/rtree.hpp

      using namespace std;
      namespace bg = boost::geometry;
      namespace bgi = boost::geometry::index;

     typedef bg::model::point<int, 2, bg::cs::cartesian> point;
     typedef std::pair<point, unsigned> value;

    struct ltstr
    {
       bool operator()(const point &p1, const point &p2) const
    {
        return (p1.get < 0 >() < p2.get < 0 >() || p1.get < 1 >() < p2.get < 1 >());
}
   };


       void main()
      {
vector<point> candidatePoints{ point(457, 184), point(457, 184), point(457, 184), point(457, 184), point(457, 184),
    point(456, 184), point(456, 184), point(456, 184), point(456, 184), point(456, 184),
    point(456, 184), point(457, 184), point(457, 184), point(457, 184), point(458, 184), point(459, 185) };

bgi::rtree< value, bgi::quadratic<16> > rtree;

set<point, ltstr> uniqueCandidatePoints;

for (int i = 0; i < candidatePoints.size(); ++i)
{
    int x = candidatePoints[i].get < 0 >();
    int y = candidatePoints[i].get < 1 >();
    uniqueCandidatePoints.insert(point(x, y));
    rtree.insert(make_pair(candidatePoints[i], i));
}

for (auto it = uniqueCandidatePoints.begin(); it != uniqueCandidatePoints.end(); ++it)
{
    std::vector<value> returnedValues;
    point currentItem = *it;
    rtree.query(bgi::satisfies([&](value const& v) {return bg::distance(v.first, currentItem) < 5; }),
        std::back_inserter(returnedValues));

    cout << "Current Item: " << currentItem.get < 0 >() << "," << currentItem.get < 1 >() << "Count: " << returnedValues.size() << endl;
} 

getchar();
  }

Answer 1

R-trees are one of the most useful spatial indexing data structures yet are proven useful for specific domains and problems. That been said, that's not a reason to refrain from being didactic (after all what's asked may be a simplification of the actual problem).

If you choose to use R-trees you are performing a domain decomposition. Much like space filling curves you can have an ordering of the space at hand, yet node elements maintan spatial vicinity (the further you get away from the root).

An ideal solution would be to build your R-Trees in a way that radius=5 regions are formed but that would require a custom data structure and a customization of STR or bulk loading algorithms and would resemble to a clustering algorithm.

With boost::index available you can identify all neiborhoods, I'll try to elaborate on the code :

Mandatory includes

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

Definitions

namespace bg  = boost::geometry;
namespace bgi = boost::geometry::index;   
using  point  = bg::model::point < float, 2, bg::cs::cartesian > ;

Auxiliaries

Boost R-Trees have a query method. Though it's designed to perform typical queries like kNN or overlaping you can feed it custom predicates. Here we design one that returns true if the point we query is up to max_dist away from a base point (both variables specified at construction)

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

Execution

For every point, we query those that lie at most distance=5 apart

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

Extensions

If you want to exlude something, I believe a clustering algorithm would be more fitting and that is out of RTrees scope. For example what if the points you exluded due to lying close to point1 happen to lie closer to a point2 ?

Yet if you really want to do it, it's just a matter of bookeeping. Define a point like so

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

and transform you for loop to

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

The Full code demonstrates the problems in this logic : lots of neighborhoods remain empty.

Same as the above can be achieved with much less code yet sightly more complicated (basically we put the query into a lambda function and use query iterators to loop through the results) Demo

Answer 2

R-tree is just a data structure but not an algorithm and to me it looks quite complicated. Unless you really need to deal with mirco efficiency I would use plain standard algorithms and a vector of points. std::count_if would be my first guess.