Hi Adam,

Thanks for the quick reply.

On Wed, 11 Apr 2018, 2:54 AM Adam Wulkiewicz via Geometry <geometry@lists.boost.org> wrote:

Hi Jeremy,

Jeremy Murphy Via Geometry wrote:

Hi Adam and everyone else,

this isoriginally a theoretical question about the R-tree, but I'm also interested in the practical aspect of how it applies to the R-tree in Boost.Geometry.

How would I best optimize a KNN query if the data are points and the query geometry is a segment, but I also want to only consider points that are on the right-hand side of the query segment (assuming that an orientation is chosen for the segment and thus right-hand side is defined).

I.e., is it better to use a used-defined predicate with `satisfies`, or a built-in spatial query such as `within(Polygon)` (if that is possible) where the Polygon is defined to cover a sufficient finite region of the right-hand side of the segment? Or some other way?

I'm going to assume that you'd like to optimize speed/performance.

Yes. :)

It's possible to pass polygon in spatial predicate but I bet a faster solution is possible.

satisfied() predicate is only applied to values, not the nodes of the R-tree. This means that the knn query during tree-traversal will not prune undesireable R-tree nodes lying on one side of the segment or the other. It's because the query will know which values satisfies you but won't know nothing about the nodes.

Yes, this is exactly the kind of optimization I meant: how to best prune the nodes in the tree.

AFAIU what you'd like to do is a spatial query with infinite(?) region defined by the "side of the segment" together with knn query inside this region. Now, while performing a spatial query the R-tree calls relational operations implemented in boost::geometry namespace (intersects, within, etc.) both for nodes and values. So you could implement your own segment-side-area type, overload required spatial predicate for this type and then pass it into query in spatial predicate.

For your case it'd be bg::intersects() for both nodes (boxes) and values (points) as the first parameter and your segment as the second parameter.

I'm not sure what do you mean by "right-hand side of the query segment", the whole "half" of space on the right side of the line defined by segment or a region enclosed by the segment and 2 perpendicular half-lines starting at segment endpoints and going in some direction. Writing the comments below I assumed the latter. If you had the former in mind then sideness test (as performed by side strategy) would be enough.

Yes, I meant the first interpretation, the infinite 'half-space' that is not on the left-hand side nor collinear with the query segment, although we can ignore collinearity for simplicity.

Btw, using the cartesian side strategy the side of a point wrt line defined by segment can be checked like this:

// left of segment (> 0), right of segment (< 0), on segment (0)int side = boost::geometry::strategy::side::side_by_triangle<>::apply(segment_p1, segment_p2, point);

Aha, so that's what I need, but how can I pass that as a predicate to the rtree? Also by writing a custom predicate that basically just calls it?

Thanks for the detailed answer.

Jeremy

Adam

_______________________________________________
Geometry mailing list
Geometry@lists.boost.org
https://lists.boost.org/mailman/listinfo.cgi/geometry