CGAL users discussion list

[Benoît Presles <>]

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
6
0 0
1 0
2.5 0
4.5 0
7 0
20 20
/***********************************************************************

Takes a list of points and returns a list of segments corresponding to the
Alpha shape.

************************************************************************/

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/algorithm.h>
#include <CGAL/Delaunay_triangulation_2.h>
#include <CGAL/Alpha_shape_2.h>

#include <iostream>
#include <fstream>
#include <vector>
#include <list>


typedef CGAL::Exact_predicates_inexact_constructions_kernel K;

typedef K::FT FT;

typedef K::Point_2  Point;
typedef K::Segment_2  Segment;


typedef CGAL::Alpha_shape_vertex_base_2<K> Vb;
typedef CGAL::Alpha_shape_face_base_2<K>  Fb;
typedef CGAL::Triangulation_data_structure_2<Vb,Fb> Tds;
typedef CGAL::Delaunay_triangulation_2<K,Tds> Triangulation_2;

typedef CGAL::Alpha_shape_2<Triangulation_2>  Alpha_shape_2;

typedef Alpha_shape_2::Face  Face;
typedef Alpha_shape_2::Vertex Vertex;
typedef Alpha_shape_2::Edge Edge;
typedef Alpha_shape_2::Face_handle  Face_handle;
typedef Alpha_shape_2::Vertex_handle Vertex_handle;

typedef Alpha_shape_2::Face_circulator  Face_circulator;
typedef Alpha_shape_2::Vertex_circulator  Vertex_circulator;

typedef Alpha_shape_2::Locate_type Locate_type;

typedef Alpha_shape_2::Face_iterator  Face_iterator;
typedef Alpha_shape_2::Vertex_iterator  Vertex_iterator;
typedef Alpha_shape_2::Edge_iterator  Edge_iterator;
typedef Alpha_shape_2::Edge_circulator  Edge_circulator;

typedef Alpha_shape_2::Alpha_iterator Alpha_iterator;
typedef Alpha_shape_2::Alpha_shape_edges_iterator Alpha_shape_edges_iterator;

//---------------------------------------------------------------------

template <class OutputIterator>
void
alpha_edges( const Alpha_shape_2&  A,
             OutputIterator out)
{

  for(Alpha_shape_edges_iterator it =  A.alpha_shape_edges_begin();
      it != A.alpha_shape_edges_end();
      ++it)
  {
    *out++ = A.segment(*it);
  }
}

template <class OutputIterator>
bool
file_input(OutputIterator out)
{
  std::ifstream is("./fin", std::ios::in);

  if(is.fail()){
    std::cerr << "unable to open file for input" << std::endl;
    return false;
  }

  int n;
  is >> n;
  std::cout << "Reading " << n << " points from file" << std::endl;
  CGAL::copy_n(std::istream_iterator<Point>(is), n, out);

  return true;
}

//------------------ main -------------------------------------------

int main()
{
  std::list<Point> points;
  if(! file_input(std::back_inserter(points)))
  {
    return -1;
  }

  Alpha_shape_2 A(points.begin(), points.end(),
                  FT(50),
                  Alpha_shape_2::GENERAL);
  //std::cout << "Alpha Shape computed" << std::endl;
  //Alpha_iterator optAlpha = A.find_optimal_alpha(1);
  //std::cout << "Optimal alpha: " << *optAlpha<<std::endl;
  //A.set_alpha(*optAlpha);
  //std::cout<<"Nb of solid components: 
"<<A.number_of_solid_components()<<std::endl;
  std::vector<Segment> segments;
  alpha_edges( A, std::back_inserter(segments));
  //
  //Print segments:
  std::vector<Segment>::iterator itPrint = segments.begin();
  while (itPrint!=segments.end())
  {
      std::cout<<*itPrint<<std::endl;
      itPrint++;
  }
  //
  return 0;
}