c++ - count the frequency of groups in vector using rtree ( or any other algorithm ) -
given following set of points in vector {( 100, 150 ), ( 101, 152 ), ( 102, 151 ), ( 105, 155 ), ( 50, 50 ), ( 51, 55 ), ( 55, 55 ), ( 150, 250 ), ( 190, 260 ) }
i need identify neighboring points , count. let acceptable distance has been set 5. need following output: frequency of point ( 100, 150 ) in 5 units 4. frequency of point ( 50, 50 ) in 5 units 3 frequency of point ( 150, 250 ) within 5 units 1 frequency of point ( 190, 260 ) within 5 units 1
i have tried rtree solution problem couldn't determine logic exclude neighboring points candidates. means once have identified there 4 neighbors of ( 100, 150 ), don't want identify neighbors of neighbors. move on next value. here presumptions: 1. efficiency topmost concern 2. vector unsorted 3. vector may contain thousands of points. using c++ , boost implementation of rtree. please guide me how can achieve solution
here code following code counts number of neighbors of unique points in vector. need guidance on excluding neighbors of point once 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; (int = 0; < 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)); } (auto = uniquecandidatepoints.begin(); != 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(); }
r-trees 1 of useful spatial indexing data structures yet proven useful specific domains , problems. been said, that's not reason refrain being didactic (after what's asked may simplification of actual problem).
if choose use r-trees performing domain decomposition. space filling curves can have ordering of space @ hand, yet node elements maintan spatial vicinity (the further away root).
an ideal solution build r-trees in way radius=5 regions formed require custom data structure , customization of str or bulk loading algorithms , resemble clustering algorithm.
with boost::index available can identify neiborhoods, i'll try elaborate on 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 query method. though it's designed perform typical queries knn or overlaping can feed custom predicates. here design 1 returns true if point query max_dist away base point (both variables specified @ 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; } }; // output std::ostream& operator<<(std::ostream &os, point const& p) { os << "{ " << p.get<0>() << ", " << p.get<1>() << " }"; return os; } execution
for every point, query lie @ 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; (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 results ----------------------------------------- if (!hood.empty()) { (auto &&pt : hood) std::cout << '\t' << pt << std::endl; } else { std::cout << "\t... empty\n"; } std::cout << std::endl; } } extensions
if want exlude something, believe clustering algorithm more fitting , out of rtrees scope. example if points exluded due lying close point1 happen lie closer point2 ?
yet if want it, it's matter of bookeeping. define point
using pointi = std::pair<point, std::size_t>; // remember : geometric info first and transform loop
for (std::size_t i(0), < cloud.size(); ++i) { if (cloud.end() != std::find(rec.begin(), rec.end(), i)) { // you'll building neighorhoods points not touched // queries , recording performed on point2 types } } the full code demonstrates problems in logic : lots of neighborhoods remain empty.
same above can achieved less code yet sightly more complicated (basically put query lambda function , use query iterators loop through results) demo
Comments
Post a Comment