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-28 08:32:38

Hi,

oliveoil_s wrote:
> I have been using boost to implement some spatial query related algorithm.
> But i am stuck in a problem .
> I need to know whether boost already support r-tree functions for Group of
> points.
> So far i have found that nearest() predicate gives knn for only a single
> point . Is it possible or is it already implemented in Boost to search for
> multiple point ?
> Like for example , I want to find group-knn for 3 points,
> point(0,0),point(100,30),point(200,60)
> bgi::nearest({point(0,0),point(100,30),point(200,60)}, 5)  .

We plan to support other Geometries in Boost 1.56. I hope we'll able to 
do it. So your example would look like this:

// 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.

> 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?
- should range return the closest values but this distance should be in 
some range?

The support for min, max and range (AFAIU them) was there but I 
commented it out. It's because we clearly need something more generic 
than those functions. It woudl be the best if the user was able to pass 
a function object or some number of function objects defining how the 
distance is calculated and compared. This way we'd handle all of those 
above, also ray queries, path queries and probably many others. However 
the work on this was postponed because we have more pressing matters 
right now. If you like you could think about the interface for this or 
if you like, contribute some code?

The nearest query should know:
1. how to calculate the distance to Value's Indexable (or maybe to Value 
itself?) (Point, Box)
2. how to calculate the distance to Node's bounding object (Box)
3. how to compare distances

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

The most straightforward thing to do would be adding the support for the 
function object implementing all of those required functionalities, e.g.:

// assuming that Values Indexables would be passed to this, NOT Values
struct my_nearest_calculator_or_some_other_name
{
     template <typename InputGeometry, typename IndexableOrNodeBounds>
     structdistance_type
     {
         typedef .... type;
     };

     // calculate distance
     template <typename InputGeometry, typename IndexableOrNodeBounds, 
typename DistanceType>
     bool operator()(InputGeometry const& param1,
                     IndexableOrNodeBounds const& param2,
                     typename distance_type<InputGeometry, 
IndexableOrNodeBounds>::type & result)
     {
         // calculate the min distance
         result = bg::comparable_distance(param1, param2);

         // analyse all
         return true;
     }

     // define how to compare distances
     template <typename DistanceType>
     bool operator()(DistanceType const& left, DistanceType const& right)
     {
         return left < right;
     }
};

First of all, it's so non-STL! And it should probably take Value instead 
of Indexable (to be even more generic) and it would complicate the above 
implementation slightly.
We should think deeply about a solution because this would be a part of 
the interface and would stay there "forever".

The use-case should be as simple as possible, e.g.:

rt.query(nearest(my_mpoint, 5, my_calc), out);

Regards,
Adam