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

From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2021-05-23 15:36:19

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,
>
> 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"