
Geometry : 
Subject: Re: [geometry] sort points on single coordinate
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 20150715 17:14:41
Hi Hussein,
20150715 20:11 GMT+02:00 Hussein Almashouq <hussein.almashouq_at_[hidden]
>:
> Greeting to all,
>
> Currently I'm using std::sort on boost points on xcoordinte as follows
>
> typedef bg::model::point<long long, 2, bg::cs::cartesian> point;
>
> typedef std::pair<point, long long> value_type;
>
> std::vector<value_type> values;
>
> // for single attribute sort on point data sets
> // std::sort needs custom comparison operator
>
> struct PointLessX {
> bool operator()(const value_type& p, const value_type& q) const
> {
> return bg::get<0>(p.first) < bg::get<0>(q.first);
> }
> };
>
>
> std::cout << "Sorting the data " << std::endl;
> PointLessX x;
> std::sort(values.begin(), values.end(), x);
>
>
>
> The above code is working fine but a bit slow when the # of points exceeds
> 10M.
>
> I looked at boost sort package and it seems it overcomes this issue
>
>
> http://www.boost.org/doc/libs/1_58_0/libs/sort/doc/html/index.html#sort.overview.intro
>
> However , I could not figure out how to adapt it to sort my boost points
> which are of value type long. It seem that I have to define some bit shift
> operator.
>
> Any suggestion please ?
>
I'm guessing you'd like to use integer_sort() ?
Have you tried to implement it like in this example:
http://www.boost.org/doc/libs/1_58_0/libs/sort/example/rightshiftsample.cpp
?
So indeed implement the rightshift function object:
struct RightShiftX {
inline long long operator()(value_type const& p, unsigned offset) const {
return bg::get<0>(p.first) >> offset; }
};
And then pass both function objects into the sorting function:
boost::sort::spreadsort::integer_sort(values.begin(), values.end(),
RightShiftX(), PointLessX());
Regards,
Adam
P.S. This is a question more closely related to Boost.Sort than
Boost.Geometry. It could be asked on BoostUsers mailing list.
Geometry list run by mateusz at loskot.net