CGAL users discussion list

[Benoît Presles <>]

I have just tried to execute the program using CGAL 3.6.1 without the  
patch you sent and I don't get the "CGAL::Assertion_exception".
To install the patch, I copied the new "Alpha_shape_2.h" file to  
include/CGAL and did make, make install.
Did I do something wrong ?

Thank you for your help,
Best Regards,
Ben_P


Le 16 août 10 à 22:24, Benoît Presles a écrit :

> > 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
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss
>
> <alphaShape.cpp><fin><fin2>