doc/python/alphashapes.rst
author Dmitriy Morozov <dmitriy@mrzv.org>
Sat, 28 Nov 2009 16:45:42 -0800
branchdev
changeset 174 3f1034dca432
parent 134 c270826fd4a8
child 181 1ee6edc17cb6
permissions -rw-r--r--
Instrumented code for counting: * added counters to addition in cohomology and ChainWrapper * rips-pairwise-cohomology counts the maximum elements stored in the cycles * added alphashapes3d-cohomology * moved progress_display from DynamicPersistence to StaticPersistence

.. _alphashapes:

Alpha shapes
============

There are two functions provided to compute alpha shapes. One in 2D and one in
3D. Both take a list of points (each a list of coordinates) as input, and fill a
list with the simplices of the `Delaunay triangulation`_. Each such simplex is
said to be *attached* (or *regular*) if its dual Voronoi cell does not contain a
critical point of the distance function to the point set. The smallest value of
the squared distance function on the dual Voronoi cell of the Delaunay simplex
is the alpha shape value assigned to it. This value is stored in the simplex's
`data` attribute; whether it is attached is stored in the `attached` attribute.

.. _`Delaunay triangulation`:   http://en.wikipedia.org/wiki/Delaunay_triangulation


.. function:: fill_alpha2D_complex(points, complex)
    
    Appends to the list `complex` the simplices of the 2D Delaunay triangulation
    on the `points`.

.. function:: fill_alpha3D_complex(points, complex)
    
    Appends to the list `complex` the simplices of the 3D Delaunay triangulation
    on the `points`.


Example
-------

The following example generates 10 points on a circle, and computes their
Delaunay triangulation with corresponding alpha shape values::

    from math import sin, cos, pi
    points = [[cos(2*pi*t/10), sin(2*pi*t/10)] for t in xrange(10)]
    complex = []
    fill_alpha2D_complex(points, complex)

One can extract any given alpha shape with the usual Python list notation::

    alphashape = [s for s in complex if s.data <= .5]