CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

Benoît Presles wrote:
> Hello everybody,
>
> I did a program which first computes the alpha shape (GENERAL mode) of 
> some points for a specific alpha value and then classifies the points 
> and the edges of the underlying Delaunay triangulation. The problem is 
> that I do not understand the results I get.
>
> First program:
> - I compute the alpha shape (GENERAL mode, alpha value = 
> *(A.alpha_begin())) of some points (cf. "fin.txt") and I classify the 
> points and the edges of the underlying Delaunay triangulation (cf. 
> Delaunay.png).
> Output:
> Reading 10 points from file
> Alpha Shape computed
> 1 alpha shape edges
> --OUT--
> 0.848177 0.590931 0.884446 0.641268
> EIRS 0 0 0 10
> EIRS 20 0 0 1
>
> So I get only 1 edge: 20 edges are "exterior", 1 is singular (cf. 
> alphaShapeSegments_1.png).
> I agree with this result but I do not understand why I get 10 singular 
> points (EIRS 0 0 0 10).
see below
> Second program:
> - I compute the alpha shape (GENERAL mode, alpha value = 
> *(A.alpha_begin()+9)) of some points (cf. "fin.txt") and I classify the 
> points and the edges of the underlying Delaunay triangulation (cf. 
> Delaunay.png).
> Output:
> Reading 10 points from file
> Alpha Shape computed
> 10 alpha shape edges
> --OUT--
> 0.884446 0.641268 0.727141 0.658053
> 0.848177 0.590931 0.884446 0.641268
> 0.604772 0.345775 0.69997 0.404789
> 0.727141 0.658053 0.848177 0.590931
> 0.560009 0.78025 0.407242 0.774075
> 0.324098 0.0413514 0.484923 0.0451195
> 0.188165 0.171543 0.324098 0.0413514
> 0.727141 0.658053 0.560009 0.78025
> 0.69997 0.404789 0.848177 0.590931
> 0.727141 0.658053 0.69997 0.404789
> EIRS 0 0 3 7
> EIRS 11 0 3 7
>
> In this case, I do not understand both results: "EIRS 0 0 3 7" and "EIRS 
> 11 0 3 7" (cf. alphaShapeSegments_2.png).
If you look at the classification of faces, you will see that only one 
face is in the alpha complex, thus only three edges are regular.


Considering the classification of vertices, as documented here:
http://www.cgal.org/Manual/beta/doc_html/cgal_manual/Alpha_shapes_2/Chapter_main.html#Section_40.2

"... singular/regular, that is be on the boundary of the alpha-shape, 
but not incident/incident to a triangle of the alpha-complex"

That is, a vertex stops being singular as soon as an incident face 
belongs to the alpha-complex.

This is not the definition you can find in the paper
of Edelsbrunner and Muecke and I understand this is misleading.

If you need this definition for the classification of the vertices, you 
can try uncommenting part of code in the function 
initialize_interval_vertex_map
(below
//-------------- examine incident edges --------------------------
)

> Thank you very much for your help,
> Best Regards,
> Benoît
>
>
> ------------------------------------------------------------------------
>
>
> ------------------------------------------------------------------------
>
>
> ------------------------------------------------------------------------