How do you generate the non-convex hull from a series of points?

Question

I am currently trying to construct the area covered by a device over an operating period. The first step in this process appears to be constructing a polygon of the covered area. Since the pattern is not a standard shape, convex hulls overstate the covered area by jumping to the largest coverage area possible.

I have found a paper that appears to cover the concept of non-convex hull generation, but no discussions on how to implement this within a high level language. http://www.geosensor.net/papers/duckham08.PR.pdf

Has anyone seen a straight forward algorithm for constructing a non-convex hull or concave hull or perhaps any python code to achieve the same result?

I have tried convex hulls mainly qhull, with a limited edge size with limited success. Also I have noticed some licensed libraries that will not be able to be distributed, so unfortunately thats off the table. Any better ideas or cookbooks?

Answer 1

You might try looking into Alpha Shapes. The CGAL library can compute them.

Edit: I see that the paper you linked references alpha shapes, and also has an algorithm listing. Is that not high level enough for you? Since you listed python as a tag, I'm sure there are Delaunay triangulation libraries in Python, which I think is the hardest part of implementing the algorithm; you just need to make sure you can modify the resulting triangulation output. The boundary query functions can probably be implemented with associative arrays.