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

Subject: Re: [Boost-users] Spatial search with boost r tree
From: Bozo Vazic (bozo.vazic_at_[hidden])
Date: 2019-03-01 10:36:43

Hi Adam,

Thnx for the help. First I'll try the simple upgrade for a custom circle/sphere class and see how it's going to affect the timings. After I'll look into R tree node visitor and try to write my own node visitor. If I have any questions I'll try the Gitter chat.

Best Regards
Bozo
________________________________
From: Adam Wulkiewicz [adam.wulkiewicz_at_[hidden]]
Sent: Friday, March 01, 2019 12:16 AM
To: boost-users_at_[hidden]
Cc: Bozo Vazic
Subject: Re: [Boost-users] Spatial search with boost r tree

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