delaunayNd
Delaunay tessellation in arbitrary dimension.
Based on the qhull
C library.
Consider this list of vertices (actually these are the vertices of a
polyhedron):
vertices :: [[Double]]
vertices = [
[ 5, 5, 16 ]  0
, [ 5, 8, 3 ]  1
, [ 4, 1, 3 ]  2
, [ 4, 5, 7 ]  3
, [ 4, 1, 10 ]  4
, [ 4, 5, 10 ]  5
, [ 5, 8, 10 ]  6
, [ 5, 5, 10 ]  7
]
The delaunay
function splits the polyhedron into simplices, the tiles of the
tesselation:
> import Geometry.Delaunay
> d < delaunay vertices False False Nothing
> _tiles d
fromList
[ ( 0
, Tile
{ _simplex =
Simplex
{ _vertices' =
fromList
[ ( 2 , [ 4.0 , 1.0 , 3.0 ] )
, ( 4 , [ 4.0 , 1.0 , 10.0 ] )
, ( 5 , [ 4.0 , 5.0 , 10.0 ] )
, ( 7 , [ 5.0 , 5.0 , 10.0 ] )
]
, _circumcenter =
[ 0.5000000000000009 , 3.0 , 3.499999999999999 ]
, _circumradius = 8.154753215150047
, _volume' = 78.0
}
, _neighborsIds = fromList [ 1 , 3 ]
, _facetsIds = fromList [ 0 , 1 , 2 , 3 ]
, _family' = None
, _toporiented = False
}
)
, ( 1
, Tile
......
The field _tiles
is a map of Tile
objects. The keys of the map are
the tiles identifiers. A Tile
object has five fields:

_simplex
, a Simplex
object;

_neighborsIds
, a set of tiles identifiers, the neighbors of the tile;

facetsIds
, a set of facets identifiers, the facets of the tile;

family'
, two tiles of the same family share the same circumcenter;

toporiented
, Boolean, whether the tile is toporiented.
A Simplex
object has four fields:

_vertices
, the vertices of the simplex, actually a map of the vertices
identifiers to their coordinates;

_circumcenter
, the coordinates of the circumcenter of the simplex;

_circumradius
, the circumradius;

_volume'
, the volume of the simplex (the area in dimension 2, the
length in dimension 1).
Another field of the output of delaunay
is _tilefacets
:
> _tilefacets d
fromList
[ ( 0
, TileFacet
{ _subsimplex =
Simplex
{ _vertices' =
fromList
[ ( 4 , [ 4.0 , 1.0 , 10.0 ] )
, ( 5 , [ 4.0 , 5.0 , 10.0 ] )
, ( 7 , [ 5.0 , 5.0 , 10.0 ] )
]
, _circumcenter = [ 0.5000000000000009 , 3.0 , 10.0 ]
, _circumradius = 4.924428900898053
, _volume' = 36.0
}
, _facetOf = fromList [ 0 ]
, _normal' = [ 0.0 , 0.0 , 1.0 ]
, _offset = 10.0
}
)
, ( 1
, TileFacet
{ _subsimplex =
......
This is a map of TileFacet
objects. A tile facet is a subsimplex. The keys of
the map are the identifiers of the facets.
A TileFacet
object has four fields: _subsimplex
, a Simplex
object,
_facetOf
, the identifiers of the tiles this facet belongs to (a set of one
or two integers), _normal'
, the normal of the facet, and offset
, the offset
of the facet.
The output of delaunay
also has a _sites
field, the vertices with
additional information:
> _sites d
fromList
[ ( 0
, Site
{ _point = [ 5.0 , 5.0 , 16.0 ]
, _neighsitesIds = fromList [ 1 , 3 , 7 ]
, _neighfacetsIds = fromList [ 15 , 16 , 17 ]
, _neightilesIds = fromList [ 5 ]
}
)
, ( 1
, Site
......
This is a map of Site
objects. The keys of the map are the identifiers of
the vertices. A Site
object has four fields:

_point
, the coordinates of the vertex;

_neighsitesIds
, the identifiers of the connected vertices;

_neighfacetsIds
, a set of integers, the identifiers of the facets the
vertex belongs to;

_neightilesIds
, the set of the identifiers of the tiles the vertex belongs
to.
Finally, the output of delaunay
has the _edges'
field, providing the
edges:
> _edges' d
fromList
[ ( Pair 0 1 , ( [ 5.0 , 5.0 , 16.0 ] , [ 5.0 , 8.0 , 3.0 ] ) )
, ( Pair 0 3 , ( [ 5.0 , 5.0 , 16.0 ] , [ 4.0 , 5.0 , 7.0 ] ) )
, ......