Boost logo

Boost Users :

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



Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net