
Geometry : 
Subject: Re: [geometry] Rtree segment query optimization
From: Jeremy Murphy (jeremy.william.murphy_at_[hidden])
Date: 20180410 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 Rtree, but I'm also
> interested in the practical aspect of how it applies to the Rtree 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 righthand side of the query segment (assuming that an orientation is
> chosen for the segment and thus righthand side is defined).
> I.e., is it better to use a useddefined predicate with `satisfies`, or a
> builtin spatial query such as `within(Polygon)` (if that is possible)
> where the Polygon is defined to cover a sufficient finite region of the
> righthand 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
> Rtree. This means that the knn query during treetraversal will not prune
> undesireable Rtree 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 Rtree calls relational
> operations implemented in boost::geometry namespace (intersects, within,
> etc.) both for nodes and values. So you could implement your own
> segmentsidearea 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 "righthand 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 halflines 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 'halfspace' that is
not on the lefthand 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
>
Geometry list run by mateusz at loskot.net