CGAL users discussion list

[rcasero <>]

Hi,

As a follow up, I have commited the Matlab MEX function that uses CGAL's Alpha_Shape_3 here [1] to share

 https://code.google.com/p/gerardus/source/browse/trunk/matlab/CgalToolbox/CgalAlphaShape3.cpp?r=1284

That code builds and works. But as I have point sets with 400,000+ points, I tried to add the flag CGAL::Fast_location to the Delaunay triangulation, replacing 

typedef CGAL::Delaunay_triangulation_3<K, Tds>       Delaunay;

with

typedef CGAL::Delaunay_triangulation_3<K, Tds, CGAL::Fast_location> Delaunay;

as in example"43.5.2   Building Basic Alpha Shapes for Many Points"

http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Alpha_shapes_3/Chapter_main.html#Subsection_43.5.2

However, this seems to give trouble with the PointWithIndex class, and I get a compilation error. The full error is given below, but digging a bit into it, it seems that the problem is with

/home/rcasero/Documents/gerardus/matlab/CgalToolbox/CgalAlphaShape3.cpp:175:   instantiated from here

/usr/include/c++/4.4/bits/stl_uninitialized.h:74: error: no matching function for call to ‘CGAL::Point_3<CGAL::Epick>::Point_3(std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int>&)’

Line 175 of CgalAlphaShape3.cpp is

https://code.google.com/p/gerardus/source/browse/trunk/matlab/CgalToolbox/CgalAlphaShape3.cpp?r=1284#175

<CODE>

Delaunay delaunay(x.begin(), x.end());

</CODE>

So is this a limitation of the Delaunay triangulation class when using a PointWithIndex, that only happens with CGAL::Fast_location? Or am I reading the error the wrong way?

Best regards,

Ramon.

<FULL ERROR>

[100%] Building CXX object matlab/CgalToolbox/CMakeFiles/cgal_alpha_shape3.dir/CgalAlphaShape3.cpp.o

In file included from /usr/include/c++/4.4/vector:64,

                 from /usr/local/include/ITK-4.3/itkMetaDataDictionary.h:22,

                 from /usr/local/include/ITK-4.3/itkObject.h:33,

                 from /usr/local/include/ITK-4.3/itkDataObject.h:31,

                 from /usr/local/include/ITK-4.3/itkProcessObject.h:31,

                 from /usr/local/include/ITK-4.3/itkImageSource.h:31,

                 from /usr/local/include/ITK-4.3/itkImportImageFilter.h:21,

                 from /home/rcasero/Documents/gerardus/matlab/CgalToolbox/../MatlabImportFilter.h:52,

                 from /home/rcasero/Documents/gerardus/matlab/CgalToolbox/CgalAlphaShape3.cpp:81:

/usr/include/c++/4.4/bits/stl_uninitialized.h: In static member function ‘static _ForwardIterator std::__uninitialized_copy<<anonymous> >::uninitialized_copy(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = __gnu_cxx::__normal_iterator<std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int>*, std::vector<std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int>, std::allocator<std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int> > > >, _ForwardIterator = CGAL::Point_3<CGAL::Epick>*, bool <anonymous> = false]’:

/usr/include/c++/4.4/bits/stl_uninitialized.h:117:   instantiated from ‘_ForwardIterator std::uninitialized_copy(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = __gnu_cxx::__normal_iterator<std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int>*, std::vector<std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int>, std::allocator<std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int> > > >, _ForwardIterator = CGAL::Point_3<CGAL::Epick>*]’

/usr/include/c++/4.4/bits/stl_uninitialized.h:257:   instantiated from ‘_ForwardIterator std::__uninitialized_copy_a(_InputIterator, _InputIterator, _ForwardIterator, std::allocator<_Tp>&) [with _InputIterator = __gnu_cxx::__normal_iterator<std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int>*, std::vector<std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int>, std::allocator<std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int> > > >, _ForwardIterator = CGAL::Point_3<CGAL::Epick>*, _Tp = CGAL::Point_3<CGAL::Epick>]’

/usr/include/c++/4.4/bits/stl_vector.h:1024:   instantiated from ‘void std::vector<_Tp, _Alloc>::_M_range_initialize(_ForwardIterator, _ForwardIterator, std::forward_iterator_tag) [with _ForwardIterator = __gnu_cxx::__normal_iterator<std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int>*, std::vector<std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int>, std::allocator<std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int> > > >, _Tp = CGAL::Point_3<CGAL::Epick>, _Alloc = std::allocator<CGAL::Point_3<CGAL::Epick> >]’

/usr/include/c++/4.4/bits/stl_vector.h:1002:   instantiated from ‘void std::vector<_Tp, _Alloc>::_M_initialize_dispatch(_InputIterator, _InputIterator, std::__false_type) [with _InputIterator = __gnu_cxx::__normal_iterator<std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int>*, std::vector<std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int>, std::allocator<std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int> > > >, _Tp = CGAL::Point_3<CGAL::Epick>, _Alloc = std::allocator<CGAL::Point_3<CGAL::Epick> >]’

/usr/include/c++/4.4/bits/stl_vector.h:303:   instantiated from ‘std::vector<_Tp, _Alloc>::vector(_InputIterator, _InputIterator, const _Alloc&) [with _InputIterator = __gnu_cxx::__normal_iterator<std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int>*, std::vector<std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int>, std::allocator<std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int> > > >, _Tp = CGAL::Point_3<CGAL::Epick>, _Alloc = std::allocator<CGAL::Point_3<CGAL::Epick> >]’

/home/rcasero/Documents/gerardus/cpp/src/third-party/CGAL-4.2/include/CGAL/Triangulation_hierarchy_3.h:133:   instantiated from ‘ptrdiff_t CGAL::Triangulation_hierarchy_3<Tr>::insert(InputIterator, InputIterator) [with InputIterator = __gnu_cxx::__normal_iterator<std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int>*, std::vector<std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int>, std::allocator<std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int> > > >, Tr = CGAL::Delaunay_triangulation_3<CGAL::Epick, CGAL::Triangulation_data_structure_3<CGAL::Triangulation_hierarchy_vertex_base_3<CGAL::Alpha_shape_vertex_base_3<CGAL::Epick, CGAL::Triangulation_vertex_base_with_info_3<long unsigned int, CGAL::Epick, CGAL::Triangulation_vertex_base_3<CGAL::Epick, CGAL::Triangulation_ds_vertex_base_3<CGAL::Triangulation_data_structure_3<CGAL::Alpha_shape_vertex_base_3<CGAL::Epick, CGAL::Triangulation_vertex_base_with_info_3<long unsigned int, CGAL::Epick, CGAL::Triangulation_vertex_base_3<CGAL::Epick, CGAL::Triangulation_ds_vertex_base_3<void> > >, CGAL::Boolean_tag<false>, CGAL::Boolean_tag<false> >, CGAL::Alpha_shape_cell_base_3<CGAL::Epick, CGAL::Default, CGAL::Boolean_tag<false>, CGAL::Boolean_tag<false> > > > > >, CGAL::Boolean_tag<false>, CGAL::Boolean_tag<false> > >, CGAL::Alpha_shape_cell_base_3<CGAL::Epick, CGAL::Default, CGAL::Boolean_tag<false>, CGAL::Boolean_tag<false> > >, CGAL::Default>]’

/home/rcasero/Documents/gerardus/cpp/src/third-party/CGAL-4.2/include/CGAL/Triangulation_hierarchy_3.h:98:   instantiated from ‘CGAL::Triangulation_hierarchy_3<Tr>::Triangulation_hierarchy_3(InputIterator, InputIterator, const typename Tr::Geom_traits&) [with InputIterator = __gnu_cxx::__normal_iterator<std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int>*, std::vector<std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int>, std::allocator<std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int> > > >, Tr = CGAL::Delaunay_triangulation_3<CGAL::Epick, CGAL::Triangulation_data_structure_3<CGAL::Triangulation_hierarchy_vertex_base_3<CGAL::Alpha_shape_vertex_base_3<CGAL::Epick, CGAL::Triangulation_vertex_base_with_info_3<long unsigned int, CGAL::Epick, CGAL::Triangulation_vertex_base_3<CGAL::Epick, CGAL::Triangulation_ds_vertex_base_3<CGAL::Triangulation_data_structure_3<CGAL::Alpha_shape_vertex_base_3<CGAL::Epick, CGAL::Triangulation_vertex_base_with_info_3<long unsigned int, CGAL::Epick, CGAL::Triangulation_vertex_base_3<CGAL::Epick, CGAL::Triangulation_ds_vertex_base_3<void> > >, CGAL::Boolean_tag<false>, CGAL::Boolean_tag<false> >, CGAL::Alpha_shape_cell_base_3<CGAL::Epick, CGAL::Default, CGAL::Boolean_tag<false>, CGAL::Boolean_tag<false> > > > > >, CGAL::Boolean_tag<false>, CGAL::Boolean_tag<false> > >, CGAL::Alpha_shape_cell_base_3<CGAL::Epick, CGAL::Default, CGAL::Boolean_tag<false>, CGAL::Boolean_tag<false> > >, CGAL::Default>]’

/home/rcasero/Documents/gerardus/cpp/src/third-party/CGAL-4.2/include/CGAL/internal/Delaunay_triangulation_hierarchy_3.h:55:   instantiated from ‘CGAL::Delaunay_triangulation_3<Gt, Tds_, CGAL::Location_policy<CGAL::Fast> >::Delaunay_triangulation_3(InputIterator, InputIterator, const Gt&) [with InputIterator = __gnu_cxx::__normal_iterator<std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int>*, std::vector<std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int>, std::allocator<std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int> > > >, Gt = CGAL::Epick, Tds_ = CGAL::Triangulation_data_structure_3<CGAL::Alpha_shape_vertex_base_3<CGAL::Epick, CGAL::Triangulation_vertex_base_with_info_3<long unsigned int, CGAL::Epick, CGAL::Triangulation_vertex_base_3<CGAL::Epick, CGAL::Triangulation_ds_vertex_base_3<void> > >, CGAL::Boolean_tag<false>, CGAL::Boolean_tag<false> >, CGAL::Alpha_shape_cell_base_3<CGAL::Epick, CGAL::Default, CGAL::Boolean_tag<false>, CGAL::Boolean_tag<false> > >]’

/home/rcasero/Documents/gerardus/matlab/CgalToolbox/CgalAlphaShape3.cpp:175:   instantiated from here

/usr/include/c++/4.4/bits/stl_uninitialized.h:74: error: no matching function for call to ‘CGAL::Point_3<CGAL::Epick>::Point_3(std::pair<CGAL::Point_3<CGAL::Epick>, long unsigned int>&)’

/home/rcasero/Documents/gerardus/cpp/src/third-party/CGAL-4.2/include/CGAL/Point_3.h:83: note: candidates are: CGAL::Point_3<R_>::Point_3(const typename R_::RT&, const typename R_::RT&, const typename R_::RT&, const typename R_::RT&) [with R_ = CGAL::Epick]

/home/rcasero/Documents/gerardus/cpp/src/third-party/CGAL-4.2/include/CGAL/Point_3.h:75: note:                 CGAL::Point_3<R_>::Point_3(const typename R_::Kernel_base::Point_3&) [with R_ = CGAL::Epick]

/home/rcasero/Documents/gerardus/cpp/src/third-party/CGAL-4.2/include/CGAL/Point_3.h:71: note:                 CGAL::Point_3<R_>::Point_3(const CGAL::Origin&) [with R_ = CGAL::Epick]

/home/rcasero/Documents/gerardus/cpp/src/third-party/CGAL-4.2/include/CGAL/Point_3.h:69: note:                 CGAL::Point_3<R_>::Point_3() [with R_ = CGAL::Epick]

/home/rcasero/Documents/gerardus/cpp/src/third-party/CGAL-4.2/include/CGAL/Point_3.h:40: note:                 CGAL::Point_3<CGAL::Epick>::Point_3(const CGAL::Point_3<CGAL::Epick>&)

make[2]: *** [matlab/CgalToolbox/CMakeFiles/cgal_alpha_shape3.dir/CgalAlphaShape3.cpp.o] Error 1

make[1]: *** [matlab/CgalToolbox/CMakeFiles/cgal_alpha_shape3.dir/all] Error 2

make: *** [all] Error 2

</FULL ERROR>

On 2 August 2013 12:55, Ramón Casero Cañas <[hidden email]> wrote:

Hi Sebastien,

Many thanks for your indications. I struggled a bit to find the correct way to combine Triangulation_vertex_base_with_info_3 and Alpha_shape_3, but it seems to work in the end. Here's a code snippet in case it's useful for somebody else (I'm programming a Matlab MEX C++ function, so some types are specific to Matlab)

<CODE>

/* CGAL headers */

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>

#include <CGAL/Delaunay_triangulation_3.h>

#include <CGAL/Triangulation_vertex_base_with_info_3.h>

#include <CGAL/Alpha_shape_3.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;

// vertex

typedef CGAL::Triangulation_vertex_base_with_info_3<mwSize, K>  Vb;

typedef CGAL::Alpha_shape_vertex_base_3<K, Vb>       AsVb;

// cell

typedef CGAL::Alpha_shape_cell_base_3<K>             Fb;

// triangulation structure: vertex and cell

typedef CGAL::Triangulation_data_structure_3<AsVb, Fb> Tds;

typedef CGAL::Delaunay_triangulation_3<K, Tds>       Delaunay;

typedef CGAL::Alpha_shape_3<Delaunay>                Alpha_shape_3;

typedef K::Point_3                                   Point;

typedef std::pair<Point, mwIndex>                    PointWithIndex;

typedef Alpha_shape_3::Alpha_iterator                Alpha_iterator;

typedef Alpha_shape_3::Facet                         Facet;

  // read points from function

  std::vector<PointWithIndex> x(nrowsX);

  for (mwIndex i = 0; i < nrowsX; ++i) {

    x[i] = std::make_pair(

  some_function_to_read_a_point(i),

 i+1 // because this will be a row index in Matlab, 1, ..., Nrows

 );

  }

  // Delaunay triangulation

  // http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Triangulation_3/Chapter_main.html#Subsection_39.5.3

  Delaunay delaunay(x.begin(), x.end());

  CGAL_assertion(delaunay.number_of_vertices() == nrowsX);

  // compute alpha shape

  Alpha_shape_3 as(delaunay);

</CODE>

Best regards,

Ramón.

On 2 August 2013 06:29, Sebastien Loriot (GeometryFactory) [via cgal-discuss] <[hidden email]> wrote:

Use one of the following examples [1] to build the triangulation of your
points and set their indices. Then build the alpha shape from the
triangulation.

then you can do:

typedef CGAL::Delaunay_triangulation_3<.....> DT3;

....

for (std::list<Facet>::iterator it = facets.begin(); it != facets.end();
  ++it)
{
   it->first->vertex( DT3::vertex_triple_index(it->second,0) )->info();
   it->first->vertex( DT3::vertex_triple_index(it->second,1) )->info();
   it->first->vertex( DT3::vertex_triple_index(it->second,2) )->info();
}

Sebastien.

[1]
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Triangulation_3/Chapter_main.html#Subsection_39.5.3

On 08/01/2013 08:44 PM, rcasero wrote:

> Dear all,
>
> I'm computing alpha shapes on a set of points
>
>    // read points from function
>    std::vector<Point>  x =
>      some_function_to_read_points();
>
>    // compute alpha shape
>    Alpha_shape_3 as(x.begin(), x.end());
>
> based on the example from the "3D Alpha shapes" documentation:
>
> http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Alpha_shapes_3/Chapter_main.html#Subsection_43.5.1

>

> What I would like to do now is extract the triangulation of a given alpha
> shape in index form, e.g.
>
> tri = [3 2 8
>          2 1 3
>         ...]
>
> where the indices are the indices of the points in the x vector above.
>
> This is similar to a previous question I got help from Sebastien Loriot to
>
> http://cgal-discuss.949826.n4.nabble.com/Getting-index-of-facet-closest-to-a-point-tp4657635.html

>

> but I don't manage to find the right pointers in this case so that I can do
> something like
>
>     std::distance(x.begin(), some_iterator_here);
>
> to get the index.
>
> I can get a list of the facets
>
>    // get alpha-shape surface
>    std::list<Facet>        facets;
>    as.get_alpha_shape_facets(std::back_inserter(facets),
>                              Alpha_shape_3::REGULAR);
>
> and I can iterate said facets
>
>    for (std::list<Facet>::iterator it = facets.begin(); it != facets.end();
> ++it) {
>
>    }
>
>  From the documentation and an old question replied to by sloriot
>
> http://stackoverflow.com/questions/7938311/cgal-help-getting-triangles-coordinates-from-delaunay-triangulation

>

> I know I can the coordinates of the facet vertices as
>
>    for (std::list<Facet>::iterator it = facets.begin(); it != facets.end();
> ++it) {
>
>      it->first->vertex((it->second+1)%4)->point();
>      it->first->vertex((it->second+2)%4)->point();
>      it->first->vertex((it->second+3)%4)->point();
>
>    }
>
> but the it->...->point(); above are not pointing to elements in x, neither
> it->first->vertex((it->second+1)%4).
>
> Many thanks for any help or, ahem, pointers.
>
> Best regards,
>
> Ramon.
>
>
>
> --
> View this message in context: http://cgal-discuss.949826.n4.nabble.com/Extracting-triangulation-from-alpha-shape-tp4657870.html

> Sent from the cgal-discuss mailing list archive at Nabble.com.
>

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

---

If you reply to this email, your message will be added to the discussion below:

http://cgal-discuss.949826.n4.nabble.com/Extracting-triangulation-from-alpha-shape-tp4657870p4657872.html

To unsubscribe from Extracting triangulation from alpha shape, click here.
NAML

--
Dr. Ramón Casero Cañas

Oxford e-Research Centre (OeRC)
University of Oxford
7 Keble Rd
Oxford OX1 3QG

tlf     <a href=""tel:%2B44%20%280%29%201865%20610739"" value="+441865610739" target="_blank">+44 (0) 1865 610739
web     http://www.cs.ox.ac.uk/people/Ramon.CaseroCanas
photos  http://www.flickr.com/photos/rcasero/

--
Dr. Ramón Casero Cañas

Oxford e-Research Centre (OeRC)
University of Oxford
7 Keble Rd
Oxford OX1 3QG

tlf     +44 (0) 1865 610739
web     http://www.cs.ox.ac.uk/people/Ramon.CaseroCanas
photos  http://www.flickr.com/photos/rcasero/

---

View this message in context: Re: Extracting triangulation from alpha shape
Sent from the cgal-discuss mailing list archive at Nabble.com.