Boost logo

Geometry :

Subject: Re: [geometry] Group Nearest Neighbour queries using nearest() predicate
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2014-03-29 07:52:20


oliveoil_s wrote:
> Thank you so much for your reply . Actually the research in the following
> paper might answer some of your questions
> :

Thanks, I'll look at it.

>> // assuming you multipoint supports initializer lists
>> bgi::nearest(my_multi_point{point(0,0),point(100,30),point(200,60)}, 5)
>> Still this call will return 5 Values closest to any of those points.
> In case of group knn the nearest neighbour query will return those
> neighbours which have the smallest group distance from the set of query
> points .
> Let's consider we have 3 query points q1,q2,q3 for which we are searching
> the group NN, for a point p to be the group nearest neighbour of these 3
> points the distance=(dist(p,q1)+dist(p,q2)+dist(p,q3)) should be the minimum
> that any other point .

This won't work like this. In this default case the distance() between
geometries will be calculated. I hope it will be possible in 1.56 (not
sure yet) to pass various geometries to the nearest() query. E.g. Box,
Segment, MultiPoint, etc.

OGC which we're conformant with defines distance as "the shortest
distance between any two Points in the two geometric objects as
calculated in the spatial reference system of this geometric object". So
the default behavior in the case of MultiPoint/Point would rather be:


>>> There are other functions like sum,max,min,range query for group of
>>> points.
>>> Are those already supported in boost ?
>> I assume that:
>> - sum returns Values for which the sum of distances with all points is
>> the smallest one?
>> - min works like the default query
>> - should max return the furthest Value for any of those points?
> you are right .
>> - should range return the closest values but this distance should be in
>> some range?
> Actual Range query returns all the points that are within a range (distance)
> from a given point .
> Let we want to do a range query for point (0,0) with range 10 in the r-tree
> .
> we will search in the r-tree for all the points that has distance<=10 with
> point(0,0) .
> Actually as you said , generalization is major issue here . These query
> should also support Box's and that will be a great challenge .

Yes, for areal/volumetric objects there are many ways to calculate
distances. So many, that I decided to NOT support each single case (by
providing a special function) because it would obscure the interface.
The user should just be able to pass some predicates.

This way the nearest() predicate could be used with the other
primitives, even types not adapted to BG. E.g. to get 5 first objects
hit by some Ray (or a Segment). Here the distance also must be
calculated but in a different way.

>> And probably (for ranges, rays, paths)
>> 4. If the Value (checked using Indexable or Value?) should be analysed
>> 5. If the Node (checked using Box) should be analysed
> I don't get this part , What do you mean by Indexable/Value/Box ?

As you probably know, in our implementation of the rtree we may store
arbitrary types, e.g. Box, std::pair<Box, size_t>, MyType, etc. They're
stored directly in the leafs of the rtree, in the STL those types are
called value_types so I call them Values for short.

Now, the rtree must know how to handle the Value, so must know how to
retrieve some object of a Geometry type (currently only Points and
Boxes) bound with the Value. This is the Indexable, it defines the
geometrical properties of an object. By default the
index::indexable<Value> function object is used for this but you can
also pass user-defined IndexableGetter to the rtree.


It's possible that the user would like to access other data stored in
the Value to calculate the distance. E.g. if he stored std::pair<Box,
Id> he could access some container by Id to get additional data or he
could access some member of his Value type. This additional data
couldn't be obtained from the Indexable type which describes only the
geometrical properties. Though I'm not sure if this is really needed.

E.g. see how satisfies() predicate works:

And Box is just an AABB of a Node. It's a different case than the one
above. The user probably shouldn't have access to the node besides
node's AABB. That's why I signal that just a Box should be passed to the
user's predicate.


Geometry list run by mateusz at