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: Branimir Betov (bbetov_at_[hidden])
Date: 2014-01-22 21:11:39

Thank you for the help!

> 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
> _______________________________________________
> Geometry mailing list
> Geometry_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/geometry
<http://lists.boost.org/mailman/listinfo.cgi/geometry>