Alphashapes and Python bindings dev
authorDmitriy Morozov <dmitriy@mrzv.org>
Thu, 16 Apr 2009 00:23:01 -0700
branchdev
changeset 131 d9e050258358
parent 130 580eaa850c4f
child 132 2a737609b8bf
Alphashapes and Python bindings * converted alphashapes2d to the new format * added Python bindings for alphashapes * added sample alphashapes.py that dynamically distinguishes between 2D and 3D
bindings/python/CMakeLists.txt
bindings/python/alphashapes2d.cpp
bindings/python/alphashapes3d.cpp
bindings/python/dionysus.cpp
examples/alphashapes/CMakeLists.txt
examples/alphashapes/alphashapes.py
examples/alphashapes/alphashapes2d.cpp
examples/alphashapes/alphashapes2d.h
examples/alphashapes/alphashapes2d.hpp
examples/alphashapes/alphashapes3d.cpp
examples/alphashapes/alphashapes3d.h
examples/alphashapes/alphashapes3d.hpp
--- a/bindings/python/CMakeLists.txt	Wed Apr 15 14:17:21 2009 -0700
+++ b/bindings/python/CMakeLists.txt	Thu Apr 16 00:23:01 2009 -0700
@@ -5,7 +5,7 @@
 
 # currently can't build bindings with counters support, eventually FIXME
 remove_definitions          (-DCOUNTERS)
-add_library                 (_dionysus SHARED 
+set                         (sources
                                                 dionysus.cpp 
                                                 filtration.cpp
                                                 chain.cpp
@@ -14,12 +14,30 @@
                                                 zigzag-persistence.cpp
                                                 rips.cpp
                             )
-target_link_libraries       (_dionysus ${libraries})
+set                         (bindings_libraries ${libraries})
+
+if                          (CGAL_FOUND)
+    set                     (sources            ${sources}
+                                                alphashapes3d.cpp
+                                                alphashapes2d.cpp)
+    add_definitions         (${CGAL_CXX_FLAGS_INIT})
+    include_directories     (${CGAL_INCLUDE_DIRS})
+
+    link_libraries          (${CGAL_LIBRARY})                                            
+else                            (CGAL_FOUND)
+    message(STATUS "CGAL not found, alphashape bindings will not be built")
+endif                       (CGAL_FOUND)
+
+add_library                 (_dionysus SHARED   ${sources})
+target_link_libraries       (_dionysus          ${libraries})
 
 
+# Python files and the symlink
 add_custom_target           (dionysus ALL
                              ${CMAKE_COMMAND} -E copy_directory ${CMAKE_CURRENT_SOURCE_DIR}/dionysus ${CMAKE_CURRENT_BINARY_DIR}/dionysus
-                             DEPENDS dionysus/__init__.py)
+                             DEPENDS            dionysus/__init__.py
+                                                dionysus/distances.py
+                            )
 
 get_target_property         (_dionysus_location _dionysus LOCATION)
 add_custom_target           (dionysus-link ALL 
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/bindings/python/alphashapes2d.cpp	Thu Apr 16 00:23:01 2009 -0700
@@ -0,0 +1,45 @@
+// Wrap includes into namespaces to avoid nameclashes
+#include "../../examples/alphashapes/alphashapes2d.h" 
+
+#include <boost/python.hpp>
+#include <boost/python/stl_iterator.hpp>
+namespace bp = boost::python;
+
+#include "simplex.h"                // defines SimplexVD, Vertex, and Data
+namespace dp = dionysus::python;
+
+
+void fill_alpha2D_complex(bp::object points, bp::list complex)
+{
+    typedef     std::map<AlphaSimplex2D::Vertex, unsigned>      ASPointMap;
+
+    Delaunay2D  Dt;
+    ASPointMap  point_map;
+    unsigned i = 0;
+    for (bp::stl_input_iterator<bp::list> pt = points; pt != bp::stl_input_iterator<bp::list>(); ++pt)
+    {
+        double x = bp::extract<double>((*pt)[0]);
+        double y = bp::extract<double>((*pt)[1]);
+        point_map[Dt.insert(Point(x,y))] = i++;
+    }
+
+    AlphaSimplex2D::SimplexSet simplices;
+    fill_simplex_set(Dt, simplices);
+
+    for (AlphaSimplex2D::SimplexSet::const_iterator cur = simplices.begin(); cur != simplices.end(); ++cur)
+    {
+        dp::SimplexVD s;
+        for (AlphaSimplex2D::VertexContainer::const_iterator vcur  = cur->vertices().begin(); 
+                                                             vcur != cur->vertices().end(); ++vcur)
+            s.add(point_map[*vcur]);
+
+        complex.append(s);
+        complex[-1].attr("data") = cur->value();
+        complex[-1].attr("attached") = cur->attached();
+    }
+}
+
+void export_alphashapes2d()
+{
+    bp::def("fill_alpha2D_complex",       &fill_alpha2D_complex);
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/bindings/python/alphashapes3d.cpp	Thu Apr 16 00:23:01 2009 -0700
@@ -0,0 +1,46 @@
+// Wrap includes into namespaces to avoid nameclashes
+#include "../../examples/alphashapes/alphashapes3d.h" 
+
+#include <boost/python.hpp>
+#include <boost/python/stl_iterator.hpp>
+namespace bp = boost::python;
+
+#include "simplex.h"                // defines SimplexVD, Vertex, and Data
+namespace dp = dionysus::python;
+
+
+void fill_alpha3D_complex(bp::object points, bp::list complex)
+{
+    typedef     std::map<AlphaSimplex3D::Vertex, unsigned>      ASPointMap;
+
+    Delaunay3D  Dt;
+    ASPointMap  point_map;
+    unsigned i = 0;
+    for (bp::stl_input_iterator<bp::list> pt = points; pt != bp::stl_input_iterator<bp::list>(); ++pt)
+    {
+        double x = bp::extract<double>((*pt)[0]);
+        double y = bp::extract<double>((*pt)[1]);
+        double z = bp::extract<double>((*pt)[2]);
+        point_map[Dt.insert(Point(x,y,z))] = i++;
+    }
+
+    AlphaSimplex3D::SimplexSet simplices;
+    fill_simplex_set(Dt, simplices);
+
+    for (AlphaSimplex3D::SimplexSet::const_iterator cur = simplices.begin(); cur != simplices.end(); ++cur)
+    {
+        dp::SimplexVD s;
+        for (AlphaSimplex3D::VertexContainer::const_iterator vcur  = cur->vertices().begin(); 
+                                                             vcur != cur->vertices().end(); ++vcur)
+            s.add(point_map[*vcur]);
+
+        complex.append(s);
+        complex[-1].attr("data") = cur->value();
+        complex[-1].attr("attached") = cur->attached();
+    }
+}
+
+void export_alphashapes3d()
+{
+    bp::def("fill_alpha3D_complex",       &fill_alpha3D_complex);
+}
--- a/bindings/python/dionysus.cpp	Wed Apr 15 14:17:21 2009 -0700
+++ b/bindings/python/dionysus.cpp	Thu Apr 16 00:23:01 2009 -0700
@@ -10,6 +10,8 @@
 void export_zigzag_persistence();
 
 void export_rips();
+void export_alphashapes2d();
+void export_alphashapes3d();
 
 #ifdef LOGGING
 void            enable_log(std::string s)
@@ -28,6 +30,8 @@
     export_zigzag_persistence();
 
     export_rips();
+    export_alphashapes2d();
+    export_alphashapes3d();
 
 #ifdef LOGGING
     bp::def("enable_log",           &enable_log);
--- a/examples/alphashapes/CMakeLists.txt	Wed Apr 15 14:17:21 2009 -0700
+++ b/examples/alphashapes/CMakeLists.txt	Thu Apr 16 00:23:01 2009 -0700
@@ -9,7 +9,7 @@
 # Add targets that depend on CGAL
 if                              (CGAL_FOUND)
     set                         (targets                        alphashapes3d
-                                                                #alphashapes2d
+                                                                alphashapes2d
                                                                 #alpharadius
                                 )
     add_definitions             (${CGAL_CXX_FLAGS_INIT})
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/examples/alphashapes/alphashapes.py	Thu Apr 16 00:23:01 2009 -0700
@@ -0,0 +1,42 @@
+# Computes the persistence diagram of the alpha shapes in both 2D and 3D 
+# (decided dynamically based on the input file)
+
+from    dionysus        import Filtration, StaticPersistence, data_dim_cmp, vertex_cmp, \
+                               fill_alpha3D_complex, fill_alpha2D_complex, points_file
+from    sys             import argv, exit
+from    math            import sqrt
+
+
+if len(argv) < 2:
+    print "Usage: %s POINTS" % argv[0]
+    exit()
+
+points = [p for p in points_file(argv[1])]
+simplices = []
+if   len(points[0]) == 2:           # 2D
+    fill_alpha2D_complex(points, simplices)
+elif len(points[1]) == 3:           # 3D
+    fill_alpha3D_complex(points, simplices)
+
+simplices.sort(vertex_cmp)                      # Must ensure lexicographic ordering
+print "Total number of simplices:", len(simplices)
+
+f = Filtration(simplices, data_dim_cmp)
+print "Filtration initialized"
+
+p = StaticPersistence(f)
+print "StaticPersistence initialized" 
+
+p.pair_simplices()
+print "Simplices paired"
+
+print "Outputting persistence diagram"
+for i in p:
+    if i.sign():
+        b = simplices[f[p(i)]]
+        if i == i.pair:
+            print b.dimension(), sqrt(b.data), "inf"
+            continue
+
+        d = simplices[f[p(i.pair)]]
+        print b.dimension(), sqrt(b.data), sqrt(d.data)
--- a/examples/alphashapes/alphashapes2d.cpp	Wed Apr 15 14:17:21 2009 -0700
+++ b/examples/alphashapes/alphashapes2d.cpp	Thu Apr 16 00:23:01 2009 -0700
@@ -2,58 +2,69 @@
 
 #include "alphashapes2d.h"
 #include <topology/filtration.h>
+#include <topology/static-persistence.h>
+#include <topology/persistence-diagram.h>
 #include <iostream>
+
 #include <fstream>
 
 
-typedef Filtration<AlphaSimplex2D>				AlphaFiltration;
+typedef Filtration<AlphaSimplex2DVector>        AlphaFiltration;
+typedef StaticPersistence<>                     Persistence;
+typedef PersistenceDiagram<>                    PDgm;
+
 
 int main(int argc, char** argv) 
 {
 #ifdef LOGGING
-	rlog::RLogInit(argc, argv);
+    rlog::RLogInit(argc, argv);
 
-	stdoutLog.subscribeTo( RLOG_CHANNEL("error") );
-	stdoutLog.subscribeTo( RLOG_CHANNEL("info") );
-	//stdoutLog.subscribeTo( RLOG_CHANNEL("topology/filtration") );
-	//stdoutLog.subscribeTo( RLOG_CHANNEL("topology/cycle") );
+    stdoutLog.subscribeTo( RLOG_CHANNEL("error") );
+    stdoutLog.subscribeTo( RLOG_CHANNEL("info") );
+    //stdoutLog.subscribeTo( RLOG_CHANNEL("topology/filtration") );
+    //stdoutLog.subscribeTo( RLOG_CHANNEL("topology/cycle") );
 #endif
 
-	SetFrequency(GetCounter("filtration/pair"), 10000);
-	SetTrigger(GetCounter("filtration/pair"), GetCounter(""));
+    SetFrequency(GetCounter("filtration/pair"), 10000);
+    SetTrigger(GetCounter("filtration/pair"), GetCounter(""));
 
-	// Read in the point set and compute its Delaunay triangulation
-	std::istream& in = std::cin;
-	double x,y;
-	Delaunay Dt;
-	while(in)
-	{
-		in >> x >> y;
-		Point p(x,y);
-		Dt.insert(p);
-	}
-	rInfo("Delaunay triangulation computed");
+    // Read in the point set and compute its Delaunay triangulation
+    std::istream& in = std::cin;
+    double x,y;
+    Delaunay2D Dt;
+    while(in)
+    {
+        in >> x >> y;
+        if (!in) break;
+        Point p(x,y);
+        Dt.insert(p);
+    }
+    rInfo("Delaunay triangulation computed");
    
-	AlphaSimplex2DVector alpha_ordering;
-	fill_alpha_order(Dt, alpha_ordering);
-	rInfo("Simplices: %i", alpha_ordering.size());
+    AlphaSimplex2DVector complex;
+    fill_complex(Dt, complex);
+    rInfo("Simplices: %i", complex.size());
+
+    // Create the alpha-shape filtration
+    AlphaFiltration af(complex.begin(), complex.end(), AlphaSimplex2D::AlphaOrder());
+    rInfo("Filtration initialized");
+
+    Persistence p(af);
+    rInfo("Persistence initializaed");
 
-	// Create the alpha-shape filtration
-	AlphaFiltration af;
-	for (AlphaSimplex2DVector::const_iterator cur = alpha_ordering.begin(); 
-											  cur != alpha_ordering.end(); ++cur)
-		af.append(*cur);
-	af.fill_simplex_index_map();
-	rInfo("Filled simplex-index map");
-	af.pair_simplices(af.begin(), af.end(), false);
-	rInfo("Simplices paired");
+    p.pair_simplices();
+    rInfo("Simplices paired");
 
-	for (AlphaFiltration::Index i = af.begin(); i != af.end(); ++i)
-		if (i->is_paired())
-		{
-			if (i->sign())
-				std::cout << i->dimension() << " " << i->value() << " " << i->pair()->value() << std::endl;
-		} //else std::cout << i->value() << std::endl;
+    std::map<Dimension, PDgm> dgms;
+    init_diagrams(dgms, p.begin(), p.end(), 
+                  evaluate_through_map(OffsetMap<Persistence::OrderIndex, AlphaFiltration::Index>(p.begin(), af.begin()), 
+                                       evaluate_through_filtration(af, AlphaSimplex2D::AlphaValueEvaluator())), 
+                  evaluate_through_map(OffsetMap<Persistence::OrderIndex, AlphaFiltration::Index>(p.begin(), af.begin()), 
+                                       evaluate_through_filtration(af, AlphaSimplex2D::DimensionExtractor())));
 
+#if 1
+    std::cout << 0 << std::endl << dgms[0] << std::endl;
+    std::cout << 1 << std::endl << dgms[1] << std::endl;
+#endif
 }
 
--- a/examples/alphashapes/alphashapes2d.h	Wed Apr 15 14:17:21 2009 -0700
+++ b/examples/alphashapes/alphashapes2d.h	Thu Apr 16 00:23:01 2009 -0700
@@ -18,62 +18,65 @@
 
 struct K: CGAL::Exact_predicates_exact_constructions_kernel {};
 
-typedef CGAL::Delaunay_triangulation_2<K>    		Delaunay;
-typedef Delaunay::Point                				Point;
-typedef Delaunay::Vertex            				Vertex;
-typedef Delaunay::Vertex_handle            			Vertex_handle;
-typedef Delaunay::Edge								Edge;
-typedef Delaunay::Face								Face;
-typedef Delaunay::Face_handle						Face_handle;
-typedef K::FT										RealValue;
+typedef CGAL::Delaunay_triangulation_2<K>           Delaunay2D;
+typedef Delaunay2D::Point                           Point;
+typedef Delaunay2D::Vertex_handle                   Vertex_handle;
+typedef Delaunay2D::Face_handle                     Face_handle;
+typedef K::FT                                       RealValue;
 
-typedef Delaunay::Finite_vertices_iterator    		Vertex_iterator;
-typedef Delaunay::Finite_edges_iterator        		Edge_iterator;
-typedef Delaunay::Finite_faces_iterator        		Face_iterator;
+typedef Delaunay2D::Finite_vertices_iterator        Vertex_iterator;
+typedef Delaunay2D::Finite_edges_iterator           Edge_iterator;
+typedef Delaunay2D::Finite_faces_iterator           Face_iterator;
 
 
-class AlphaSimplex2D: public SimplexWithVertices<Vertex_handle>
+class AlphaSimplex2D: public Simplex<Vertex_handle>
 {
-	public:
-		typedef 	std::set<AlphaSimplex2D>							SimplexSet;
-		typedef		SimplexWithVertices<Vertex_handle>					Parent;
-		typedef		Parent::VertexContainer								VertexSet;
-		typedef		std::list<AlphaSimplex2D>							Cycle;
+    public:
+        typedef     Simplex<Vertex_handle>                              Parent;
+        typedef     std::set<AlphaSimplex2D, Parent::VertexComparison>  SimplexSet;
+        typedef     Parent::VertexContainer                             VertexSet;
 
     public:
-									AlphaSimplex2D()					{}
-									AlphaSimplex2D(const Parent& p): 
-											Parent(p) 					{}
-									AlphaSimplex2D(const AlphaSimplex2D& s): 
-											Parent(s) 					{ attached_ = s.attached_; alpha_ = s.alpha_; }
-	    							AlphaSimplex2D(const ::Vertex& v);
-		
-								    AlphaSimplex2D(const Edge& e);
-								    AlphaSimplex2D(const Edge& e, const SimplexSet& simplices, const Delaunay& Dt);
-		
-									AlphaSimplex2D(const Face& c);
-	    
-		RealType					value() const						{ return CGAL::to_double(alpha_); }
-		RealValue					alpha() const						{ return alpha_; }
-		bool						attached() const					{ return attached_; }
-		Cycle						boundary() const;
+                                    AlphaSimplex2D()                    {}
+                                    AlphaSimplex2D(const Parent& p): 
+                                            Parent(p)                   {}
+                                    AlphaSimplex2D(const AlphaSimplex2D& s): 
+                                            Parent(s)                   { attached_ = s.attached_; alpha_ = s.alpha_; }
+                                    AlphaSimplex2D(const Delaunay2D::Vertex& v);
+        
+                                    AlphaSimplex2D(const Delaunay2D::Edge& e);
+                                    AlphaSimplex2D(const Delaunay2D::Edge& e, const SimplexSet& simplices, const Delaunay2D& Dt);
+        
+                                    AlphaSimplex2D(const Delaunay2D::Face& c);
+        
+        RealType                    value() const                       { return CGAL::to_double(alpha_); }
+        RealValue                   alpha() const                       { return alpha_; }
+        bool                        attached() const                    { return attached_; }
 
-		// Ordering
-		struct AlphaOrder
-		{ bool operator()(const AlphaSimplex2D& first, const AlphaSimplex2D& second) const; };
-		
-		std::ostream& 				operator<<(std::ostream& out) const;
-		
-	private:
-		RealValue 					alpha_;
-		bool 						attached_;
+        // Ordering
+        struct AlphaOrder
+        { bool operator()(const AlphaSimplex2D& first, const AlphaSimplex2D& second) const; };
+        
+        struct AlphaValueEvaluator
+        { 
+            typedef                 AlphaSimplex2D                                  first_argument_type;
+            typedef                 RealType                                        result_type;
+
+            RealType                operator()(const AlphaSimplex2D& s) const       { return s.value(); }
+        };
+
+        std::ostream&               operator<<(std::ostream& out) const;
+        
+    private:
+        RealValue                   alpha_;
+        bool                        attached_;
 };
 
-typedef 			std::vector<AlphaSimplex2D>								AlphaSimplex2DVector;
-void 				fill_alpha_order(const Delaunay& Dt, 
-									 AlphaSimplex2DVector& alpha_order);
+typedef             std::vector<AlphaSimplex2D>                             AlphaSimplex2DVector;
+void                fill_simplex_set(const Delaunay2D& Dt, AlphaSimplex2D::SimplexSet& simplices);
+void                fill_complex(const Delaunay2D& Dt,     AlphaSimplex2DVector& alpha_order);
 
-std::ostream& 		operator<<(std::ostream& out, const AlphaSimplex2D& s)	{ return s.operator<<(out); }
+std::ostream&       operator<<(std::ostream& out, const AlphaSimplex2D& s)  { return s.operator<<(out); }
 
 #include "alphashapes2d.hpp"
 
--- a/examples/alphashapes/alphashapes2d.hpp	Wed Apr 15 14:17:21 2009 -0700
+++ b/examples/alphashapes/alphashapes2d.hpp	Thu Apr 16 00:23:01 2009 -0700
@@ -1,5 +1,7 @@
+#include <utilities/log.h>
+
 AlphaSimplex2D::	    
-AlphaSimplex2D(const ::Vertex& v): alpha_(0), attached_(false)
+AlphaSimplex2D(const Delaunay2D::Vertex& v): alpha_(0), attached_(false)
 {
 	for (int i = 0; i < 3; ++i)
 		if (v.face()->vertex(i)->point() == v.point())
@@ -7,7 +9,7 @@
 }
 
 AlphaSimplex2D::	    
-AlphaSimplex2D(const Edge& e): attached_(false)
+AlphaSimplex2D(const Delaunay2D::Edge& e): attached_(false)
 {
     Face_handle f = e.first;
 	for (int i = 0; i < 3; ++i)
@@ -16,7 +18,7 @@
 }
 
 AlphaSimplex2D::	    
-AlphaSimplex2D(const Edge& e, const SimplexSet& simplices, const Delaunay& Dt): attached_(false)
+AlphaSimplex2D(const Delaunay2D::Edge& e, const SimplexSet& simplices, const Delaunay2D& Dt): attached_(false)
 {
     Face_handle f = e.first;
 	for (int i = 0; i < 3; ++i)
@@ -26,7 +28,7 @@
 	Face_handle o = f->neighbor(e.second);
 	int oi = o->index(f);
 
-	VertexSet::const_iterator v = Parent::vertices().begin();
+	VertexSet::const_iterator v = static_cast<const Parent*>(this)->vertices().begin();
 	const Point& p1 = (*v++)->point();
 	const Point& p2 = (*v)->point();
 	
@@ -55,27 +57,17 @@
 }
 
 AlphaSimplex2D::	    
-AlphaSimplex2D(const Face& f): attached_(false)
+AlphaSimplex2D(const Delaunay2D::Face& f): attached_(false)
 {
 	for (int i = 0; i < 3; ++i)
 		Parent::add(f.vertex(i));
-	VertexSet::const_iterator v = Parent::vertices().begin();
+	VertexSet::const_iterator v = static_cast<const Parent*>(this)->vertices().begin();
 	Point p1 = (*v++)->point();
 	Point p2 = (*v++)->point();
 	Point p3 = (*v)->point();
 	alpha_ = CGAL::squared_radius(p1, p2, p3);
 }
 
-AlphaSimplex2D::Cycle
-AlphaSimplex2D::boundary() const
-{
-	Cycle bdry;
-	Parent::Cycle pbdry = Parent::boundary();
-	for (Parent::Cycle::const_iterator cur = pbdry.begin(); cur != pbdry.end(); ++cur)
-		bdry.push_back(*cur);
-	return bdry;
-}
-
 
 bool 
 AlphaSimplex2D::AlphaOrder::
@@ -99,11 +91,8 @@
 	return out;
 }
 
-
-void fill_alpha_order(const Delaunay& Dt, AlphaSimplex2DVector& alpha_order)
+void fill_simplex_set(const Delaunay2D& Dt, AlphaSimplex2D::SimplexSet& simplices)
 {
-	// Compute all simplices with their alpha values and attachment information
-	AlphaSimplex2D::SimplexSet simplices;
 	for(Face_iterator cur = Dt.finite_faces_begin(); cur != Dt.finite_faces_end(); ++cur)
 		simplices.insert(AlphaSimplex2D(*cur));
 	rInfo("Faces inserted");
@@ -113,10 +102,18 @@
 	for(Vertex_iterator cur = Dt.finite_vertices_begin(); cur != Dt.finite_vertices_end(); ++cur)
 		simplices.insert(AlphaSimplex2D(*cur));
 	rInfo("Vertices inserted");
+}
+
+void fill_complex(const Delaunay2D& Dt, AlphaSimplex2DVector& alpha_order)
+{
+	// Compute all simplices with their alpha values and attachment information
+	AlphaSimplex2D::SimplexSet simplices;
+    fill_simplex_set(Dt, simplices);
     
 	// Sort simplices by their alpha values
 	alpha_order.resize(simplices.size());
 	std::copy(simplices.begin(), simplices.end(), alpha_order.begin());
-	std::sort(alpha_order.begin(), alpha_order.end(), AlphaSimplex2D::AlphaOrder());
+	// std::sort(alpha_order.begin(), alpha_order.end(), AlphaSimplex2D::AlphaOrder());
+	std::sort(alpha_order.begin(), alpha_order.end(), AlphaSimplex2D::VertexComparison());
 }
 
--- a/examples/alphashapes/alphashapes3d.cpp	Wed Apr 15 14:17:21 2009 -0700
+++ b/examples/alphashapes/alphashapes3d.cpp	Thu Apr 16 00:23:01 2009 -0700
@@ -62,7 +62,7 @@
     // Read in the point set and compute its Delaunay triangulation
     std::ifstream in(infilename.c_str());
     double x,y,z;
-    Delaunay Dt;
+    Delaunay3D Dt;
     while(in)
     {
         in >> x >> y >> z;
--- a/examples/alphashapes/alphashapes3d.h	Wed Apr 15 14:17:21 2009 -0700
+++ b/examples/alphashapes/alphashapes3d.h	Thu Apr 16 00:23:01 2009 -0700
@@ -18,18 +18,17 @@
 
 struct K: CGAL::Exact_predicates_exact_constructions_kernel {};
 
-typedef CGAL::Delaunay_triangulation_3<K>    		Delaunay;
-typedef Delaunay::Point                				Point;
-typedef Delaunay::Vertex            				Vertex;
-typedef Delaunay::Vertex_handle            			Vertex_handle;
-typedef Delaunay::Cell_handle						Cell_handle;
-typedef K::FT										RealValue;
+typedef CGAL::Delaunay_triangulation_3<K>           Delaunay3D;
+typedef Delaunay3D::Point                           Point;
+typedef Delaunay3D::Vertex_handle                   Vertex_handle;
+typedef Delaunay3D::Cell_handle                     Cell_handle;
+typedef K::FT                                       RealValue;
 
-typedef Delaunay::Finite_vertices_iterator    		Vertex_iterator;
-typedef Delaunay::Finite_edges_iterator        		Edge_iterator;
-typedef Delaunay::Finite_facets_iterator        	Facet_iterator;
-typedef Delaunay::Finite_cells_iterator        		Cell_iterator;
-typedef Delaunay::Facet_circulator					Facet_circulator;
+typedef Delaunay3D::Finite_vertices_iterator        Vertex_iterator;
+typedef Delaunay3D::Finite_edges_iterator           Edge_iterator;
+typedef Delaunay3D::Finite_facets_iterator          Facet_iterator;
+typedef Delaunay3D::Finite_cells_iterator           Cell_iterator;
+typedef Delaunay3D::Facet_circulator                Facet_circulator;
 
 
 class AlphaSimplex3D: public Simplex<Vertex_handle>
@@ -38,7 +37,6 @@
 		typedef		Simplex<Vertex_handle>					            Parent;
 		typedef 	std::set<AlphaSimplex3D, Parent::VertexComparison>  SimplexSet;
 		typedef		Parent::VertexContainer								VertexSet;
-		typedef		std::list<AlphaSimplex3D>							Boundary;
 
     public:
 									AlphaSimplex3D()					{}
@@ -46,15 +44,15 @@
 											Parent(p) 					{}
 									AlphaSimplex3D(const AlphaSimplex3D& s): 
 											Parent(s) 					{ attached_ = s.attached_; alpha_ = s.alpha_; }
-	    							AlphaSimplex3D(const ::Vertex& v);
+	    							AlphaSimplex3D(const Delaunay3D::Vertex& v);
 		
-								    AlphaSimplex3D(const Delaunay::Edge& e);
-								    AlphaSimplex3D(const Delaunay::Edge& e, const SimplexSet& simplices, const Delaunay& Dt, Facet_circulator facet_bg);
+								    AlphaSimplex3D(const Delaunay3D::Edge& e);
+								    AlphaSimplex3D(const Delaunay3D::Edge& e, const SimplexSet& simplices, const Delaunay3D& Dt, Facet_circulator facet_bg);
 		
-								    AlphaSimplex3D(const Delaunay::Facet& f);
-								    AlphaSimplex3D(const Delaunay::Facet& f, const SimplexSet& simplices, const Delaunay& Dt);
+								    AlphaSimplex3D(const Delaunay3D::Facet& f);
+								    AlphaSimplex3D(const Delaunay3D::Facet& f, const SimplexSet& simplices, const Delaunay3D& Dt);
 	    
-									AlphaSimplex3D(const Delaunay::Cell& c);
+									AlphaSimplex3D(const Delaunay3D::Cell& c);
 	    
 		RealType					value() const						{ return CGAL::to_double(alpha_); }
 		RealValue					alpha() const						{ return alpha_; }
@@ -80,8 +78,8 @@
 };
 
 typedef 			std::vector<AlphaSimplex3D>								AlphaSimplex3DVector;
-void 				fill_complex(const Delaunay& Dt, 
-								 AlphaSimplex3DVector& alpha_order);
+void 				fill_simplex_set(const Delaunay3D& Dt, AlphaSimplex3D::SimplexSet& simplices);
+void 				fill_complex(const Delaunay3D& Dt,     AlphaSimplex3DVector& alpha_order);
 
 std::ostream& 		operator<<(std::ostream& out, const AlphaSimplex3D& s)	{ return s.operator<<(out); }
 
--- a/examples/alphashapes/alphashapes3d.hpp	Wed Apr 15 14:17:21 2009 -0700
+++ b/examples/alphashapes/alphashapes3d.hpp	Thu Apr 16 00:23:01 2009 -0700
@@ -1,5 +1,7 @@
+#include <utilities/log.h>
+
 AlphaSimplex3D::	    
-AlphaSimplex3D(const ::Vertex& v): alpha_(0), attached_(false)
+AlphaSimplex3D(const Delaunay3D::Vertex& v): alpha_(0), attached_(false)
 {
 	for (int i = 0; i < 4; ++i)
 		if (v.cell()->vertex(i)->point() == v.point())
@@ -7,7 +9,7 @@
 }
 
 AlphaSimplex3D::	    
-AlphaSimplex3D(const Delaunay::Edge& e)
+AlphaSimplex3D(const Delaunay3D::Edge& e)
 {
     Cell_handle c = e.first;
 	Parent::add(c->vertex(e.second));
@@ -15,7 +17,7 @@
 }
 
 AlphaSimplex3D::	    
-AlphaSimplex3D(const Delaunay::Edge& e, const SimplexSet& simplices, const Delaunay& Dt, Facet_circulator facet_bg)
+AlphaSimplex3D(const Delaunay3D::Edge& e, const SimplexSet& simplices, const Delaunay3D& Dt, Facet_circulator facet_bg)
 {
     Cell_handle c = e.first;
 	Parent::add(c->vertex(e.second));
@@ -57,7 +59,7 @@
 }
 
 AlphaSimplex3D::	    
-AlphaSimplex3D(const Delaunay::Facet& f)
+AlphaSimplex3D(const Delaunay3D::Facet& f)
 {
     Cell_handle c = f.first;
 	for (int i = 0; i < 4; ++i)
@@ -66,7 +68,7 @@
 }
 
 AlphaSimplex3D::	    
-AlphaSimplex3D(const Delaunay::Facet& f, const SimplexSet& simplices, const Delaunay& Dt)
+AlphaSimplex3D(const Delaunay3D::Facet& f, const SimplexSet& simplices, const Delaunay3D& Dt)
 {
     Cell_handle c = f.first;
 	for (int i = 0; i < 4; ++i)
@@ -106,7 +108,7 @@
 }
 
 AlphaSimplex3D::	    
-AlphaSimplex3D(const Delaunay::Cell& c): attached_(false)
+AlphaSimplex3D(const Delaunay3D::Cell& c): attached_(false)
 {
 	for (int i = 0; i < 4; ++i)
 		Parent::add(c.vertex(i));
@@ -140,11 +142,9 @@
 	return out;
 }
 
-
-void fill_complex(const Delaunay& Dt, AlphaSimplex3DVector& alpha_order)
+void fill_simplex_set(const Delaunay3D& Dt, AlphaSimplex3D::SimplexSet& simplices)
 {
 	// Compute all simplices with their alpha values and attachment information
-	AlphaSimplex3D::SimplexSet simplices;
 	for(Cell_iterator cur = Dt.finite_cells_begin(); cur != Dt.finite_cells_end(); ++cur)
 		simplices.insert(AlphaSimplex3D(*cur));
 	rInfo("Cells inserted");
@@ -157,6 +157,12 @@
 	for(Vertex_iterator cur = Dt.finite_vertices_begin(); cur != Dt.finite_vertices_end(); ++cur)
 		simplices.insert(AlphaSimplex3D(*cur));
 	rInfo("Vertices inserted");
+}
+
+void fill_complex(const Delaunay3D& Dt, AlphaSimplex3DVector& alpha_order)
+{
+	AlphaSimplex3D::SimplexSet simplices;
+    fill_simplex_set(Dt, simplices);
     
 	// Sort simplices by their alpha values
 	alpha_order.resize(simplices.size());