Skip to Content.
Sympa Menu

cgal-discuss - [cgal-discuss] New bug in Alpha_shape_2 computation ?

Subject: CGAL users discussion list

List archive

[cgal-discuss] New bug in Alpha_shape_2 computation ?


Chronological Thread 
  • From: Benoît Presles <>
  • To:
  • Subject: [cgal-discuss] New bug in Alpha_shape_2 computation ?
  • Date: Wed, 25 Aug 2010 17:27:03 +0200

Hello Everybody,

I think a new bug could be present in the "Alpha_shape_2" class (the problem can be reproduced by using the list of points "fin" attached in this email).

First, I compute the alpha shape (GENERAL MODE).
Second, I print the segments which belongs to the alpha shape.
Third, I print the points which belongs to the alpha shape (Alpha_shape_vertices_iterator).

The problem is that I get too many points printed, for example the point (60,50) doesn't belong to the alpha shape but is printed.

Output of the program:
Reading 11 points from file
Alpha Shape computed
7 alpha shape edges
7 0 4 4
4 4 1 0
0 0 1 0
1 0 2.5 0
2.5 0 4.5 0
4.5 0 7 0
16 16 20 20
as_it=4.5 0
as_it=2.5 0
as_it=4 4
as_it=7 0
as_it=1 0
as_it=0 0
as_it=8 12
as_it=16 16
as_it=20 20
as_it=40 40
as_it=60 50
11
0 0
1 0
2.5 0
4.5 0
7 0
4 4
16 16
20 20
8 12
60 50
40 40

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

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;
//
typedef Alpha_shape_2::Alpha_shape_vertices_iterator
Alpha_shape_vertices_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(10),
Alpha_shape_2::GENERAL);

std::vector<Segment> segments;
alpha_edges( A, std::back_inserter(segments));

std::cout << "Alpha Shape computed" << std::endl;
std::cout << segments.size() << " alpha shape edges" << std::endl;
//std::cout << "Optimal alpha: " << *A.find_optimal_alpha(1)<<std::endl;
//Print segments:
std::vector<Segment>::iterator itPrint = segments.begin();
while (itPrint!=segments.end())
{
std::cout<<*itPrint<<std::endl;
itPrint++;
}
//Print vertices:
Alpha_shape_vertices_iterator as_it = A.alpha_shape_vertices_begin();
while(as_it != A.alpha_shape_vertices_end())
{
std::cout<<"as_it="<<(*as_it)->point()<<std::endl;
as_it++;
}
return 0;
}



Archive powered by MHonArc 2.6.16.

Top of Page