Re: [Boost-users] Spatial search with boost r tree

Subject: Re: [Boost-users] Spatial search with boost r tree
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2019-03-01 00:16:34

Hi Bozo,

Bozo Vazic Via Boost-users wrote:
> Hi all,
>
> I'm trying to create a boost r tree with packing algorithm that will store 2D or 3D geometric points. This will be applied in side my peridynamic software for what we call "family search". Family search is basically a simple spatial search where each point of the peridynamic mesh (cloud of geometric points) needs to find all points inside it's horizon (horizon is for 2D a circle with a specific radius and for 3D it's a sphere with a specific radius).
>
> What I've found so far were examples for distance search using a random point (not the point that is a r-tree member). I did a distance and index check using bg::index::satisfies by passing a method that checks if the index is different and is distance smaller than radius. Also I use within(box) to constrain my search, but I'm not sure that is the correct way to use r tree spatial search for the point that is a member of the same r tree. Because as far as I understand the point in the r-tree knows has the information of boxes in which it is contained, so wouldn't there be a way to query the tree member using using only the horizon value?
>
> The reason why I'm asking this question is because I need to define most optimal spatial search so that query times don't take to long. This is important as I can have several million points that need to be constantly queried.

This is the only way of doing it using the public interface of the R-tree.

One simple upgrade would be to pass a representation of a sphere into 
the R-tree. So either implement your class and overload needed 
relational operations like boost::geometry::within(Point, 
CircleOrSphere) or use nsphere from extensions in develop branch 
(https://github.com/boostorg/geometry/tree/develop/include/boost/geometry/extensions/nsphere), 
but I see that after recent changes the nsphere doesn't compile so I'll 
look into that in case you wanted to use it.

I think you're also correct that it should be possible to write more 
efficient custom algorithm traversing the whole R-tree structure once or 
at least traverses only local subtrees if needed without going from the 
root for each point. For this you'd have to write your own R-tree node 
visitor. See e.g. visitore for printing the whole R-tree:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/utilities/print.hpp#L133

If you're willing to do this I'll help you but I think better place for 
talking about it would either be Boost.Geometry mailing list 
(https://lists.boost.org/mailman/listinfo.cgi/geometry), GitHub Issue 
(https://github.com/boostorg/geometry/issues) or Gitter chat 
(https://gitter.im/boostorg/geometry). I'd probably prefer one of the 
latter two because you could publish put nice pictures and code there.

Adam