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

Subject: Re: [geometry] R-tree segment query optimization
From: Jeremy Murphy (jeremy.william.murphy_at_[hidden])
Date: 2018-04-10 22:23:35

Hi Adam,
Thanks for the quick reply.

On Wed, 11 Apr 2018, 2:54 AM Adam Wulkiewicz via Geometry <
geometry_at_[hidden]> 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_at_[hidden]
> https://lists.boost.org/mailman/listinfo.cgi/geometry
>