convexHullNd: Convex hull

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

Computes the convex hull of a set of points in arbitrary dimension.

This library uses the C library qhull.

For examples, look at the README file.


[Skip to Readme]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 0.1.0.0
Change log CHANGELOG.md
Dependencies base (>=4.9 && <5), containers (>=0.6.4.1 && <0.7), 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), regex-compat (>=0.95 && <0.96), 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/convexHullNd#readme
Source repo head: git clone https://github.com/stla/convexHullNd
Uploaded by stla at 2023-11-22T20:04:53Z
Distributions NixOS:0.1.0.0
Downloads 20 total (6 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-22 [all 1 reports]

Readme for convexHullNd-0.1.0.0

[back to package description]

convexHullNd

Stack-lts Stack-lts-Mac Stack-nightly

Convex hull in arbitrary dimension.


The main function of this package is convexHull:

convexHull :: [[Double]]     -- ^ vertices
           -> Bool           -- ^ whether to triangulate
           -> Bool           -- ^ whether to print output to stdout
           -> Maybe FilePath -- ^ write summary to a file
           -> IO ConvexHull

The first argument is the list of the Cartesian coordinates of the points for which the convex hull is wanted. The second argument indicates whether one wants a "triangulated" convex hull. In 3D this means all facets of the hull are triangles. In 4D this means they all are tetrahedra. The correct word for any dimension is "simplex".

A ConvexHull object has the following fields:

  • _hvertices: provides the vertices of the convex hull;

  • _hfacets: provides the facets of the convex hull;

  • _hridges: provides the ridges (facets of facets) of the convex hull;

  • _hedges: provides the edges of the convex hull.

ConvexHull
  { _hvertices =
      fromList
        [ ( 0
          , Vertex
              { _point = [ 0.0 , 0.0 , 0.0 ]
              , _neighfacets = fromList [ 0 , 1 , 3 ]
              , _neighvertices = fromList [ 2 , 3 , 4 ]
              , _neighridges = fromList [ 1 , 2 , 4 ]
              }
          )
        , ...

  , _hfacets =
      fromList
        [ ( 0
          , Facet
              { _fvertices =
                  fromList
                    [ ( 0 , [ 0.0 , 0.0 , 0.0 ] )
                    , ( 1 , [ 0.0 , 1.0 , 1.0 ] )
                    , ( 2 , [ 0.0 , 0.0 , 1.0 ] )
                    , ( 3 , [ 0.0 , 1.0 , 0.0 ] )
                    ]
              , _fridges = fromList [ 0 , 1 , 2 , 3 ]
              , _centroid = [ 0.0 , 0.5 , 0.5 ]
              , _normal' = [ -1.0 , 0.0 , -0.0 ]
              , _offset' = -0.0
              , _orientation' = 1
              , _area = 1.0
              , _neighbors = fromList [ 1 , 2 , 3 , 5 ]
              , _family' = None
              , _fedges =
                  fromList
                    [ ( Pair 0 2 , ( [ 0.0 , 0.0 , 0.0 ] , [ 0.0 , 0.0 , 1.0 ] ) )
                    , ( Pair 0 3 , ( [ 0.0 , 0.0 , 0.0 ] , [ 0.0 , 1.0 , 0.0 ] ) )
                    , ( Pair 1 2 , ( [ 0.0 , 1.0 , 1.0 ] , [ 0.0 , 0.0 , 1.0 ] ) )
                    , ( Pair 1 3 , ( [ 0.0 , 1.0 , 1.0 ] , [ 0.0 , 1.0 , 0.0 ] ) )
                    ]
              }
          )
        , ...

  , _hridges =
      fromList
        [ ( 0
          , Ridge
              { _rvertices =
                  fromList
                    [ ( 1 , [ 0.0 , 1.0 , 1.0 ] ) , ( 2 , [ 0.0 , 0.0 , 1.0 ] ) ]
              , _ridgeOf = fromList [ 0 , 2 ]
              , _redges = fromList []
              }
          )
        , ...

  , _hedges =
      fromList
        [ ( Pair 0 2 , ( [ 0.0 , 0.0 , 0.0 ] , [ 0.0 , 0.0 , 1.0 ] ) )
        , ...

This is a big object. The function hullSummary returns a summary of it.

The hullVolume function returns the volume of the convex hull in any dimension (area in dimension 2, volume in dimension 3, hypervolume in higher dimension).

Another useful function is hullToSTL for dimension 3. It writes a STL file of the mesh representing the convex hull. One can visualize it in e.g. MeshLab.