barendgehrels on develop
test: add and use test settings (compare)
Can anyone help me to get started
No. There is plenty of material online, general and Boost specific, that should get you started in no time
Hi everyone, before I have time to write a proper issue on this for github, I hoped that I might get some preliminary feedback here. At work I was recently confronted by a problem of determining geometries that are "visible" in some obstructed space. In this case this means that I want to query objects that are located between two straight, oriented lines in 2D or planes in 3D (the cones of vision). If I understand the structure of the rtree correctly, it would be in principle possible to use it to make such query efficient. I assume this would require a new predicate.
I also mention this, because I understand that GSoC is coming up and it's only 175h this year. I am not eligible this year, but I wondered whether it could be something for the list of project ideas.
@vissarion thanks for the quick feedback. I will provide a sketch that illustrates what I mean: https://ibb.co/ynVG2RZ . By oriented lines I mean the lines passing through point_1, point_2 and point_3, point_1 (oriented in the sense the order of those points matters). I am looking for the objects to which the view from point_1 is obstructed by the obstacle point_2, point_3. These are the objects that are to the right of [point_1, point_2] and [point_3, point_1] and [point_3, point_2].
I think this would be a new spatial predicate and
is not yet efficiently decided by the existing bg rtree predicates (EDIT: I suppose currently in 2D a ring could be used that extends to the boundary of the space, I don't know the implementation of that, but I think this would involve at least some redundant tests. But I think for 3D, there is no efficient predicate yet), i.e. the bounding box of the shadow that is cased by the segment wrt to point_1 would hit many more boxes than the combination of the orientation tests above. The way I understand the structure of the rtree is that a predicate can be efficiently implemented if it can be efficiently decided for internal tree nodes and rule out their entire subtree, and I think that is the case here (we can check for the red rectangles sketch and if they don't fit the query, we don't need to search through their children).
I understand that it may be too simple for a project. There is also a 3D version of that problem, in which I would want an rtree predicate that looks for objects that lie in some half-space above a given plane. Or more generally, I think the rtree could use an interface for custom spatial queries, that requires an apply-method for internal rtree tree nodes and for rtree leaves. If I didn't miss something in the documentation, currently there is only an interface for custom unary predicates that need to be applied to each leaf in the query result (index::satisfies).
@tinko92 So AFAIU you want to get all of the points intersecting an infinite frustum. Since you want to get all of the objects intersecting it this would be a spatial query.
There is a method to do this right now but it's undocumented: https://stackoverflow.com/questions/19490435/boost-geometry-spatial-query-shapes
So indeed I think the best course would be to implement user-defined spatial predicate allowing the user to pass two functors/predicates defining the tree traversal for node bounding boxes and values stored in the rtree.
I understand that it may be too simple for a project.
Yes this would be too simple. I'm planning to do this for some time now but I still find something more important. The most tricky part of this is the interface which will be unchangeable when it's made public.
Yes, this predicate does not take a part in tree traversal at all. It's only for filtering of the resulting values. Basically working like if
std::copy_if was called after
Hi, I have some follow-up questions/comments regarding rtree queries, and I'd be interested in comments.
For a recent application of the rtree at my work (the same that could use the infinite frustum query), there would be utility in having a version of index::satisifies that takes part in the traversal. As @awulkiew mentioned, this is currently not the case and I understand it can't be done generally, but I think it can be done and have utility for some categories of custom queries.
E.g., consider a large space of geometries, some percentage of which (which also tend to be cluster close to each other), are red. Querying a box in that space for red objects would require linear search over all elements in the query box, even if none of them is red. If internal tree nodes had, aside from the bounding box of their children, some representation of whether some or none of the children are red, that query could skip entire subtrees.
More generally, I think this could be provided for user-defined index data that can be aggregated with, e.g., operator|= and compared in leaves with operator==. I understand that there are ways to achieve some of this with the current implementation. I could use an extra rtree for the red geometries, but I am not sure how well that scales for more complicated custom queries. Or I could add an extra spatial dimension and set it to 1 for red geometries, but I think that would change the results of k-nearest queries in an unintended way. I do not know how treating this field would affect the structure of the tree, maybe it would be beneficial if it makes the tree consider the value in the extra dimension in the decision for grouping nodes into subtrees.
I do not know what other applications that use the rtree look like, so I would be thankful for comments on whether custom index data like that could be useful as a general interface, from people that have more insight into it.
@tinko92 In such case the additional information would have to be stored in the internal nodes aside from the bounding box and this information would have to be calculated during the creation of the R-tree (so balancing and packing). There was a user in the past asking about it. He wanted to store planets or stars in the R-tree and to speed up the query hold the information about the total mass or some other quantity related to the objects represented by a region defined by an internal node. So yes, custom nodes + their creation and custom query using this info would be something that could be useful for sure.
Something like this could be done even now but it would be complex (and the internals of the r-tree are not documented). Internally r-tree is implemented more or less like a GIST. It is possible to define your node type, the ways how this node is created/destroyed, various balancing algorithms, etc. and all of these things are then chosen by the compiler based on tags when certain parameters are passed (e.g. these are the options for
index::linear<>: https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/options.hpp#L65-L75). AFAIR besides packing algorithm because this is always the same right now.
Are you asking because you'd like to use it at your work or because you consider this as a potential project for GSOC?
You are correct that all of the algorithms are implemented and that the interface would be the most complex part.
But to give you some idea I think that this should be implemented as a more generalized version of the rtree, let's say bounding_tree or similar. So a tree created bottom-up allowing to define any bounding geometry (spheres, oriented bounding boxes, variants. etc.) and additional data stored in the internal nodes. Maybe even allowing to define the exact type of an element stored in the internal node. Then the r-tree would be implemented on top of that.
Aside from user-defined spatial queries it would also be possible to implement user-defined knn queries. E.g. AFAIR there is an experimental version of "path query", i.e. a knn query returning the k nearest values intersecting a linear geometry which could be interpreted as first object hit by a ray or first object found on a driving path or a river, etc. So knn queries could be generalized too.
I'm also not sure if this is a good idea for a GSoC project. I'm only asking because you mentioned GSoC before.