- Author
- Vincent Rouvreau
Definition
Alpha_complex is a simplicial complex constructed from the finite cells of a Delaunay Triangulation.
The filtration value of each simplex is computed as the square of the circumradius of the simplex if the circumsphere is empty (the simplex is then said to be Gabriel), and as the minimum of the filtration values of the codimension 1 cofaces that make it not Gabriel otherwise.
All simplices that have a filtration value strictly greater than a given alpha squared value are not inserted into the complex.
Alpha-complex representation
Alpha_complex is constructing a Simplex_tree using Delaunay Triangulation [11] from CGAL (the Computational Geometry Algorithms Library [17]).
The complex is a template class requiring an Epick_d dD Geometry Kernel [16] from CGAL as template parameter.
Example from points
This example builds the Delaunay triangulation from the given points in a 2D static kernel, and initializes the alpha complex with it.
Then, it is asked to display information about the alpha complex.
#include <CGAL/Epick_d.h>
#include <gudhi/Alpha_complex.h>
#include <iostream>
#include <string>
#include <vector>
#include <limits>
typedef CGAL::Epick_d< CGAL::Dimension_tag<2> > Kernel;
typedef Kernel::Point_d Point;
typedef std::vector<Point> Vector_of_points;
void usage(int nbArgs, char * const progName) {
std::cerr << "Error: Number of arguments (" << nbArgs << ") is not correct\n";
std::cerr << "Usage: " << progName << " [alpha_square_max_value]\n";
std::cerr << " i.e.: " << progName << " 60.0\n";
exit(-1);
}
int main(int argc, char **argv) {
if ((argc != 1) && (argc != 2)) usage(argc, (argv[0] - 1));
double alpha_square_max_value = std::numeric_limits<double>::infinity();
if (argc == 2)
alpha_square_max_value = atof(argv[1]);
Vector_of_points points;
points.push_back(Point(1.0, 1.0));
points.push_back(Point(7.0, 0.0));
points.push_back(Point(4.0, 6.0));
points.push_back(Point(9.0, 6.0));
points.push_back(Point(0.0, 14.0));
points.push_back(Point(2.0, 19.0));
points.push_back(Point(9.0, 17.0));
std::cout << "Alpha complex is of dimension " << alpha_complex_from_points.dimension() <<
" - " << alpha_complex_from_points.num_simplices() << " simplices - " <<
alpha_complex_from_points.num_vertices() << " vertices." << std::endl;
std::cout << "Iterator on alpha complex simplices in the filtration order, with [filtration value]:" << std::endl;
for (auto f_simplex : alpha_complex_from_points.filtration_simplex_range()) {
std::cout << " ( ";
for (auto vertex : alpha_complex_from_points.simplex_vertex_range(f_simplex)) {
std::cout << vertex << " ";
}
std::cout << ") -> " << "[" << alpha_complex_from_points.filtration(f_simplex) << "] ";
std::cout << std::endl;
}
return 0;
}
When launching:
the program output is:
Alpha complex is of dimension 2 - 25 simplices - 7 vertices.
Iterator on alpha complex simplices in the filtration order, with [filtration value]:
( 0 ) -> [0]
( 1 ) -> [0]
( 2 ) -> [0]
( 3 ) -> [0]
( 4 ) -> [0]
( 5 ) -> [0]
( 6 ) -> [0]
( 3 2 ) -> [6.25]
( 5 4 ) -> [7.25]
( 2 0 ) -> [8.5]
( 1 0 ) -> [9.25]
( 3 1 ) -> [10]
( 2 1 ) -> [11.25]
( 3 2 1 ) -> [12.5]
( 2 1 0 ) -> [12.9959]
( 6 5 ) -> [13.25]
( 4 2 ) -> [20]
( 6 4 ) -> [22.7367]
( 6 5 4 ) -> [22.7367]
( 6 3 ) -> [30.25]
( 6 2 ) -> [36.5]
( 6 3 2 ) -> [36.5]
( 6 4 2 ) -> [37.2449]
( 4 0 ) -> [59.7107]
( 4 2 0 ) -> [59.7107]
Algorithm
Data structure.
In order to build the alpha complex, first, a Simplex tree is built from the cells of a Delaunay Triangulation. (The filtration value is set to NaN, which stands for unknown value):
Simplex tree structure construction example
Filtration value computation algorithm
Dimension 2
From the example above, it means the algorithm looks into each triangle ([0,1,2], [0,2,4], [1,2,3], ...), computes the filtration value of the triangle, and then propagates the filtration value as described here :
Filtration value propagation example
Dimension 1
Then, the algorithm looks into each edge ([0,1], [0,2], [1,2], ...), computes the filtration value of the edge (in this case, propagation will have no effect).
Dimension 0
Finally, the algorithm looks into each vertex ([0], [1], [2], [3], [4], [5] and [6]) and sets the filtration value (0 in case of a vertex - propagation will have no effect).
Non decreasing filtration values
As the squared radii computed by CGAL are an approximation, it might happen that these alpha squared values do not quite define a proper filtration (i.e. non-decreasing with respect to inclusion). We fix that up by calling Simplex_tree::make_filtration_non_decreasing().
Prune above given filtration value
The simplex tree is pruned from the given maximum alpha squared value (cf. Simplex_tree::prune_above_filtration()). In the following example, the value is given by the user as argument of the program.
Example from OFF file
This example builds the Delaunay triangulation in a dynamic kernel, and initializes the alpha complex with it.
Then, it is asked to display information about the alpha complex.
#include <gudhi/Alpha_complex.h>
#include <CGAL/Epick_d.h>
#include <iostream>
#include <string>
void usage(int nbArgs, char * const progName) {
std::cerr << "Error: Number of arguments (" << nbArgs << ") is not correct\n";
std::cerr << "Usage: " << progName << " filename.off alpha_square_max_value [ouput_file.txt]\n";
std::cerr << " i.e.: " << progName << " ../../data/points/alphacomplexdoc.off 60.0\n";
exit(-1);
}
int main(int argc, char **argv) {
if ((argc != 3) && (argc != 4)) usage(argc, (argv[0] - 1));
std::string off_file_name(argv[1]);
double alpha_square_max_value = atof(argv[2]);
typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > Kernel;
std::streambuf* streambufffer;
std::ofstream ouput_file_stream;
if (argc == 4) {
ouput_file_stream.open(std::string(argv[3]));
streambufffer = ouput_file_stream.rdbuf();
} else {
streambufffer = std::cout.rdbuf();
}
std::ostream output_stream(streambufffer);
output_stream << "Alpha complex is of dimension " << alpha_complex_from_file.dimension() <<
" - " << alpha_complex_from_file.num_simplices() << " simplices - " <<
alpha_complex_from_file.num_vertices() << " vertices." << std::endl;
output_stream << "Iterator on alpha complex simplices in the filtration order, with [filtration value]:" << std::endl;
for (auto f_simplex : alpha_complex_from_file.filtration_simplex_range()) {
output_stream << " ( ";
for (auto vertex : alpha_complex_from_file.simplex_vertex_range(f_simplex)) {
output_stream << vertex << " ";
}
output_stream << ") -> " << "[" << alpha_complex_from_file.filtration(f_simplex) << "] ";
output_stream << std::endl;
}
ouput_file_stream.close();
return 0;
}
When launching:
$> ./alphaoffreader ../../data/points/alphacomplexdoc.off 32.0
the program output is:
Alpha complex is of dimension 2 - 20 simplices - 7 vertices.
Iterator on alpha complex simplices in the filtration order, with [filtration value]:
( 0 ) -> [0]
( 1 ) -> [0]
( 2 ) -> [0]
( 3 ) -> [0]
( 4 ) -> [0]
( 5 ) -> [0]
( 6 ) -> [0]
( 3 2 ) -> [6.25]
( 5 4 ) -> [7.25]
( 2 0 ) -> [8.5]
( 1 0 ) -> [9.25]
( 3 1 ) -> [10]
( 2 1 ) -> [11.25]
( 3 2 1 ) -> [12.5]
( 2 1 0 ) -> [12.9959]
( 6 5 ) -> [13.25]
( 4 2 ) -> [20]
( 6 4 ) -> [22.7367]
( 6 5 4 ) -> [22.7367]
( 6 3 ) -> [30.25]
- Copyright
- GNU General Public License v3.
Contact: gudhi-users@lists.gforge.inria.fr
1.8.6