Boost logo

Geometry :

Subject: Re: [geometry] partial_sort vs nth_element in the rtree implementation
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2014-02-28 08:08:26


Boost was moved to GitHub some time ago. SVN trunk has become GIT
develop branch. You can browse it here:

If you'd like to switch to GIT, here's some tutorial:
So to use Boost.Geometry develop branch with Boost you need to replace
the last commends mentioned on the page above to something like this:

git checkout develop
git pull

and probably again run

./b2 headers

but, back to the subject.

Lu Wang wrote:
> Hi all,
> I'm now reading the source code of the rtree implementation in
> boost::geometry, especially in pack_create.hpp
> <>,
> I found that std::partial_sort is used to find the median along the
> longest dimension, which is then used to split the array and perform
> the splitting recursively:
> // pack_create.hpp, around line 281
> partial_sort(first, median, last, ...);
> per_level_packets(first, median, ...);
> per_level_packets(median, last, ...);
> It seems to me that the sortedness of the first half is never used,
> in this case, I guess that std::partial_sort may be replaced by
> std::nth_element, which should be faster.

Thanks for catching this! Tests passed, code pushed.

> Is there any particular reason that partial_sort is used?

No, I must have been under the mental influence of the R* ;).

The speedup is nice, ~4x faster for 1M random boxes.

I remember that someone on the list raised the issue of the small
preformance difference between linear split and packing algorithm some
time ago. Please recheck.


Geometry list run by mateusz at