Geometry Boost List: Re: [geometry] Question about boost::geometry::index::rtree and the nearest predicate

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

Hi,

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 
today.

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.
>
<snip>

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

Regards,
Adam