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

Question

I'm currently trying to build the area covered by the device over a period of work. The first step in this process, apparently, is to create a polygon of the covered area. Since the pattern is not a standard shape, convex hulls exaggerate the covered area, jumping to the largest coverage area.

I found a document that seems to cover the concept of generating non-convex hulls, but does not discuss how to implement this in a high-level language. http://www.geosensor.net/papers/duckham08.PR.pdf

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

I tried convex hulls mostly qhull with a limited edge size with limited success. I also noticed some licensed libraries that could not be distributed, so unfortunately this does not work. Any better ideas or cookbooks?

Answer 1

You can try looking at alpha shapes. The CGAL library can calculate them.

Change I see that the document you linked uses alpha forms, and also has a list of algorithms. Is this not a high enough level for you? Since you pointed python as a tag, I'm sure Python has Delaunay triangulation libraries, which, in my opinion, are the most difficult part of the algorithm implementation; you just need to make sure that you can change the result of the triangulation. Boundary query functions can probably be implemented using associative arrays.

Answer 2

I wrote an application to calculate the non-convex hull of a set of points (you will need java jre to run).