Query points using Boost

Question

I seem to get incorrect results when using boost to query for points. Using a separate algorithm (using BSTs), I get an answer of 2000 points on average for each query but using boost I get an answer of 10 points. This is the fist time I am using Boost, so can some one help me on what I am messing up.

About the code: I put 1M random points (with x,y between 0 and 1). Then I run queries for 100 small random regions and count number of matches.

#include <iostream>
#include <vector>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <iomanip>

#include <boost/geometry/geometry.hpp>
#include <boost/geometry/geometries/geometries.hpp> 
#include <boost/geometry/geometries/point.hpp>
#include <boost/geometry/index/rtree.hpp>

using namespace std;
namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;
typedef bg::model::point<double, 2, bg::cs::cartesian> point;
typedef bg::model::box<point> box;    

struct particle
{
  double x;
  double y;
};

int main(int argc, char *argv[])
{
  int N=1000000;
  clock_t start,stop;

  vector<particle> myvec(N);
  vector<particle>::iterator cii;
  //Set vector values
  for (cii = myvec.begin(); cii != myvec.end(); ++cii)
    {
    cii->x =1.0*rand()/RAND_MAX;
    cii->y =1.0*rand()/RAND_MAX;
    }

  //Build R-tree
  start=clock();
  bgi::rtree<point, bgi::quadratic<16> > rtree;
  for (cii=myvec.begin();cii!=myvec.end(); ++cii)
    { 
     double x = cii->x;
     double y = cii->y;
     point p(x,y);
     rtree.insert(p);
    }
  stop=clock();
  cout<<"Time for building R tree "<<(stop-start)/(double) CLOCKS_PER_SEC<<endl;

  //Build Query List
  vector<particle> querylist(100);
  for (cii = querylist.begin(); cii != querylist.end(); ++cii)
    {
    cii->x =1.0*rand()/RAND_MAX;
    cii->y =1.0*rand()/RAND_MAX;
    }

  //Query R-tree
  start=clock();
  for (cii = querylist.begin(); cii != querylist.end(); ++cii)
    {
    double x = cii->x;
    double y = cii->y;
    double lx = x - .001;
    double ux = x + .001;
    double ly = y - .001;
    double uy = y + .001;
    point p1(lx,ly), p2(ux,uy);
    box query_box(p1, p2);

    vector<point> queryresult;
    rtree.query(bgi::intersects(query_box), std::back_inserter(queryresult));

    std::cout << "The intersection has " << (queryresult.size()) << " elements:\n";
    }
  stop=clock();
  cout<<"Time for query "<<(stop-start)/(double) CLOCKS_PER_SEC<<endl;

  return 0;
}

Answer 1

Your sample is not statistically sound.

Let's make the query boxes significantly larger:

double const delta = .05; // so boxes are .1x.1, i.e. 1/100th of total area
// and later
for (auto& p : querylist) {
    box query_box(point {p.x - delta, p.y - delta}, point {p.x + delta, p.y + delta});

Results in exactly the expected number of hits:

Live On Coliru

Time for building R tree 2182054657 nanoseconds
Time for query 52749607 nanoseconds
Average intersections: 10000.3
Standard deviation:    98.9173
Expected mean:         10000

Code

Notes

• replaced rand() with Boost Random (uniform_real<> distribution)
• fixed the boxes to not overlap the border of the region (so we get no skewed results)

• instead of filling a vector each time, just measure the number of query results:

  auto n = std::distance(
          bgi::qbegin(rtree, bgi::intersects(query_box)),
          bgi::qend(rtree));
  

• instead of "anecdotally" reporting some "intersection" counts, do some proper statistics using Boost Accumulator:

  std::cout << "Average intersections: " << ba::mean(stats) << "\n";
  std::cout << "Standard deviation:    " << sqrt(ba::variance(stats)) << "\n";
  
  std::cout << "Expected mean:         " << (N * (2*delta) * (2*delta)) << "\n";
  

Full Listing

#include <iostream>
#include <vector>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <iomanip>

#include <boost/geometry/geometry.hpp>
#include <boost/geometry/geometries/geometries.hpp>
#include <boost/geometry/geometries/point.hpp>
#include <boost/geometry/index/rtree.hpp>
#include <boost/random.hpp>
#include <boost/chrono.hpp>

#include <boost/accumulators/accumulators.hpp>
#include <boost/accumulators/statistics.hpp>

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

double const delta = .05; // so boxes are .1x.1, i.e. 1/100th of total area

typedef bg::model::point<double, 2, bg::cs::cartesian> point;
typedef bg::model::box<point> box;

struct particle {
    double x;
    double y;
};

namespace ba  = boost::accumulators;
namespace bat = ba::tag;
using hrc = boost::chrono::high_resolution_clock;

int main() {
    boost::mt19937 prng(std::random_device{}());
    size_t N = 1000000ul;

    std::vector<particle> myvec;
    myvec.reserve(N);

    {
        boost::uniform_real<double> dist(0,1);

        // Set vector values
        for (size_t i = 0; i<N; ++i)
            myvec.push_back({dist(prng), dist(prng)});
    }

    // Build R-tree
    auto start = hrc::now();

    bgi::rtree<point, bgi::quadratic<16> > rtree;
    for (auto& p : myvec)
        rtree.insert(point {p.x, p.y});

    auto stop = hrc::now();
    std::cout << "Time for building R tree " << (stop - start) << std::endl;

    // Build Query List
    std::vector<particle> querylist;
    querylist.reserve(100);

    {
        boost::uniform_real<double> dist(0+delta,1-delta);

        for (size_t i = 0; i<100; ++i)
            querylist.push_back({dist(prng), dist(prng)});
    }

    ba::accumulator_set<double, ba::stats<bat::mean, bat::variance>> stats;

    // Query R-tree
    start = hrc::now();
    for (auto& p : querylist) {
        box query_box(point {p.x - delta, p.y - delta}, point {p.x + delta, p.y + delta});

#if 0
        std::vector<point> queryresult;
        rtree.query(bgi::intersects(query_box), std::back_inserter(queryresult));

        //std::cout << "The intersection has " << queryresult.size() << " elements:\n";
        stats(queryresult.size());
#else
        auto n = std::distance(
                bgi::qbegin(rtree, bgi::intersects(query_box)),
                bgi::qend(rtree));
        stats(n);
#endif
    }
    stop = hrc::now();
    std::cout << "Time for query " << (stop - start) << "\n";
    std::cout << "Average intersections: " << ba::mean(stats) << "\n";
    std::cout << "Standard deviation:    " << sqrt(ba::variance(stats)) << "\n";

    std::cout << "Expected mean:         " << (N * (2*delta) * (2*delta)) << "\n";
}

Scaling

Note that the results scale:

double const delta = .005; // so boxes are .01x.01, i.e. 1/10000th of total area

Time for building R tree 2101529662 nanoseconds
Time for query 2982070 nanoseconds
Average intersections: 99.69
Standard deviation:    8.96069
Expected mean:         100

And even

double const delta = .00005; // so boxes are .0001x.0001, i.e. 1/100000000th of total area

Time for building R tree 726361394 nanoseconds
Time for query 216690 nanoseconds
Average intersections: 0.02
Standard deviation:    0.14
Expected mean:         0.01