boostorg / boostorg/geometry

predicates::satisfies doesn't(?) allow control over tree traversal

Open
#735 5 comments 0 reactions 0 assignees View on GitHub
enhancement
Dominant language
C++
Stars
517
Forks
232
PR merge metrics
No merged PRs in 30d

Description

AFAICT, `predicates::satisfies` lets you give an arbitrary function object and then use it to, say, visit every `rtree::value_type` in an `rtree`. It seems like it just needs a second function, which could default to `[](auto&&...) { return true; }`, to let you control the traversal of the tree. For example, suppose I want to visit an `rtree` and visit all points in the (-,+) direction of the line y=x. I think(?) there's no way to do that right now. If I have `struct IsAboveLeft { bool operator()(const Point2D& pt) const { return pt[0] - pt[1] > 0; } };` then I could use `predicates::satisfies`, but it would be an O(n) query of my `rtree`. But if I could do something like
```
struct FindAboveLeft {
bool partially_contains(const Box&) const; // check if ay part of AABB is above-left of the line y=x
bool contains(const Value&) const; // check if the point is above-left of the line y=x
};
// ...
rtree.query(satisfies(), std::back_inserter(results));
```
then the query could be O(log n) per result returned. As it is, I can't see how to get this behavior without injecting things into the `boost::geometry::index::predicates::detail` namespace. I think a predicate like this could be very expressive and allow for all sorts of interesting queries.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.