Re: [Boost-users] geometry: knn search of point to many linestrings?

Jens Thiele writes:

Adam Wulkiewicz via Boost-users writes:

...

W dniu 23.05.2021 o 17:33, Adam Wulkiewicz pisze:

...

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.

the performance problem is fixed now [1] :-) - thanks again! Another problem I face now is that each run produces different results which is still correct (multiple linestrings might have the same distance to some point) but I would prefer a reproducible result. I guess the cause for this is that rtree_t::const_query_iterator it=t->qbegin(idx::nearest(pt, tree_size)); returns an iterator where the order isn't stable. Would it be difficult to fix the iteration order? Jens [1] s.a. https://github.com/boostorg/geometry/issues/867