sort points on single coordinate

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

sort points on single coordinate

Hussein Almashouq
Greeting to all,

Currently I'm using std::sort  on boost points on x-coordinte 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 ?

Hussein Almashouq


This message and its contents, including attachments are intended solely for the original recipient. If you are not the intended recipient or have received this message in error, please notify me immediately and delete this message from your computer system. Any unauthorized use or distribution is prohibited. Please consider the environment before printing this email.
_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: sort points on single coordinate

Adam Wulkiewicz
Hi Hussein,

2015-07-15 20:11 GMT+02:00 Hussein Almashouq <[hidden email]>:
Greeting to all,

Currently I'm using std::sort  on boost points on x-coordinte 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 Boost-Users mailing list.

_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Loading...