Alpha Shape Toolbox

Toolbox for generating n-dimensional alpha shapes.

Alpha shapes are often used to generalize bounding polygons containing sets of points. The alpha parameter is defined as the value a, such that an edge of a disk of radius 1/a can be drawn between any two edge members of a set of points and still contain all the points. The convex hull, a shape resembling what you would see if you wrapped a rubber band around pegs at all the data points, is an alpha shape where the alpha parameter is equal to zero. In this toolbox we will be generating alpha complexes, which are closely related to alpha shapes, but which consist of straight lines between the edge points instead of arcs of circles.

https://en.wikipedia.org/wiki/Alpha_shape

https://en.wikipedia.org/wiki/Convex_hull

Creating alpha shapes around sets of points usually requires a visually interactive step where the alpha parameter for a concave hull is determined by iterating over or bisecting values to approach a best fit. The alpha shape toolbox provides workflows to shorten the development loop on this manual process, or to bypass it completely by solving for an alpha shape with particular characteristics. A python API is provided to aid in the scripted generation of alpha shapes. A console application is also provided as an example usage of the alpha shape toolbox, and to facilitate generation of alpha shapes from the command line.

• Free software: MIT license
• Documentation: https://alphashape.readthedocs.io.

Features

Import Dependencies

import os
import sys
import pandas as pd
import numpy as np
from descartes import PolygonPatch
import matplotlib.pyplot as plt
sys.path.insert(0, os.path.dirname(os.getcwd()))
import alphashape

2 Dimensional Example

Define a set of points

points_2d = [(0., 0.), (0., 1.), (1., 1.), (1., 0.),
          (0.5, 0.25), (0.5, 0.75), (0.25, 0.5), (0.75, 0.5)]

Visualize Test Coordinates

fig, ax = plt.subplots()
ax.scatter(*zip(*points_2d))
plt.show()

Generate an Alpha Shape ($\alpha=0.0$) (Convex Hull)

Every convex hull is an alpha shape, but not every alpha shape is a convex hull. When the alphashape function is called with an alpha parameter of 0, a convex hull will always be returned.

Create the alpha shape

You can visualize the shape within Jupyter notebooks using the built-in shapely renderer as shown below.

alpha_shape = alphashape.alphashape(points_2d, 0.)
alpha_shape

Plotting the alpha shape over the input data with Matplotlib

fig, ax = plt.subplots()
ax.scatter(*zip(*points_2d))
ax.add_patch(PolygonPatch(alpha_shape, alpha=0.2))
plt.show()

Generate an Alpha Shape ($\alpha=2.0$) (Concave Hull)

As we increase the alpha parameter value, the bounding shape will begin to fit the sample data with a more tightly fitting bounding box.

Create the alpha shape

alpha_shape = alphashape.alphashape(points_2d, 2.0)
alpha_shape

Plotting the alpha shape over the input data with Matplotlib

fig, ax = plt.subplots()
ax.scatter(*zip(*points_2d))
ax.add_patch(PolygonPatch(alpha_shape, alpha=0.2))
plt.show()

Generate an Alpha Shape ($\alpha=3.5$)

If you go too high on the alpha parameter, you will start to lose points from the original data set.

Create the alpha shape

alpha_shape = alphashape.alphashape(points_2d, 3.5)
alpha_shape

Plotting the alpha shape over the input data with Matplotlib

fig, ax = plt.subplots()
ax.scatter(*zip(*points_2d))
ax.add_patch(PolygonPatch(alpha_shape, alpha=0.2))
plt.show()

Generate an Alpha Shape (Alpha=5.0)

If you go too far, you will lose everything.

alpha_shape = alphashape.alphashape(points_2d, 5.0)
print(alpha_shape)

GEOMETRYCOLLECTION EMPTY

Using a varying Alpha Parameter

The alpha parameter can be defined locally within a region of points by supplying a callback that will return what alpha parameter to use. This can be utilized to create tighter fitting alpha shapes where point densitities are different in different regions of a data set. In the following example, the alpha parameter is changed based off of the value of the x-coordinate of the points.

alpha_shape = alphashape.alphashape(
    points_2d,
    lambda ind, r: 1.0 + any(np.array(points_2d)[ind][:,0] == 0.0))
alpha_shape

Plotting the alpha shape over the input data with Matplotlib

fig, ax = plt.subplots()
ax.scatter(*zip(*points_2d))
ax.add_patch(PolygonPatch(alpha_shape, alpha=0.2))
plt.show()

Generate an Alpha Shape by Solving for an Optimal Alpha Value

The alpha parameter can be solved for if it is not provided as an argument, but with large datasets this can take a long time to calculate.

Create the alpha shape

alpha_shape = alphashape.alphashape(points_2d)
alpha_shape

Plotting the alpha shape over the input data

fig, ax = plt.subplots()
ax.scatter(*zip(*points_2d))
ax.add_patch(PolygonPatch(alpha_shape, alpha=0.2))
plt.show()

3 Dimensional Example

Define a set of points

points_3d = [
    (0., 0., 0.), (0., 0., 1.), (0., 1., 0.),
    (1., 0., 0.), (1., 1., 0.), (1., 0., 1.),
    (0., 1., 1.), (1., 1., 1.), (.25, .5, .5),
    (.5, .25, .5), (.5, .5, .25), (.75, .5, .5),
    (.5, .75, .5), (.5, .5, .75)
]

Visualize Test Coordinates

fig = plt.figure()
ax = plt.axes(projection='3d')
ax.scatter(df_3d['x'], df_3d['y'], df_3d['z'])
plt.show()

Alphashape with Static Alpha Parameter

You can visualize the shape within Jupyter notebooks using the built-in trimesh renderer by calling the .show() method as shown below.

alpha_shape = alphashape.alphashape(points_3d, 1.1)
alpha_shape.show()

fig = plt.figure()
ax = plt.axes(projection='3d')
ax.plot_trisurf(*zip(*alpha_shape.vertices), triangles=alpha_shape.faces)
plt.show()

Alphashape with Dymanic Alpha Parameter

alpha_shape = alphashape.alphashape(points_3d, lambda ind, r: 1.0 + any(
    np.array(points_3d)[ind][:,0] == 0.0))
alpha_shape.show()

fig = plt.figure()
ax = plt.axes(projection='3d')
ax.plot_trisurf(*zip(*alpha_shape.vertices), triangles=alpha_shape.faces)
plt.show()

Alphashape found by solving for the Alpha Parameter

alpha_shape = alphashape.alphashape(points_3d)
alpha_shape.show()

fig = plt.figure()
ax = plt.axes(projection='3d')
ax.plot_trisurf(*zip(*alpha_shape.vertices), triangles=alpha_shape.faces)
plt.show()

4 Dimensional Example

Define a set of points

points_4d = [
    (0., 0., 0., 0.), (0., 0., 0., 1.), (0., 0., 1., 0.),
    (0., 1., 0., 0.), (0., 1., 1., 0.), (0., 1., 0., 1.),
    (0., 0., 1., 1.), (0., 1., 1., 1.), (1., 0., 0., 0.),
    (1., 0.,