CGAL users discussion list

[Benoît Presles <>]

> Benoît Presles wrote:
> > > > Dear Sébastien,
> > > > I did more tests using the function you provided me and I really  
> > > > think that a problem could be present in the "Alpha_shape_2" class.
> > > > First program:
> > > > - I compute the alpha shape (GENERAL) with the optimal alpha  
> > > > value found with the function "find_optimal_alpha(1)".
> > > > - I display on the screen all the edges (interior, exterior,  
> > > > singular, regular) using the function you sent.
> > > > - I display on the screen all the singular and regular edges  
> > > > using alpha_shape_edges.
> > > > First test (data file "fin"):
> > > > Here is the error I get:
> > > > terminate called after throwing an instance of  
> > > > 'CGAL::Assertion_exception'
> > > > what():  CGAL ERROR: assertion violation!
> > > > Expr: ((classify((*edge_alpha_it).second.first,  
> > > > (*edge_alpha_it).second.second) == REGULAR) ||  
> > > > (classify((*edge_alpha_it).second.first,  
> > > > (*edge_alpha_it).second.second) == SINGULAR))
> > > > File: /usr/local/include/CGAL/Alpha_shape_2.h
> > > > Line: 1189
> > > > Aborted
> > > When I put this line in your code
> > > A.set_alpha(*optAlpha);
> > > I have one solid component but no assertion.
> > I redid the test and here is the result:
> > Source file: alphaShape.cpp with A.set_alpha(*optAlpha)
> > Data file: fin
> > Configuration: Ubuntu 10.04 LTS with CGAL 3.6.1 installed from  
> > sources and patched with the file you sent.
> > Compilation line: g++ -frounding-math -I/usr/local/include -L/usr/ 
> > local/lib -lCGAL alphaShape.cpp
> > Execution: ./a.out
> > Output:
> > Reading 6 points from file
> > Alpha Shape computed
> > Optimal alpha: 2
> > Nb of solid components: 1
> > REGULAR:
> > INTERIOR:
> > REGULAR:
> > INTERIOR:
> > REGULAR:
> > REGULAR:
> > INTERIOR:
> > INTERIOR:
> > INTERIOR:
> > REGULAR:
> > EIRS 0 5 5 0
> > 0 2 2 2
> > 1 1 0 2
> > 0 2 0 0
> > 0 0 1 1
> > 2 2 4 0
> > 4 0 2 0
> > 1 1 2 2
> > 2 0 2 2
> > 1 1 2 0
> > 2 0 0 0
> > terminate called after throwing an instance of  
> > 'CGAL::Assertion_exception'
> >  what():  CGAL ERROR: assertion violation!
> > Expr: ((classify((*edge_alpha_it).second.first,  
> > (*edge_alpha_it).second.second) == REGULAR) ||  
> > (classify((*edge_alpha_it).second.first,  
> > (*edge_alpha_it).second.second) == SINGULAR))
> > File: /usr/local/include/CGAL/Alpha_shape_2.h
> > Line: 1189
> > Aborted
> > > > Second test (data file "fin2"):
> > > > The function you sent classify for example the segment (0.3,0.1)- 
> > > > (0.1,0.1) as regular (which is ok) but the function  
> > > > alpha_shape_edges doesn't display it which is an error I think.
> > > with A.set_alpha(*optAlpha);
> > > I have EIRS 1 10 13 1 and 14 edges of the alpha-shape are printed
> > > (which are the correct one)
> > I also redid the test and here is the result:
> > Source file: alphaShape.cpp with A.set_alpha(*optAlpha)
> > Data file: fin2
> > Configuration: Ubuntu 10.04 LTS with CGAL 3.6.1 installed from  
> > sources and patched with the file you sent.
> > Compilation line: g++ -frounding-math -I/usr/local/include -L/usr/ 
> > local/lib -lCGAL alphaShape.cpp
> > Execution: ./a.out
> > Output:
> > Reading 13 points from file
> > Alpha Shape computed
> > Optimal alpha: 0.01
> > Nb of solid components: 1
> > REGULAR:
> > INTERIOR:
> > REGULAR:
> > REGULAR:
> > REGULAR:
> > REGULAR:
> > INTERIOR:
> > INTERIOR:
> > INTERIOR:
> > REGULAR:
> > REGULAR:
> > REGULAR:
> > SINGULAR:
> > REGULAR:
> > EXTERIOR:
> > REGULAR:
> > INTERIOR:
> > INTERIOR:
> > REGULAR:
> > INTERIOR:
> > INTERIOR:
> > INTERIOR:
> > REGULAR:
> > INTERIOR:
> > REGULAR:
> > EIRS 1 10 13 1
> > 0.1 0 0 0
> > 0.1 0.1 0 0
> > 0.1 0 0.1 0.1
> > 0 0.1 0 0.2
> > 0 0 0 0.1
> > 0.4 0 0.3 0
> > 0.1 0.1 0 0.1
> > 0.1 0.2 0 0.1
> > 0.1 0.1 0.1 0.2
> > 0.1 0.2 0.2 0.2
> > 0.1 0.2 0 0.2
> > 0.3 0.2 0.4 0.2
> > 0.3 0 0.1 0
> > 0.2 0.2 0.3 0.2
> > 0.1 0 0.3 0.1
> > 0.3 0.1 0.1 0.1
> > 0.1 0.1 0.2 0.2
> > 0.3 0.1 0.2 0.2
> > 0.4 0.2 0.4 0.1
> > 0.3 0.2 0.4 0.1
> > 0.3 0.1 0.4 0.1
> > 0.3 0.2 0.3 0.1
> > 0.4 0.1 0.4 0
> > 0.3 0.1 0.4 0
> > 0.3 0.1 0.3 0
> > ----
> > 0.3 0.2 0.2 0.2
> > 0 0 0.1 0
> > 0 0.2 0 0.1
> > 0 0.1 0 0
> > 0.2 0.2 0.1 0.2
> > 0.1 0.2 0 0.2
> > 0.1 0 0.1 0.1
> > 0.4 0.1 0.4 0.2
> > 0.4 0 0.4 0.1
> > 0.3 0.1 0.3 0
> > 0.4 0.2 0.3 0.2
> > 0.3 0 0.4 0
> > I get the same classification as you (I guess) but only 12 edges of  
> > the alpha-shape are printed.
> I do not have any problem on my machine with the same CGAL and the
> patched file. Do you have the same problem with
> Exact_predicates_exact_constructions_kernel ?

I did both tests with "Exact_predicates_exact_constructions_kernel"  
and here are the results.
First test:
Reading 6 points from file
Alpha Shape computed
Optimal alpha: 2
Nb of solid components: 1
REGULAR:
INTERIOR:
REGULAR:
INTERIOR:
REGULAR:
REGULAR:
INTERIOR:
INTERIOR:
INTERIOR:
REGULAR:
EIRS 0 5 5 0
0 2 2 2
1 1 0 2
0 2 0 0
0 0 1 1
2 2 4 0
4 0 2 0
1 1 2 2
2 0 2 2
1 1 2 0
2 0 0 0
terminate called after throwing an instance of  
'CGAL::Assertion_exception'
  what():  CGAL ERROR: assertion violation!
Expr: ((classify((*edge_alpha_it).second.first,  
(*edge_alpha_it).second.second) == REGULAR) ||  
(classify((*edge_alpha_it).second.first,  
(*edge_alpha_it).second.second) == SINGULAR))
File: /usr/local/include/CGAL/Alpha_shape_2.h
Line: 1189
Aborted

Second test:
Reading 13 points from file
Alpha Shape computed
Optimal alpha: 0.0125
Nb of solid components: 1
REGULAR:
INTERIOR:
INTERIOR:
REGULAR:
REGULAR:
REGULAR:
INTERIOR:
INTERIOR:
INTERIOR:
REGULAR:
REGULAR:
REGULAR:
REGULAR:
REGULAR:
INTERIOR:
INTERIOR:
INTERIOR:
INTERIOR:
REGULAR:
INTERIOR:
INTERIOR:
INTERIOR:
REGULAR:
INTERIOR:
INTERIOR:
EIRS 0 14 11 0
0.1 0 0 0
0.1 0.1 0 0
0.1 0 0.1 0.1
0 0.1 0 0.2
0 0 0 0.1
0.4 0 0.3 0
0.1 0.1 0 0.1
0.1 0.2 0 0.1
0.1 0.1 0.1 0.2
0.1 0.2 0.2 0.2
0.1 0.2 0 0.2
0.3 0.2 0.4 0.2
0.3 0 0.1 0
0.2 0.2 0.3 0.2
0.1 0 0.3 0.1
0.3 0.1 0.1 0.1
0.1 0.1 0.2 0.2
0.3 0.1 0.2 0.2
0.4 0.2 0.4 0.1
0.3 0.2 0.4 0.1
0.3 0.1 0.4 0.1
0.3 0.2 0.3 0.1
0.4 0.1 0.4 0
0.3 0.1 0.4 0
0.3 0.1 0.3 0
terminate called after throwing an instance of  
'CGAL::Assertion_exception'
  what():  CGAL ERROR: assertion violation!
Expr: ((classify((*edge_alpha_it).second.first,  
(*edge_alpha_it).second.second) == REGULAR) ||  
(classify((*edge_alpha_it).second.first,  
(*edge_alpha_it).second.second) == SINGULAR))
File: /usr/local/include/CGAL/Alpha_shape_2.h
Line: 1189
Aborted


The result of the second test is different (not the same  
classification) but I still get the "Assertion_exception" in both cases.
Do I need to install a specific version of Boost, GMP or MPFR ?


> > > > Second program (data file "fin2"):
> > > > - I compute the alpha shape (GENERAL) with alpha=0.0026.
> > > > - I display on the screen all the edges (interior, exterior,  
> > > > singular, regular) using the function you sent.
> > > > - I display on the screen all the singular and regular edges  
> > > > using alpha_shape_edges.
> > > > I get some exterior edges like (0.1,0.1)-(0,0) but I think with  
> > > > such a value of alpha, this edge should be interior.
> > >
> > > (0.1 x 0.1 + 0.1 x 0.1)/2 = 0.01
> > > and 0.01 > 0.0026
> > > So I see no reason why this edge should be interior.
> > Source file: alphaShape.cpp with A.set_alpha(FT(0.0026))
> > Data file: fin2
> > With such a value of alpha, I think the alpha-shape edges should be  
> > the blue edges in the image "alphaShapeFin2alpha=0.0026.jpg". So  
> > the edge (0.1,0.1)-(0,0) should be interior. Do I miss something ?
> Yes, what I wrote before:
>
> the squared distance between points (0.1,0.1) and (0,0) is
> 0.02
> You set alpha to a value which is less than the half of the squared
> distance, so the edge CANNOT be in the alpha complex.
>
> Please re-read the documentation and the reference provided for more  
> information
>
> http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Alpha_shapes_2/Chapter_main.html

You are right. I am sorry, it is my mistake.

> > Thank you very much for your help,
> > Best Regards,
> > Ben_P
> > > S.
> > >
> > > > Thank you for your help,
> > > > Best Regards,
> > > > Ben_P
> > > > Le 12 août 10 à 09:01, Sebastien Loriot (GeometryFactory) a écrit :
> > > > > If I remember correctly, the range
> > > > > [alpha_shape_edges_begin,_end] is over regular edges in  
> > > > > Regularized mode,
> > > > > and singular and regular edges in general mode (it gives you the  
> > > > > alpha-shape which is the boundary of the alpha-complex)
> > > > >
> > > > > So interior edges are not displayed.
> > > > >
> > > > >
> > > > > You this function so get the classifications:
> > > > >
> > > > > void
> > > > > alpha_edges( const Alpha_shape_2&  A)
> > > > > {
> > > > > int r=0,s=0,i=0,e=0;
> > > > > for(Alpha_shape_2::Finite_edges_iterator it =   
> > > > > A.finite_edges_begin();
> > > > >    it != A.finite_edges_end();
> > > > >    ++it)
> > > > > {
> > > > >  switch ( A.classify(*it) )
> > > > >  {
> > > > >    case Alpha_shape_2::REGULAR:  ++r; break;
> > > > >    case Alpha_shape_2::SINGULAR: ++s; break;
> > > > >    case Alpha_shape_2::EXTERIOR: ++e; break;
> > > > >    case Alpha_shape_2::INTERIOR: ++i; break;
> > > > >  }
> > > > > }
> > > > > std::cout << "EIRS " << e << " " << i << " "<< r << " " << s <<  
> > > > > std::endl;
> > > > > }
> > > > >
> > > > > S.
> > > > >
> > > > > Benoît Presles wrote:
> > > > > > Hello Everybody,
> > > > > > In my last email, I submitted you 2 problems I had with the  
> > > > > > "Alpha_shape_2" class. I still have the first problem but after  
> > > > > > some tests I realised that the results I obtained about the  
> > > > > > second problem were OK.
> > > > > > However, I still get some wrong results for some list of points  
> > > > > > (cf. attached file):
> > > > > > First test:
> > > > > > - I compute the alpha shape (GENERAL) with the optimal alpha  
> > > > > > value found with the function "find_optimal_alpha(1)" and I  
> > > > > > display on the screen the alpha edges. With such a value of  
> > > > > > alpha I should get a closed boundary, but instead I get this  
> > > > > > result:
> > > > > > Reading 13 points from file
> > > > > > Alpha Shape computed
> > > > > > Optimal alpha: 0.01
> > > > > > Nb of solid components: 1
> > > > > > 0.3 0.2 0.2 0.2
> > > > > > 0 0 0.1 0
> > > > > > 0 0.2 0 0.1
> > > > > > 0 0.1 0 0
> > > > > > 0.2 0.2 0.1 0.2
> > > > > > 0.1 0.2 0 0.2
> > > > > > 0.1 0 0.1 0.1
> > > > > > 0.4 0.1 0.4 0.2
> > > > > > 0.4 0 0.4 0.1
> > > > > > 0.3 0.1 0.3 0
> > > > > > 0.4 0.2 0.3 0.2
> > > > > > 0.3 0 0.4 0
> > > > > > Second test:
> > > > > > - I compute the alpha shape (GENERAL) with alpha=0.0025 and I  
> > > > > > display on the screen the alpha edges.  With such a value of  
> > > > > > alpha I should get much more edges but instead I get this result:
> > > > > > Reading 13 points from file
> > > > > > Alpha Shape computed
> > > > > > Optimal alpha: 0.01
> > > > > > Nb of solid components: 0
> > > > > > 0.3 0.2 0.2 0.2
> > > > > > Third test:
> > > > > > - I compute the alpha shape (GENERAL) with alpha=0.0026 and I  
> > > > > > display on the screen the alpha edges.  With such a value of  
> > > > > > alpha I get too much edges:
> > > > > > Reading 13 points from file
> > > > > > Alpha Shape computed
> > > > > > Optimal alpha: 0.01
> > > > > > Nb of solid components: 0
> > > > > > 0.3 0.2 0.2 0.2
> > > > > > 0.3 0.1 0.3 0.2
> > > > > > 0 0 0.1 0
> > > > > > 0 0.2 0 0.1
> > > > > > 0 0.1 0 0
> > > > > > 0.2 0.2 0.1 0.2
> > > > > > 0.1 0.2 0 0.2
> > > > > > 0.1 0.1 0 0.1
> > > > > > 0.1 0.1 0.1 0.2
> > > > > > 0.1 0 0.1 0.1
> > > > > > 0.4 0.1 0.4 0.2
> > > > > > 0.4 0 0.4 0.1
> > > > > > 0.3 0.1 0.3 0
> > > > > > 0.4 0.2 0.3 0.2
> > > > > > 0.4 0.1 0.3 0.1
> > > > > > 0.3 0 0.4 0
> > > > > > Thank you for your help,
> > > > > > Best Regards,
> > > > > > Ben_P
> > > > > > Le 11 août 10 à 19:07, Benoît Presles a écrit :
> > > > > > > Hello Everybody,
> > > > > > >
> > > > > > > I use the latest patched version of CGAL and I think some bugs  
> > > > > > > could be present in the "Alpha_shape_2" class (all problems  
> > > > > > > can be reproduced by using the list of points "fin" attached  
> > > > > > > in this email).
> > > > > > >
> > > > > > > First problem:
> > > > > > > - First, I use the function "find_optimal_alpha" to find the  
> > > > > > > best alpha to get 1 connected component.
> > > > > > > - Second, I set this alpha.
> > > > > > > - Third, I use the function "number_of_solid_components" to  
> > > > > > > get the number of solid components of A.
> > > > > > > - Fourth, I compute the alpha edges which I display on the  
> > > > > > > screen.
> > > > > > >
> > > > > > > When I do this last step, I get a "CGAL::Assertion_exception":
> > > > > > > Reading 6 points from file
> > > > > > > Alpha Shape computed
> > > > > > > Optimal alpha: 380.5
> > > > > > > Nb of solid components: 1
> > > > > > > terminate called after throwing an instance of  
> > > > > > > 'CGAL::Assertion_exception'
> > > > > > > what():  CGAL ERROR: assertion violation!
> > > > > > > Expr: (classify((*edge_alpha_it).second.first,  
> > > > > > > (*edge_alpha_it).second.second) == REGULAR)
> > > > > > > File: /appli/include/CGAL/Alpha_shape_2.h
> > > > > > > Line: 1170
> > > > > > > Aborted
> > > > > > >
> > > > > > > Second problem:
> > > > > > > - First, I compute the alpha shape with alpha=50.
> > > > > > > - Second, I compute the alpha edges which I display on the  
> > > > > > > screen.
> > > > > > >
> > > > > > > With such a value of alpha I should get the convex hull of the  
> > > > > > > points, but instead I get this result:
> > > > > > > Reading 6 points from file
> > > > > > > 0 0 1 0
> > > > > > > 1 0 2.5 0
> > > > > > > 2.5 0 4.5 0
> > > > > > > 4.5 0 7 0
> > > > > > >
> > > > > > >
> > > > > > > Attached, you can fine the c++ code (basically the same as in  
> > > > > > > the example) and a list of points for which the program  
> > > > > > > doesn't work as expected (both problems).
> > > > > > >
> > > > > > >
> > > > > > >
> > > > > > > Thank you for your help,
> > > > > > > Best Regards,
> > > > > > > Ben_P
> > > > > > >
> > > > > > > --
> > > > > > > You are currently subscribed to cgal-discuss.
> > > > > > > To unsubscribe or access the archives, go to
> > > > > > > https://lists-sop.inria.fr/wws/info/cgal-discuss
> > > > > > >
> > > > > > > <fin.txt><alphaShape.cpp>
> > > > >
> > > > >
> > > > > --
> > > > > You are currently subscribed to cgal-discuss.
> > > > > To unsubscribe or access the archives, go to
> > > > > https://lists-sop.inria.fr/wws/info/cgal-discuss
> > >
> > >
> > > --
> > > You are currently subscribed to cgal-discuss.
> > > To unsubscribe or access the archives, go to
> > > https://lists-sop.inria.fr/wws/info/cgal-discuss
> > ------------------------------------------------------------------------
>
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss

Attachment: alphaShape.cpp
Description: Binary data

Attachment: fin
Description: Binary data

Attachment: fin2
Description: Binary data