DioDe

DioDe uses CGAL to generate alpha shapes filtrations in a format that Dionysus understands. DioDe is not integrated into Dionysus because of licensing restrictions (Dionysus is under BSD, DioDe is under GPL because of its dependence on CGAL). It supports both ordinary and weighted alpha shapes.

Dependencies:

• CGAL

Get, Build, Install

The simplest way to install Diode as a Python package:

pip install --verbose diode

or from this repository directly:

pip install --verbose git+https://github.com/mrzv/diode.git

Alternatively, you can clone and build everything by hand. To get Diode, either clone its repository:

git clone https://github.com/mrzv/diode.git

or download it as a Zip archive.

To build the project:

mkdir build
cd build
cmake ..
make

To use the Python bindings, either launch Python from .../build/bindings/python or add this directory to your PYTHONPATH variable, by adding:

export PYTHONPATH=.../build/bindings/python:$PYTHONPATH

to your ~/.bashrc or ~/.zshrc.

Usage

NB: a remark below about using exact computation. This issue is especially important when working with degenerate point sets (e.g., repeated copies of a fundamental domain in a periodic point set).

See examples/generate_alpha_shape.cpp and examples/generate_weighted_alpha_shape.cpp for C++ examples.

In Python, use diode.fill_alpha_shapes(...) and diode.fill_weighted_alpha_shapes(...) to fill a list of simplices, together with their alpha values:

>>> import diode
>>> import numpy as np

>>> points = np.random.random((100,3))
>>> simplices = diode.fill_alpha_shapes(points)

>>> print(simplices)
 [([13L], 0.0),
  ([18L], 0.0),
  ([59L], 0.0),
  ([10L], 0.0),
  ([72L], 0.0),
  ...,
  ([91L, 4L, 16L, 49L], 546.991052812204),
  ([49L, 62L], 1933.2257381777533),
  ([62L, 34L, 49L], 1933.2257381777533),
  ([62L, 91L, 49L], 1933.2257381777533),
  ([62L, 91L, 34L, 49L], 1933.2257381777533)]

>>> weighted_points = np.random.random((100,4))
>>> simplices2 = diode.fill_weighted_alpha_shapes(weighted_points)
>>> print(simplices2)
[([24L], -0.987214836816236),
 ([35L], -0.968749877102265),
 ([50L], -0.9673151804059413),
 ([47L], -0.9640549893422644),
 ([71L], -0.9639978806827709),
 ([24L, 50L], -0.9540965704765515),
 ...
 ([54L, 10L], 29223.611044169364),
 ([10L, 54L, 43L], 29223.611044169364),
 ([13L, 10L, 54L], 29223.611044169364),
 ([13L, 10L, 54L, 43L], 29223.611044169364)]

The list can be passed to Dionysus to initialize a filtration:

>>> import dionysus
>>> f = dionysus.Filtration(simplices)
>>> print(f)
Filtration with 2287 simplices

DioDe also includes diode.fill_periodic_alpha_shapes(...), which generates the alpha shape for a point set on a periodic cube, by default [0,0,0] - [1,1,1]. (In the periodic case, it may happen that CGAL reports each simplex multiple times. However, passing the result to dionysus.Filtration will take care of the duplicates.):

>>> simplices_periodic = diode.fill_periodic_alpha_shapes(points)
>>> f_periodic = dionysus.Filtration(simplices_periodic)
>>> print(f_periodic)
Filtration with 2912 simplices

>>> for s in f_periodic: print(s)
<0> 0
<1> 0
<2> 0
<3> 0
...
<77,94,97> 0.0704355
<46,77,94,97> 0.0708062
<30,77,94,97> 0.0708474
<18,65,79> 0.0715833
<18,64,65,79> 0.0715833
<18,65,79,99> 0.0725366

When using CGAL version at least 4.11, DioDe includes diode.fill_weighted_periodic_alpha_shapes(...), which generates the alpha shape for a weighted point set on a periodic cube:

>>> weighted_points[:,3] /= 64
>>> simplices_weighted_periodic = diode.fill_weighted_periodic_alpha_shapes(weighted_points)

diode.circumcenter(...) can be used to compute the circumcenter of a tetrahedron in 3D:

>>> tet = np.random.random((4,3))
>>> center = diode.circumcenter(tet)
>>> print(center)
[-0.00752673  0.14213101  1.0060982 ]

Delaunay combinatorics (no alpha values)

Some consumers only need the simplicial complex (the Delaunay triangulation, which for full-dimensional input is the same simplex set as the alpha complex) and recompute their own filtration values -- for example a differentiable Cech-Delaunay filtration that recomputes values as minimum-enclosing-ball radii. For those, diode.fill_delaunay_arrays(...) returns just the combinatorics, skipping all of CGAL's per-simplex Gabriel/circumradius work (about 1.6x faster than the alpha path in 2D and 4x in 3D):

>>> verts_by_dim = diode.fill_delaunay_arrays(points)

The result is a list of per-dimension NumPy arrays, where verts_by_dim[d] is an (n_d, d+1) int64 array of vertex ids (dimension 0 = vertices, 1 = edges, and so on). diode.fill_delaunay(...) is the equivalent list-of-tuples form. diode.fill_periodic_delaunay_arrays(...) / diode.fill_periodic_delaunay(...) are the periodic counterparts (over the cube [from, to], default the unit cube). All four take the same exact argument as the alpha-shape functions.

Exactness

All functions take an argument exact, set to False by default. The argument determines a choice of the kernel in CGAL (Exact_predicates_inexact_constructions_kernel vs Exact_predicates_exact_constructions_kernel). exact = True guarantees correctness of the output; exact = False is faster, but can sometimes fail (not even produce a simplicial complex). It's possible to run the two versions adaptively by running the default exact = False version first, and if the result is not a simplicial complex, then run exact = True. This should be the best of both worlds.