Boost logo

Geometry :

Subject: Re: [geometry] Question about boost::geometry::index::rtree and the nearest predicate
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2014-01-22 18:22:06


Branimir Betov wrote:
> I posted in boost-users, but looks like this list is better. Sorry
> about the double post.
> I don't know if I don't understand how the rtree works or there is a
> problem with the indexing.
> I have an rtree with about 20,000 points and I tried creating two
> rtrees with different strategies (linear and rstar) defined as follows:
> typedef boost::geometry::model::point<double, 2,
> boost::geometry::cs::spherical_equatorial<boost::geometry::degree>>point;
> boost::geometry::index::rtree< point,
> boost::geometry::index::linear<16> > coastPointsLinear;
> boost::geometry::index::rtree< point,
> boost::geometry::index::rstar<16> > coastPointsRStar;
> When I query for the nearest 3 points, I get different results returned!
> coastPointsRStar.query(bgi::nearest(point(latitude, longitude), 3),
> std::back_inserter(nearestRStar));
> coastPointsLinear.query(bgi::nearest(point(latitude, longitude), 3),
> std::back_inserter(nearestLinear));
> This seems like a bug. (I attached a text file with the list of the
> points I put in the rtree; first two columns are longitude and
> latitude). The results also seem to change if I change the maximum
> number of elements in nodes from 16 to something else (i.e. 32, 64, etc.)
Thanks for the tests and the info.

Currently, the R-tree is fully working for cartesian CS. While
performing the nearest query the R-tree must be able to calculate the
distance between Points and Boxes. Currently comparable_distance(Point,
Box) isn't officially supported so internally in the R-tree simple
function working properly only for cartesian CS is used, so yes, this is
a bug. I plan to implement this function it in the near future but not

If you're searching for a quick workaround you may want to implemement
it yourself. Something like this should work:

namespace boost { namespace geometry { namespace index { namespace detail {

typename geometry::default_distance_result<point, point>::type
comparable_distance_near(point const& pt1, point const& pt2)
     return comparable_distance(pt1, pt2); // assuming that this works
for spherical CS

typename geometry::default_distance_result<point, point>::type
comparable_distance_near(point const& pt, model::box<point> const& box)
     // your implementation here
     return comparable_distance_consistent_with_the_above;

}}}} // namespace boost::geometry::index::detail

> For what is worth, I also did an experiment with returning points in a
> box and it seems like the intersects code returns the same points
> (works as I expected) and they seem OK when I plot them in a GIS.
Yes, the balancing and spatial queries should work for other coordinate
systems as you noticed. However the R*-tree may be not optimal as it
could be because all metrics (perimeter, area, etc.) used in the
balancing algorithm are calculated with cartesian CS in mind. I should
revise/test it for other coordinate systems when I had more free time.

> Please help me figure out what I might be doing wrong - here is the
> whole test function.

Your code should work. Thanks for the results of your tests.


Geometry list run by mateusz at