Geometry Boost List: Re: [geometry] Group Nearest Neighbour queries using nearest() predicate

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

Hi,

oliveoil_s wrote:
> Thank you so much for your reply . Actually the research in the following
> paper might answer some of your questions
> :http://www.cs.ust.hk/~dimitris/PAPERS/TODS05-ANN.pdf

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:

distance=min(dist(p,q1),dist(p,q2),dist(p,q3))

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

http://www.boost.org/doc/libs/1_55_0/libs/geometry/doc/html/geometry/reference/spatial_indexes/boost__geometry__index__rtree.html#geometry.reference.spatial_indexes.boost__geometry__index__rtree.indexablegetter

and

http://www.boost.org/doc/libs/1_55_0/libs/geometry/doc/html/geometry/reference/spatial_indexes/boost__geometry__index__rtree/rtree_parameters_type_const____indexable_getter_const____value_equal_const____allocator_type_const___.html#classboost_1_1geometry_1_1index_1_1rtree_1a1a6b696d4855cbf1866196fe058c3a87

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:
http://www.boost.org/doc/libs/1_55_0/libs/geometry/doc/html/geometry/spatial_indexes/queries.html#geometry.spatial_indexes.queries.user_defined_unary_predicate

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.

Regards,
Adam