delaunayNd: Delaunay tessellation

[ geometry, gpl, library, math ] [ Propose Tags ]

This library performs the Delaunay tessellation in arbitrary dimension.

It uses the C library qhull.

For examples, look at the README file.


[Skip to Readme]

Modules

[Index] [Quick Jump]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

Versions [RSS] 0.1.0.0, 0.1.0.1, 0.1.0.2
Change log CHANGELOG.md
Dependencies base (>=4.9 && <5), containers (>=0.6.4.1 && <0.8), extra (>=1.7.7 && <1.8), hashable (>=1.3.5.0 && <1.5), ilist (>=0.4.0.1 && <0.5), insert-ordered-containers (>=0.2.5.3 && <0.3), Unique (>=0.4.7.9 && <0.5) [details]
License GPL-3.0-only
Copyright 2023 Stéphane Laurent
Author Stéphane Laurent
Maintainer laurent_step@outlook.fr
Category Math, Geometry
Home page https://github.com/stla/delaunayNd#readme
Source repo head: git clone https://github.com/stla/delaunayNd
Uploaded by stla at 2023-11-20T08:17:07Z
Distributions NixOS:0.1.0.2
Reverse Dependencies 1 direct, 0 indirect [details]
Downloads 55 total (9 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2023-11-20 [all 1 reports]

Readme for delaunayNd-0.1.0.2

[back to package description]

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