Re: geometry: knn search of point to many linestrings?

From: Jens Thiele (karme_at_[hidden])
Date: 2021-06-14 09:33:36

Adam Wulkiewicz via Boost-users <boost-users_at_[hidden]> writes:

> W dniu 23.05.2021 o 17:33, Adam Wulkiewicz pisze:
>> W dniu 18.05.2021 o 09:34, Jens Thiele via Boost-users pisze:
>>> I have lots of linestrings and want to find the k nearest linestrings to
>>> some point.
>>>
>>> Looking at the example
>>> /libs/geometry/doc/index/src/examples/rtree/polygons_shared_ptr.cpp
>>> I first thought this should be close to the solution and I just could
>>> replace the polygons with linestrings. But now I think the nearest query
>>> in that example only finds the nearest polygon bounding boxes and not
>>> the nearest polygons. Am I correct?
>>>
>>> If yes, how would one extend that example to find the nearest polygons?
>>
>> Hi Jens,

Hi,

>>
>> Yes, your understanding is correct. Bounding boxes of polygons
>> together with pointers to polygons are stored in the rtree. This is
>> also what is returned by the query. So you need to calculate the
>> distances to actual linestrings by yourself.
>>
>> I propose you to use query iterators instead of query function. Then
>> you can iterate over nearest boxes (passing the number of values
>> stored in the rtree into the nearest predicate). In the loop
>> calculate distances to linestrings and break when you have enough of
>> them. You should probably break when the number of linestrings you
>> have is equal to your K and the distance to the furthest linestring
>> is lesser than the distance to the current box returned by the rtree
>> query (because then you know that you will not get any closer
>> linestring). To track the furthest linestring you can use
>> std::priority_queue.
>>
>> Adam
>
> Correction: "the current box returned by the rtree query"
>
> I of course had in mind: "the current box returned by the query iterator"

I followed that route and the results look correct but performance is
really bad.
Nearly all time (0.5s with a really small test) is consumed by qbegin:
rtree_t::const_query_iterator it = t->qbegin(idx::nearest(pt,
tree_size));

Any ideas how to improve performance?

Jens