@hackage / delaunayNd

Delaunay tessellation

Latest0.1.0.2

About

Metadata

  • Last updated , by stla
  • License GPL-3.0-only
  • Categories Mathematics

  • Maintained by: laurent_step@outlook.fr

  • Lottery factor: 0

Links

Installation

Readme

delaunayNd

Stack-lts Stack-lts-Mac Stack-nightly

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 top-oriented.

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 ] ) )

  , ......