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.
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.

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.

So it'd look like this:

namespace boost { namespace geometry {

template <typename Point>
 bool intersects(Point const& point, my_segment const& s)
 {
     // unfortunately you have to implement this by yourself
    // e.g. in cartesian CS find if a projection of the point
    // on line defined by segment lies on the segment
    // and/or that it lies on right side (you can use side
    // strategy for that)
 }

template <typename Box>
bool intersects(Box const& box, my_segment const& s)
{
    // unfortunately you have to implement this by yourself
    // e.g. in cartesian CS find if a projection of all 4
    // corner poins of the box on line defined by segment
    // doesn't lie only on one side of the segment outside
    // and/or that at least one of them lies on right side
    // (you can use side strategy for that)
}

}}

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);

If you're going to compare this with e.g. passing polygon or some other solution like passing only satisfies() could you share the differences in performance?

Adam