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

From: Jens Thiele (karme_at_[hidden])
Date: 2021-07-13 15:04:16

Jens Thiele <karme_at_[hidden]> writes:

> Adam Wulkiewicz via Boost-users <boost-users_at_[hidden]> 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