Adam Wulkiewicz via Boost-users <boost-users@lists.boost.org> 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 _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org https://lists.boost.org/mailman/listinfo.cgi/boost-users
