concave hulls using shapely and scipy

concave_hulls.ipynb

Hello dwyerk

I prepared this example (https://github.com/vic1309/concave_hull_area) with a test data and a Jupyter notebook. Please, feel free to make suggestions and play around with them. A feedback would be just awesome :)

Looks like a great presentation!

Hello dwyerk, I think your work is perfect. Can it be extended to higher dimension (>3)?

Hello dwyerk, I think your work is perfect. Can it be extended to higher dimension (>3)?

Hi dd-debug. There is probably an algorithm for concave hulls in 3D but I think it's more complicated than adjusting this one. Since the triangulation is 2D by nature, you'll need to find a way to work with surfaces. Good luck!

Hey dd-debug, there's already an algorithm for computing N-dimensional concave hulls. You can find discussion of the algorithm and intuition for it in the paper A New Concave Hull Algorithm and Concaveness Measure for n-dimensional Datasets by Jin-Seo Park and Se-Jong Oh, the link for which I've attached here:

https://journal.iis.sinica.edu.tw/paper/1/100295-3.pdf?cd=2217EEBB7C44EDA26.

I've tinkered with an implementation of it that's available on github which I've trial-ran in the past couple of days and I'm getting pleasing results, though I have by no means looked through it in detail for optimization tweaks. You can find that here:

https://gist.github.com/AndreLester/589ea1eddd3a28d00f3d7e47bd9f28fb

I hope that helps address your question!

What if I don't want to scale up and add more points? That is, given the H shape at the first beginning, how to get the concave hull? I've tried multiple alpha shape libraries but none of them worked for a set of points which only include the boundary without any interior points.

You can still try, but you may not be able to find an acceptable alpha value. It's been a few years since I was working on this but if I recall correctly, the delaunay triangulation doesn't generate enough triangles to be later pruned, or at least the space between them is not great enough.

# Area of triangle by Heron's formula
area = math.sqrt(s*(s-a)*(s-b)*(s-c))
circum_r = a*b*c/(4.0*area)
if circum_r < 1.0/alpha:
    # Keep these edges

Those areas need to be low enough to be less than the inverse of the alpha parameter. I'd step through this in a debugger with your shapefile and see what kind of values you're getting for each triangle to see if you can find a better set of parameters.

FYI for anyone running this notebook today (unless Descartes receives an update), you need to patch Descartes as described in this stackoverflow answer or the plot_polygon won't work https://stackoverflow.com/questions/75287534/indexerror-descartes-polygonpatch-wtih-shapely

I get the error "AttributeError: 'Delaunay' object has no attribute 'vertices'"

Is the .vertices method deprecated for Delaunay?

Yeah looks like it scipy/scipy@99cc995

Switch to tri.simplices

Yeah looks like it scipy/scipy@99cc995

Switch to tri.simplices

That fixed it. Thanks!

I am trying to get this to work for two offset sine waves. However, the best I can get is the second image. After that, increasing the alpha parameter creates a segmented geometry. Perhaps my ordering of points isn't in the proper format for this function?