-
-
Save dwyerk/10561690 to your computer and use it in GitHub Desktop.
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?
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!