Geometry Boost List: Re: [geometry] R-tree segment query optimization

Subject: Re: [geometry] R-tree segment query optimization
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2018-04-10 16:54:08

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 boxon line defined by segment
 Â Â Â  // doesn't lie only on one sideof 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