Hilbert Sort on a User Defined Point

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

Hilbert Sort on a User Defined Point

Derek
Hello,

I'm looking to sort a vector of points using the hilbert_sort function.
The problem is that I have a user defined point. My attempts to implement
this so far have failed. Is there a way to use the traits mechanism
mentioned in the user manual to sort user defined (3D) points?

Thank you,
Derek



--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss

Reply | Threaded
Open this post in threaded view
|

Re: Hilbert Sort on a User Defined Point

Sylvain Pion
Administrator
Le 09/08/10 18:48, Derek Basehore a écrit :
> I'm looking to sort a vector of points using the hilbert_sort function.
> The problem is that I have a user defined point. My attempts to implement
> this so far have failed. Is there a way to use the traits mechanism
> mentioned in the user manual to sort user defined (3D) points?

Yes.
What failed exactly in your attempts ?

--
Sylvain

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss

Reply | Threaded
Open this post in threaded view
|

Re: Hilbert Sort on a User Defined Point

Derek
Specifically,

I got as far as figuring out that I needed to implement a custom SpatialSortingTraits_3 class. I implemented it with all of the required functions, except I didn't know what to do for the Has Models section.

It says at the end of the page in the User Manual that SpatialSortingTraits_3 should have any CGAL kernel. I don't know what to do for that part, so the code does not compile.

Other than that, I just create a Hilbert_sort_3 object templatized to the SpatialSortingTraits_3 class I created and use its function.

Compilation produces a bunch of template errors that narrow down to:

error: no match for ‘operator<’

Thanks
Reply | Threaded
Open this post in threaded view
|

Re: Hilbert Sort on a User Defined Point

Sylvain Pion
Administrator
Le 09/08/10 21:43, Derek a écrit :

>
> Specifically,
>
> I got as far as figuring out that I needed to implement a custom
> SpatialSortingTraits_3 class. I implemented it with all of the required
> functions, except I didn't know what to do for the Has Models section.
>
> It says at the
> http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Spatial_sorting_ref/Concept_SpatialSortingTraits_3.html#Cross_link_anchor_1675
> end of the page in the User Manual  that SpatialSortingTraits_3 should have
> any CGAL kernel. I don't know what to do for that part, so the code does not
> compile.

There is nothing to do here.  It says that CGAL kernels (e.g. CGAL::Cartesian...)
aremodels of this concept.

> Other than that, I just create a Hilbert_sort_3 object templatized to the
> SpatialSortingTraits_3 class I created and use its function.
>
> Compilation produces a bunch of template errors that narrow down to:
>
> error: no match for ‘operator<’

Can you send the code of your traits class, and the complete error message ?

--
Sylvain

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss

Reply | Threaded
Open this post in threaded view
|

Re: Hilbert Sort on a User Defined Point

Derek
Here's the complex error massage:

In file included from /usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/algorithm:62,
                 from nn_test.h:24,
                 from nn_test.cc:10:
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h: In function ‘const _Tp& std::__median(const _Tp&, const _Tp&, const _Tp&) [with _Tp = Point3]’:
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:2268:   instantiated from ‘void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >, _Size = int]’
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:5220:   instantiated from ‘void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >]’
nn_test.cc:327:   instantiated from here
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:89: error: no match for ‘operator<’ in ‘__a < __b’
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:90: error: no match for ‘operator<’ in ‘__b < __c’
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:92: error: no match for ‘operator<’ in ‘__a < __c’
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:96: error: no match for ‘operator<’ in ‘__a < __c’
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:98: error: no match for ‘operator<’ in ‘__b < __c’
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h: In function ‘_RandomAccessIterator std::__unguarded_partition(_RandomAccessIterator, _RandomAccessIterator, _Tp) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >, _Tp = Point3]’:
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:2268:   instantiated from ‘void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >, _Size = int]’
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:5220:   instantiated from ‘void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >]’
nn_test.cc:327:   instantiated from here
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:2209: error: no match for ‘operator<’ in ‘__first.__gnu_cxx::__normal_iterator<_Iterator, _Container>::operator* [with _Iterator = Point3*, _Container = std::vector<Point3, std::allocator<Point3> >]() < __pivot’
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:2268:   instantiated from ‘void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >, _Size = int]’
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:5220:   instantiated from ‘void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >]’
nn_test.cc:327:   instantiated from here
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:2212: error: no match for ‘operator<’ in ‘__pivot < __last.__gnu_cxx::__normal_iterator<_Iterator, _Container>::operator* [with _Iterator = Point3*, _Container = std::vector<Point3, std::allocator<Point3> >]()’
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h: In function ‘void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >]’:
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:2178:   instantiated from ‘void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >]’
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:5222:   instantiated from ‘void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >]’
nn_test.cc:327:   instantiated from here
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:2106: error: no match for ‘operator<’ in ‘__val < __first.__gnu_cxx::__normal_iterator<_Iterator, _Container>::operator* [with _Iterator = Point3*, _Container = std::vector<Point3, std::allocator<Point3> >]()’
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h: In function ‘void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >]’:
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:5067:   instantiated from ‘void std::partial_sort(_RAIter, _RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >]’
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:2256:   instantiated from ‘void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >, _Size = int]’
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:5220:   instantiated from ‘void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >]’
nn_test.cc:327:   instantiated from here
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:1906: error: no match for ‘operator<’ in ‘__i.__gnu_cxx::__normal_iterator<_Iterator, _Container>::operator* [with _Iterator = Point3*, _Container = std::vector<Point3, std::allocator<Point3> >]() < __first.__gnu_cxx::__normal_iterator<_Iterator, _Container>::operator* [with _Iterator = Point3*, _Container = std::vector<Point3, std::allocator<Point3> >]()’
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h: In function ‘void std::__unguarded_linear_insert(_RandomAccessIterator, _Tp) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >, _Tp = Point3]’:
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:2112:   instantiated from ‘void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >]’
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:2178:   instantiated from ‘void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >]’
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:5222:   instantiated from ‘void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >]’
nn_test.cc:327:   instantiated from here
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:2067: error: no match for ‘operator<’ in ‘__val < __next.__gnu_cxx::__normal_iterator<_Iterator, _Container>::operator* [with _Iterator = Point3*, _Container = std::vector<Point3, std::allocator<Point3> >]()’
In file included from /usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:62,
                 from /usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/algorithm:62,
                 from nn_test.h:24,
                 from nn_test.cc:10:
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_heap.h: In function ‘void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >, _Distance = int, _Tp = Point3]’:
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_heap.h:394:   instantiated from ‘void std::make_heap(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >]’
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:1904:   instantiated from ‘void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >]’
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:5067:   instantiated from ‘void std::partial_sort(_RAIter, _RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >]’
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:2256:   instantiated from ‘void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >, _Size = int]’
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:5220:   instantiated from ‘void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >]’
nn_test.cc:327:   instantiated from here
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_heap.h:232: error: no match for ‘operator<’ in ‘__first.__gnu_cxx::__normal_iterator<_Iterator, _Container>::operator+ [with _Iterator = Point3*, _Container = std::vector<Point3, std::allocator<Point3> >](((const ptrdiff_t&)((const ptrdiff_t*)(& __secondChild)))).__gnu_cxx::__normal_iterator<_Iterator, _Container>::operator* [with _Iterator = Point3*, _Container = std::vector<Point3, std::allocator<Point3> >]() < __first.__gnu_cxx::__normal_iterator<_Iterator, _Container>::operator+ [with _Iterator = Point3*, _Container = std::vector<Point3, std::allocator<Point3> >](((const ptrdiff_t&)((const ptrdiff_t*)(&(__secondChild + -0x000000001))))).__gnu_cxx::__normal_iterator<_Iterator, _Container>::operator* [with _Iterator = Point3*, _Container = std::vector<Point3, std::allocator<Point3> >]()’
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_heap.h: In function ‘void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >, _Distance = int, _Tp = Point3]’:
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_heap.h:244:   instantiated from ‘void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >, _Distance = int, _Tp = Point3]’
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_heap.h:394:   instantiated from ‘void std::make_heap(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >]’
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:1904:   instantiated from ‘void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >]’
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:5067:   instantiated from ‘void std::partial_sort(_RAIter, _RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >]’
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:2256:   instantiated from ‘void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >, _Size = int]’
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_algo.h:5220:   instantiated from ‘void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<Point3*, std::vector<Point3, std::allocator<Point3> > >]’
nn_test.cc:327:   instantiated from here
/usr/lib/gcc/i586-redhat-linux/4.4.1/../../../../include/c++/4.4.1/bits/stl_heap.h:134: error: no match for ‘operator<’ in ‘__first.__gnu_cxx::__normal_iterator<_Iterator, _Container>::operator+ [with _Iterator = Point3*, _Container = std::vector<Point3, std::allocator<Point3> >](((const ptrdiff_t&)((const ptrdiff_t*)(& __parent)))).__gnu_cxx::__normal_iterator<_Iterator, _Container>::operator* [with _Iterator = Point3*, _Container = std::vector<Point3, std::allocator<Point3> >]() < __value’
make: *** [nn_test.o] Error 1

The class I am using for traits is:

class Spatial_sorting_traits
{
 public:
  typedef Point3 Point_3;

  Spatial_sorting_traits() {}

  Spatial_sorting_traits(Spatial_sorting_traits &) {}

  struct Less_x_3
  {
    bool operator()(const Point_3 &p1, const Point_3 &p2)
    {
      return p1.x() < p2.x();
    }
  };
  struct Less_y_3
  {
    bool operator()(const Point_3 &p1, const Point_3 &p2)
    {
      return p1.y() < p2.y();
    }
  };
  struct Less_z_3
  {
    bool operator()(const Point_3 &p1, const Point_3 &p2)
    {
      return p1.z() < p2.z();
    }
  };

  Less_x_3 less_x_3_object() const
  {
    return Less_x_3();
  }
  Less_y_3 less_y_3_object() const
  {
    return Less_y_3();
  }
  Less_z_3 less_z_3_object() const
  {
    return Less_z_3();
  }
};

I pass this into Hilbert_sort_3 as the Traits. I'm pretty sure that my problem is the CGAL kernel. I don't know how to give my class the model for a CGAL Kernel. Should I have Spatial_sorting_traits extend the Kernel I use for my point (which is just a simple one I wrote for my point class)?
Reply | Threaded
Open this post in threaded view
|

Re: Hilbert Sort on a User Defined Point

Sylvain Pion
Administrator
Your error message doesn't mention CGAL at all.
You seem to call std::sort() on an std::vector<your Point3>,
but your Point3 is not LessThanComparable (it lacks operator<).

So, to me, this is totally unrelated.  Not knowing what is in nn_test.cpp,
I can't tell more.

> I pass this into Hilbert_sort_3 as the Traits. I'm pretty sure that my
> problem is the CGAL kernel. I don't know how to give my class the model for
> a CGAL Kernel. Should I have Spatial_sorting_traits extend the Kernel I use
> for my point (which is just a simple one I wrote for my point class)?

If you only use the spatial sort functions, then when you have is OK
(modulo the missing consts on the copy-ctor and the function operators).
Just make sure "p.x() < q.x()" and such are valid expressions for your
point type.

--
Sylvain

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss

Reply | Threaded
Open this post in threaded view
|

Re: Hilbert Sort on a User Defined Point

andreas.fabri


Hi Derek,

here comes a self contained example.

andreas



#include <CGAL/spatial_sort.h>


struct MyPoint {
   double x,y;

   MyPoint()
     : x(0), y(0)
   {}

   MyPoint(double x, double y)
     : x(x), y(y)
   {}
};


struct MyLessX {

   bool operator()(const MyPoint& p, const MyPoint& q) const
   {
     return p.x < q.x;
   }

};

struct MyLessY {

   bool operator()(const MyPoint& p, const MyPoint& q) const
   {
     return p.y < q.y;
   }

};

struct MySpatialSortingTraits {

   typedef MyPoint Point_2;

   typedef MyLessX Less_x_2;
   typedef MyLessY Less_y_2;

   Less_x_2 less_x_2_object() const
   {
     return Less_x_2();
   }

   Less_y_2 less_y_2_object() const
   {
     return Less_y_2();
   }
};

int main()
{
   MyPoint points[2];

   points[0] = MyPoint(78,12);
   points[1] = MyPoint(3,121);
   MySpatialSortingTraits sst;
   CGAL::spatial_sort(points, points+2, sst);
   std::cerr << "done" << std::endl;
   return 0;
}


--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss

Reply | Threaded
Open this post in threaded view
|

Re: Hilbert Sort on a User Defined Point

Derek
In reply to this post by Sylvain Pion
I figured it out.

In my hast to reproduce the code to where it was (since I got rid of the function calls in my code) it seems that I produced some new bugs. It seems that my Spatial_sorting_traits class was not an exact model for SpatialSortingTraits_3. There was a small mistake in a function call that prevented the code from matching to template.

Thanks for your help,
Derek