CGAL users discussion list

[rcasero <>]

The MEX C++ code for CGAL alpha shapes and fixed alpha shapes is now available here

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

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

but it's slower than the Matlab implementation by Jonas Lundgren

http://www.mathworks.co.uk/matlabcentral/fileexchange/28851-alpha-shapes/content/alphavol.m

I have done some profiling of the fixed alpha shape version, and it seems that although the alpha shape computation is fast, most of the time goes on computing the Delaunay triangulation. This is for a set of 412,068 points, for one value of alpha.

alphavol

11.469328 sec

cgal_fixed_alpha_shape3 with CGAL::Fast_location 

49.118425 sec

cgal_fixed_alpha_shape3 without CGAL::Fast_location

46.946552 sec

The breakdown of the MEX C++ functions:

<PROFILING cgal_fixed_alpha_shape3 with CGAL::Fast_location>

Initializing and reading data from Matlab

time = 0.07 sec

Computing Delaunay triangulation

Delaunay triangulation computed

time = 43.15 sec

Computing alpha shape in REGULARIZED mode by default

Alpha shape computed in REGULARIZED mode by default

time = 2.98 sec

Extracting surface triangulation for alpha = 5.80644e-07

Number of facets = 22188

Surface triangulation extracted

time = 2.52 sec

</PROFILING>

<PROFILING cgal_fixed_alpha_shape3 without CGAL::Fast_location>

Initializing and reading data from Matlab

time = 0.07 sec

Computing Delaunay triangulation

Delaunay triangulation computed

time = 41.1 sec

Computing alpha shape in REGULARIZED mode by default

Alpha shape computed in REGULARIZED mode by default

time = 2.88 sec

Extracting surface triangulation for alpha = 5.80644e-07

Number of facets = 22188

Surface triangulation extracted

time = 2.51 sec

</PROFILING>

Best regards,

Ramon.

On 5 August 2013 16:46, Ramón Casero Cañas <[hidden email]> wrote:

That works in a quick test, thanks! Will submit the code when it's finished.

Best regards,

Ramon.

On 5 August 2013 16:14, Sebastien Loriot (GeometryFactory) [via cgal-discuss] <[hidden email]> wrote:

On your side this time:

The class Fixed_alpha_shape_3 needs vertex and cell to be model of
FixedAlphaShapeVertex_3 and FixedAlphaShapeCell_3.

You can use CGAL::Fixed_alpha_shape_vertex_base_3<Gt> and
CGAL::Fixed_alpha_shape_cell_base_3<Gt>.

Sebastien.

On 08/05/2013 05:05 PM, rcasero wrote:

> On 5 August 2013 15:49, Sebastien Loriot (GeometryFactory) [via

> cgal-discuss] <[hidden email]

> </user/SendEmail.jtp?type=node&node=4657887&i=0>> wrote:

>
>     On 08/05/2013 04:33 PM, rcasero wrote:
>
>      >
>      > (As a side note, I haven't noticed a speed improvement with the
>     400,000
>      > point example).
>
>     for the location or the insertion?
>
>
>
> For the CgalAlphaShape3.cpp function overall, which reads the list of
> points from Matlab, then builds the Delaunay triangulation, then the
> alpha shape, then extracts the triangulation for a particular alpha
> value (~48 sec on my machine all together).
>
> Checking the documentation, it seems that it'll be faster using
> a Fixed_alpha_shape_3 for a single value of alpha.
>
> I have modified the function adding
>
> typedef CGAL::Fixed_alpha_shape_3<Delaunay>          Fixed_alpha_shape_3;
> ...
>    Fixed_alpha_shape_3 as2(delaunay, 0.0);
>
> (I'm not doing anything to as2 so far, only trying to create the object).
>
> But there's a compilation error "has no member named ‘is_on_chull’". Is
> this a bug like before?
>
> Full error attached.
>
> Best regards,
>
> Ramon.
>
> --
> 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/

>

> *foo.txt* (55K) Download Attachment
> <http://cgal-discuss.949826.n4.nabble.com/attachment/4657887/0/foo.txt>

>
> ------------------------------------------------------------------------
> View this message in context: Re: Extracting triangulation from alpha
> shape

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

> Sent from the cgal-discuss mailing list archive
> <http://cgal-discuss.949826.n4.nabble.com/> 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-tp4657870p4657888.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.