Instantly share code, notes, and snippets.

# AndreLester/ConcaveHull.py

Last active April 2, 2024 12:59
Show Gist options
• Save AndreLester/589ea1eddd3a28d00f3d7e47bd9f28fb to your computer and use it in GitHub Desktop.
Fast concave hull implementation in Python.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters

### kinreehou commented Feb 11, 2020

how to return the boundary points?

### jafekb commented Mar 5, 2020 • edited

``````import numpy as np
from ConcaveHull import ConcaveHull

ch = ConcaveHull()
pts = np.random.uniform(size=(100, 2))
ch.calculatehull()

boundary_points = np.vstack(ch.boundary.exterior.coords.xy).T
# boundary_points is a subset of pts corresponding to the concave hull

``````

### paulaceccon commented Mar 9, 2020

Much faster then using alphashape!

### shiernee commented Apr 10, 2020

how can i plot the surface of the polygon?

### planzaprecisionag commented Apr 17, 2020 • edited

how can i plot the surface of the polygon?

Have you tried accessing the class's polygon object? So something like ploygonToPlot = ch.boundary, then just plot it however you normally plot polygons.

- had typed ch.polygon instead of boundary to reference the polygon object

### jakobhaervig commented Feb 2, 2021

Used your code as part of my project. Thought it would interesting for you:
https://externalflow.et.aau.dk/image-processing-techniques/

### RobSimpsonHove commented Mar 30, 2021

Is this Concave or Convex Hulls - I am getting only Convex hulls from this.

### Fajikuma commented Apr 21, 2021

Is this Concave or Convex Hulls - I am getting only Convex hulls from this.

I'm also getting Convex hulls instead of the intended Concave ones. This code here provided better results, at least in my case, although they are not yet what I need. Hope it helps you.

https://gist.github.com/dwyerk/10561690

### TinKurbatoff commented Apr 24, 2021

This code produces CONVEX hull:

That is good and clean code, but the naming is incorrect.

### RobSimpsonHove commented Apr 25, 2021

Thanks, I thought as much. I've ended up using alphashape.

### TinKurbatoff commented Apr 25, 2021 • edited

I am using alpha shape, but it still not as well as I want to:

——————
It is a "manual" code, and it used the Delaunay function.
The code template I took from here:
Not ideal, but it works better.
—————
I still try to build a concave hull algorithm implementation. Will keep you posted if succeed.

### arjun-bala-krishnan commented Sep 8, 2021

I am still trying to find a similar implementation in 3D using python. If anybody manages to find it (similar to MATLAB boundary function for 3d) it would be really helpful.

### jatinnimawat commented Oct 18, 2022

Is this Concave or Convex Hulls - I am getting only Convex hulls from this.

I'm also getting Convex hulls instead of the intended Concave ones. This code here provided better results, at least in my case, although they are not yet what I need. Hope it helps you.

https://gist.github.com/dwyerk/10561690

Same here. I am also getting convex hulls instead of concave.

### cvr commented Feb 8, 2023

To get a concave hull you need to change the tolerance by changing argument `tol`:

```ch = ConcaveHull()
ch.calculatehull(tol=0.5)```

Is this Concave or Convex Hulls - I am getting only Convex hulls from this.

I'm also getting Convex hulls instead of the intended Concave ones. This code here provided better results, at least in my case, although they are not yet what I need. Hope it helps you.
https://gist.github.com/dwyerk/10561690

Same here. I am also getting convex hulls instead of concave.

### AndreLester commented Feb 8, 2023 • edited

@cvr The "tol" variable presents the length of the longest edge you wish to have in the respective units. Usually in feet or metres. It is not a factor between zero and one as other concave hull algorithms. I prefer it like this.
The problems above where the people got convex hulls was probably due to the fact that their units was in degrees.

Note: Apologies. I was unaware that my "gist" blew up like this.

### cvr commented Feb 8, 2023 • edited

Thanks for the clarification. Matter of fact I was also using degrees in the test case where I'm trying your code.

It actually makes a lot of sense now. You could have it in degrees, it is just a question of changing the `tol` value to a meaningful value of distance, if you would convert it to degrees (e.g. divide `tol` in km it by 111.045 to have a rough measure in degrees).

As this will depend on some triangulation of a set of points, eventually `tol` could be made as a fraction of the total width (or height) span of the collection of points.

### Joshua-Mursic commented Jun 1, 2023

@AndreLester, Thanks a lot for the code! I am trying to implement a offset value into this function, do you have any idea how this would work?

Like in the image above the green is original shape and the blue is the offset shape.

### AndreLester commented Jun 2, 2023 • edited

@Joshua-Mursic I would use the buffer function from shapely on the resultant polygon. Play around with the options to get the desired result.

### AndreLester commented Jul 16, 2023

I have updated, modified and documented this script. It can be found at https://github.com/civildot/cdBoundary and installed with:

`pip install cdBoundary`