fast-alphashape

A Rust backed implementation for generating 2D alpha shapes from points.

This project is still a prototype and should not be considered production-ready.

Alpha shapes are often used to generalise 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.

Installation

pip install fast-alphashape

Quick start

The package provides an alphashape function that takes a 2D array of points and an alpha value:

import numpy as np
from fast_alphashape import alphashape

points = np.array(
    [
        (0.0, 0.0),
        (0.0, 1.0),
        (1.0, 1.0),
        (1.0, 0.0),
        (0.5, 0.25),
        (0.5, 0.75),
        (0.25, 0.5),
        (0.75, 0.5),
    ]
)

alpha_polygon = alphashape(points, alpha=2.0)

Development

Prequisites:

• Python (>=3.7) and make
• Rust toolchain

After cloning the repository, the Makefile includes helpful commands for setting up a development environment, linting, formatting, testing, and benchmarking. Get started as follows:

# setup a new virtual environment
python -m venv .venv
source .venv/bin/activate

# install the development dependencies
make install

# check other available commands
make help

Tooling:

• Cargo and Pytest are used for testing the Rust and Python code respectively (see /tests).
• Python code is linted using flake8 and formatted using Black; rust code with cargo fmt and cargo clippy.
• pre-commit is used to run these checks locally before files are pushed to git
• The Github Actions pipeline runs these checks and tests
• Semantic-release is used with conventional commits for automated releasing to PyPI

Credits

• This project is largely a Rust port of the Alpha Shape Toolbox by Ken Bellock
• Image credit: Sigbert, CC BY-SA 3.0, via Wikimedia Commons