CGAL users discussion list

["Eitan Yaffe" <>]

Dear CGAL users,

I've ran into some problems while using the Alpha_shape_2 class in its non-weighted form.  In my problem I have a set of circles with a radius of 1. My purpose is to easily distinguish the edges that are part of the alpha-complex using this method.
I get strange results (seems like errors to me) when classifying the edges of the alpha shape triangulation.

In the attached file (and below) you can see an example with 3 points : (0,0), (4,0), (0,4). I've set the alpha value to 1, hoping to discover that all edges are external (since the 3 circles are disjoint). Instead I get one interior and two exterior edges. Below is an extract from the attached file. This is, of course, a simplified example: I got similar results for multiple circles.

BTW The alpha shape edges (returned from alpha_shape_edges_begin/end()) works fine, only the classification fails.

I hope I'm doing something wrong (which means a quick remedy to my problem), thanks for you help,

Eitan Yaffe,
MSc. student, CGAL group at Tel-Aviv University

-------------------------------------------------------------------------

typedef CGAL::Quotient<CGAL::MP_Float> NT;
typedef CGAL::Cartesian<NT>   K;
typedef K::Point_2                     Point_2;

// Alpha Shape
typedef CGAL::Alpha_shape_vertex_base_2<K> Av;
typedef CGAL::Triangulation_face_base_2<K> Tf;
typedef CGAL::Alpha_shape_face_base_2<K,Tf> Af;
typedef CGAL::Triangulation_default_data_structure_2<K,Av,Af> Tds;
typedef CGAL::Delaunay_triangulation_2<K,Tds> Dt;
typedef CGAL::Alpha_shape_2<Dt> Alpha_shape_2;
typedef Alpha_shape_2::Alpha_iterator Alpha_iterator_2;
typedef Alpha_shape_2::Alpha_shape_edges_iterator Alpha_shape_edges_iterator_2;

int main(int argc, char **argv)
{

    vector < Point_2 > points;
    points.push_back(Point_2(0, 0));
    points.push_back

(Point_2(4, 0));
    points.push_back(Point_2(0, 4));
    
    const NT alpha_value = 1;

    // construct alpha shape
    Alpha_shape_2 alpha_shape(points.begin(), points.end(),
                              alpha_value,
                              Alpha_shape_2::GENERAL);

    // print alpha values
    for (int i = 0; i < alpha_shape.number_of_alphas(); ++i)
        cout << i << " : " << alpha_shape.get_nth_alpha(i) << endl;

    // classify edges
    for (Alpha_shape_2::Edge_iterator eit = alpha_shape.finite_edges_begin();
         eit != alpha_shape.finite_edges_end(); ++eit)
    {
        Alpha_shape_2::Edge edge = *eit;
        cout << "classify result: " << classify_to_string(alpha_shape.classify(edge)) << endl;
    }

    return 0;
}


/* 
   alpha_problem.C

   Problem in non-weighted alpha shape classification
*/

#include <CGAL/Delaunay_triangulation_2.h>
#include <CGAL/Alpha_shape_2.h>
#include <CGAL/MP_Float.h>
#include <CGAL/Quotient.h>
#include <CGAL/Cartesian.h>

typedef CGAL::Quotient<CGAL::MP_Float> NT;
typedef CGAL::Cartesian<NT>   K;
typedef K::Point_2                     Point_2;

// Alpha Shape
typedef CGAL::Alpha_shape_vertex_base_2<K> Av;
typedef CGAL::Triangulation_face_base_2<K> Tf;
typedef CGAL::Alpha_shape_face_base_2<K,Tf> Af;
typedef CGAL::Triangulation_default_data_structure_2<K,Av,Af> Tds;
typedef CGAL::Delaunay_triangulation_2<K,Tds> Dt;
typedef CGAL::Alpha_shape_2<Dt> Alpha_shape_2;
typedef Alpha_shape_2::Alpha_iterator Alpha_iterator_2;
typedef Alpha_shape_2::Alpha_shape_edges_iterator Alpha_shape_edges_iterator_2;

using namespace std;

string classify_to_string(Alpha_shape_2::Classification_type type)
{
    switch (type)
    {
    case Alpha_shape_2::EXTERIOR: return "EXTERIOR";
    case Alpha_shape_2::SINGULAR: return "SINGULAR";
    case Alpha_shape_2::REGULAR: return "REGULAR";
    case Alpha_shape_2::INTERIOR: return "INTERIOR";
    default: return "unknown";
    }
}

int main(int argc, char **argv)
{

    vector < Point_2 > points;
    points.push_back(Point_2(0, 0));
    points.push_back(Point_2(4, 0));
    points.push_back(Point_2(0, 4));
    
    const NT alpha_value = 1;

    // construct alpha shape
    Alpha_shape_2 alpha_shape(points.begin(), points.end(),
                              alpha_value,
                              Alpha_shape_2::GENERAL);

    // print alpha values
    for (int i = 0; i < alpha_shape.number_of_alphas(); ++i)
        cout << i << " : " << alpha_shape.get_nth_alpha(i) << endl;

    // classify edges
    for (Alpha_shape_2::Edge_iterator eit = alpha_shape.finite_edges_begin();
         eit != alpha_shape.finite_edges_end(); ++eit)
    {
        Alpha_shape_2::Edge edge = *eit;
        cout << "classify result: " << classify_to_string(alpha_shape.classify(edge)) << endl;
    }

    return 0;
}