
Geometry : 
Subject: Re: [geometry] Question about boost::geometry::index::rtree and the nearest predicate
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 20140122 18:22:06
Hi,
Branimir Betov wrote:
> I posted in boostusers, 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 Rtree is fully working for cartesian CS. While
performing the nearest query the Rtree must be able to calculate the
distance between Points and Boxes. Currently comparable_distance(Point,
Box) isn't officially supported so internally in the Rtree 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
Geometry list run by mateusz at loskot.net