CGAL users discussion list

[Benoît Presles <>]

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).


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).


Thank you very much for your help,
Best Regards,
Benoît
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
/***********************************************************************

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_2;
typedef K::Segment_2  Segment_2;


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;

//---------------------------------------------------------------------
//
void alpha_all_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;
}
//
void alpha_all_vertices(const Alpha_shape_2&  A,std::vector<Point_2> &points)
{
  int r=0,s=0,i=0,e=0;
  for(std::vector<Point_2>::iterator it =  points.begin();it != 
points.end();++it)
  {
    //std::cout << "*it "<<*it<<std::endl;
    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;
}
//
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.txt", 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_2>(is), n, out);

  return true;
}

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

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

  Alpha_shape_2 A(points.begin(), points.end(),
                  FT(10000),
                  Alpha_shape_2::GENERAL);
  //
  Alpha_iterator alpha_it = A.alpha_begin();
  A.set_alpha(*alpha_it);
  //
  std::vector<Segment_2> segments;
  alpha_edges( A, std::back_inserter(segments));

  std::cout << "Alpha Shape computed" << std::endl;
  std::cout << segments.size() << " alpha shape edges" << std::endl;
  //DEBUG
  std::cout<<"--OUT--"<<std::endl;
  std::vector<Segment_2>::iterator it_seg = segments.begin();
  while(it_seg != segments.end())
  {
      std::cout<<(*it_seg)<<std::endl;
      it_seg++;
  }
  //FIN DEBUG
  alpha_all_vertices(A,points);
  alpha_all_edges(A);
  return 0;
}


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

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_2;
typedef K::Segment_2  Segment_2;


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;

//---------------------------------------------------------------------
//
void alpha_all_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;
}
//
void alpha_all_vertices(const Alpha_shape_2&  A,std::vector<Point_2> &points)
{
  int r=0,s=0,i=0,e=0;
  for(std::vector<Point_2>::iterator it =  points.begin();it != 
points.end();++it)
  {
    //std::cout << "*it "<<*it<<std::endl;
    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;
}
//
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.txt", 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_2>(is), n, out);

  return true;
}

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

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

  Alpha_shape_2 A(points.begin(), points.end(),
                  FT(10000),
                  Alpha_shape_2::GENERAL);
  //
  Alpha_iterator alpha_it = A.alpha_begin();
  A.set_alpha(*(alpha_it+9));
  //
  std::vector<Segment_2> segments;
  alpha_edges( A, std::back_inserter(segments));

  std::cout << "Alpha Shape computed" << std::endl;
  std::cout << segments.size() << " alpha shape edges" << std::endl;
  //DEBUG
  std::cout<<"--OUT--"<<std::endl;
  std::vector<Segment_2>::iterator it_seg = segments.begin();
  while(it_seg != segments.end())
  {
      std::cout<<(*it_seg)<<std::endl;
      it_seg++;
  }
  //FIN DEBUG
  alpha_all_vertices(A,points);
  alpha_all_edges(A);
  return 0;
}

Attachment: alphaShapeSegments_1.png
Description: PNG image

Attachment: alphaShapeSegments_2.png
Description: PNG image

Attachment: Delaunay.png
Description: PNG image

10
5.6000861e-01   7.8025025e-01
6.9996984e-01   4.0478872e-01
3.2409775e-01   4.1351351e-02
4.8492261e-01   4.5119464e-02
4.0724158e-01   7.7407523e-01
8.8444597e-01   6.4126785e-01
7.2714145e-01   6.5805292e-01
8.4817671e-01   5.9093100e-01
1.8816486e-01   1.7154302e-01
6.0477158e-01   3.4577464e-01
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