Hi,

IMPORTANT!
Boost was moved to GitHub some time ago. SVN trunk has become GIT develop branch. You can browse it here: https://github.com/boostorg/geometry/tree/develop.

If you'd like to switch to GIT, here's some tutorial: https://svn.boost.org/trac/boost/wiki/TryModBoost
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:

cd modular-boost/libs/geometry
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.

Is there any particular reason that partial_sort is used?