Skip to main content

A very fast 2D concave hull algorithm

Project description

concave_hull

A very fast 2D concave hull algorithm.

Credits goes to:

Install

via pip

pip install concave_hull

from source

git clone --recursive https://github.com/cubao/concave_hull
pip install ./concave_hull

Or

pip install git+https://github.com/cubao/concave_hull.git

(you can build wheels for later reuse by pip wheel git+https://github.com/cubao/concave_hull.git)

Usage

Signature:

# get concave hull indexes
concave_hull_indexes(
       points: Union[numpy.ndarray, List, Tuple],
       *,
       concavity: float = 2.0,
       length_threshold: float = 0.0,
       convex_hull_indexes: numpy.ndarray[numpy.int32[m, 1]] = None, # will use integrated scipy ConvexHull if None
) -> numpy.ndarray[numpy.int32[m, 1]]

# get concave hull points
concave_hull(
       points: Union[numpy.ndarray, List, Tuple],
       *args, *kwargs # will proxy all to covcave_hull_indexes
) -> Union[numpy.ndarray, List, Tuple]
  • concavity is a relative measure of concavity. 1 results in a relatively detailed shape, Infinity results in a convex hull. You can use values lower than 1, but they can produce pretty crazy shapes.
  • length_threshold: when a segment length is under this threshold, it stops being considered for further detalization. Higher values result in simpler shapes.

(document from https://github.com/mapbox/concaveman)

Example (see full code in test.py):

import matplotlib.pyplot as plt
import numpy as np
from scipy.spatial import ConvexHull

from concave_hull import concave_hull, concave_hull_indexes

points = []
c = np.array([250, 250])
for x in np.arange(100, 400, 5 * np.pi):
    for y in np.arange(100, 400, 5 * np.pi):
        if x > c[0] and y > c[1]:
            continue
        r = np.linalg.norm(c - [x, y])
        if r > 150:
            continue
        points.append([x, y])
points = np.array(points)
convex_hull = ConvexHull(points[:, :2])  # it's already N-by-2, I'm just emphasizing

# https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.ConvexHull.html

plt.plot(points[:, 0], points[:, 1], "o")
for simplex in convex_hull.simplices:
    plt.plot(points[simplex, 0], points[simplex, 1], "g-", alpha=0.5)

idxes = concave_hull_indexes(
    points[:, :2],
    length_threshold=50,
    # for concave_hull>=0.0.3
    #   it's not necessary to provide convex_hull_indexes
    # convex_hull_indexes=convex_hull.vertices.astype(np.int32),
)
# you can get coordinates by `points[idxes]`
assert np.all(points[idxes] == concave_hull(points, length_threshold=50))

for f, t in zip(idxes[:-1], idxes[1:]):  # noqa
    seg = points[[f, t]]
    plt.plot(seg[:, 0], seg[:, 1], "r-", alpha=0.5)
# plt.savefig('hull.png')
plt.show()

Tests

make python_install
make python_test

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

concave_hull-0.0.5.tar.gz (3.2 MB view hashes)

Uploaded Source

Built Distributions

concave_hull-0.0.5-cp311-cp311-win_amd64.whl (74.8 kB view hashes)

Uploaded CPython 3.11 Windows x86-64

concave_hull-0.0.5-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (95.5 kB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ x86-64

concave_hull-0.0.5-cp311-cp311-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (87.7 kB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ ARM64

concave_hull-0.0.5-cp311-cp311-macosx_11_0_arm64.whl (61.0 kB view hashes)

Uploaded CPython 3.11 macOS 11.0+ ARM64

concave_hull-0.0.5-cp311-cp311-macosx_10_9_x86_64.whl (67.0 kB view hashes)

Uploaded CPython 3.11 macOS 10.9+ x86-64

concave_hull-0.0.5-cp310-cp310-win_amd64.whl (74.9 kB view hashes)

Uploaded CPython 3.10 Windows x86-64

concave_hull-0.0.5-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (95.5 kB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ x86-64

concave_hull-0.0.5-cp310-cp310-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (87.7 kB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ ARM64

concave_hull-0.0.5-cp310-cp310-macosx_11_0_arm64.whl (61.0 kB view hashes)

Uploaded CPython 3.10 macOS 11.0+ ARM64

concave_hull-0.0.5-cp310-cp310-macosx_10_9_x86_64.whl (67.0 kB view hashes)

Uploaded CPython 3.10 macOS 10.9+ x86-64

concave_hull-0.0.5-cp39-cp39-win_amd64.whl (75.0 kB view hashes)

Uploaded CPython 3.9 Windows x86-64

concave_hull-0.0.5-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (95.6 kB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.17+ x86-64

concave_hull-0.0.5-cp39-cp39-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (87.9 kB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.17+ ARM64

concave_hull-0.0.5-cp39-cp39-macosx_11_0_arm64.whl (61.2 kB view hashes)

Uploaded CPython 3.9 macOS 11.0+ ARM64

concave_hull-0.0.5-cp39-cp39-macosx_10_9_x86_64.whl (67.1 kB view hashes)

Uploaded CPython 3.9 macOS 10.9+ x86-64

concave_hull-0.0.5-cp38-cp38-win_amd64.whl (74.7 kB view hashes)

Uploaded CPython 3.8 Windows x86-64

concave_hull-0.0.5-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (95.3 kB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.17+ x86-64

concave_hull-0.0.5-cp38-cp38-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (87.8 kB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.17+ ARM64

concave_hull-0.0.5-cp38-cp38-macosx_11_0_arm64.whl (61.0 kB view hashes)

Uploaded CPython 3.8 macOS 11.0+ ARM64

concave_hull-0.0.5-cp38-cp38-macosx_10_9_x86_64.whl (67.0 kB view hashes)

Uploaded CPython 3.8 macOS 10.9+ x86-64

concave_hull-0.0.5-cp37-cp37m-win_amd64.whl (74.7 kB view hashes)

Uploaded CPython 3.7m Windows x86-64

concave_hull-0.0.5-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (96.8 kB view hashes)

Uploaded CPython 3.7m manylinux: glibc 2.17+ x86-64

concave_hull-0.0.5-cp37-cp37m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (89.8 kB view hashes)

Uploaded CPython 3.7m manylinux: glibc 2.17+ ARM64

concave_hull-0.0.5-cp37-cp37m-macosx_10_9_x86_64.whl (67.1 kB view hashes)

Uploaded CPython 3.7m macOS 10.9+ x86-64

concave_hull-0.0.5-cp36-cp36m-win_amd64.whl (74.7 kB view hashes)

Uploaded CPython 3.6m Windows x86-64

concave_hull-0.0.5-cp36-cp36m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (96.8 kB view hashes)

Uploaded CPython 3.6m manylinux: glibc 2.17+ x86-64

concave_hull-0.0.5-cp36-cp36m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (89.8 kB view hashes)

Uploaded CPython 3.6m manylinux: glibc 2.17+ ARM64

concave_hull-0.0.5-cp36-cp36m-macosx_10_9_x86_64.whl (67.1 kB view hashes)

Uploaded CPython 3.6m macOS 10.9+ x86-64

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page