# AlphaShapes.jl Documentation

## Overview of AlphaShapes.jl

### Alpha Shapes

An $\alpha$-shape is closely related to the Delaunay triangulation and Convex Hull of a set of points (in any dimension).

The $\alpha$-shape is constructed for a parameter $\alpha$ by testing each Delaunay simplex to determine if it's circumsphere has a radius less than $\alpha$. If it does then the simplex is kept, otherwise the simplex is removed. This modified triangulation is the $\alpha$-shape.

Choosing $\alpha$ is done in many ways. AlphaShapes.jl optimises $\alpha$ to find the triangulation with the smallest volume which includes all input points as a vertex to at least on simplex.

### Functionality

AlphaShapes.jl represents an $\alpha$-shape as a function of an array, `Array{Float64,2}`

, of points. So all user functionality comes through this.

`AlphaShapes.AlphaShape`

— Function```
AlphaShape(X::Array{Float64,2};α::Union{Nothing,Float64}=nothing,
search::Tuple{Float64,Float64}=(0.0, 10.0),
MaxSteps::Int=100)::Array{Float64,3}
```

Find the alpha shape corresponding to the 2D array of points X: [npoints,2], and the α value α.

If α == nothing then a search over the range of values search is done to find the best value. The optimisation objective is the alpha shape area (minimise) subject to all points in X being included in the alpha shape triangulation.

### Utils

The volume of one simplex can be found using

`AlphaShapes.SimplexVolume`

— Function`SimplexVolume`

Calculate the volume of a simplex using the Cayley Menger matrix

https://westy31.home.xs4all.nl/Circumsphere/ncircumsphere.htm

For the whole $\alpha$-shape the volume can be found using

`AlphaShapes.AlphaShapeVolume`

— Function`AlphaShapeVolume(A::Array{Float64,3})`

return the sum of volumes of all simplices in the alpha shapes A

The Delaunay triangulation is used to build the alpha shapes so there is a helper method to build one for any set of points (MiniQhull.jl)

`AlphaShapes.GetDelaunayTriangulation`

— Function`GetDelaunayTriangulation(points::Array{Float64,2})::Array{Float64,3}`

Wrap MiniQhull.jl's delaunay to get a delaunay triangualation in any dimension

### Under the hood

Arbitrary dimensions is handled by using the Cayley-Menger matrix for simplex volume and simplex circumsphere calculation

`AlphaShapes.CayleyMenger`

— Function```
CayleyMenger
Compute the Cayley-Menger matrix from squared
distances dij^2.
https://mathworld.wolfram.com/Cayley-MengerDeterminant.html
For a 2-d triangle the following example would symbolically
represent the matrix for points x1, x2, and x3 where dij^2
is the square Euclidean distance between i and j
Example
```

```
julia>:([0 1 1 1
1 0 d12^2 d13^2
1 d21^2 0 d23^2
1 d32^2 d32^2 0])
:([0 1 1 1; 1 0 d12 ^ 2 d13 ^ 2; 1 d21 ^ 2 0 d23 ^ 2; 1 d32 ^ 2 d32 ^ 2 0])
```

`AlphaShapes.SimplexCircumSphere`

— Function`SimplexCircumSphere`

Find the centre and radius of the circumsphere of a simplex https://westy31.home.xs4all.nl/Circumsphere/ncircumsphere.htm