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

From: Jens Thiele (karme_at_[hidden])
Date: 2021-07-14 14:28:32

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

> W dniu 13.07.2021 o 17:04, Jens Thiele via Boost-users pisze:
>> 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?
> The rtree can have different internal structure depending on balancing
> algorithm and the order of inserts. So unless you know that values are
> always inserted in the same order it's impossible to guarantee that
> the structure is going to be the same. Then the order is also
> determined by the internals of the iterator, how exactly the rtree is
> traversed, how nodes and values are prioritized based on distance. And
> yes, currently heap and sort is used and I plan to replace sort with
> minmax heap for performance. Neither of these is stable.
>
> But I don't understand what do you mean by "each run" and "stable
> order"? What the stability refers to? Could you give an example?

Problem solved. The details:

The test basically does the following:
1) create r-tree
2) knn search of some points to linestrings
3) repeat 2 and compare results

Now a few points have the same distance to multiple linestrings
and in those cases I saw some random ordering of the linestrings in the
knn search results.

But:
it wasn't the query iterator that introduced that randomness it was the
priority queue in the case where linestrings had the same distance =>
priority. To break the tie I now additionally use the ID of the
linestring => no more random ordering.

Jens