Contents
How long does it take to compute a concave Hull?
This is to compare the affect of input point size and the number of iterations of K have on computation time. Large Example 1: 995165 input points, 5221 concave hull points, 10.7 seconds to compute. Large Example 2: 984119 input points, 4907 concave hull points, 16.8 seconds to compute.
What does the concave hull of a set of points look like?
Fortunately, there are alternatives to this state of affairs: we can calculate a concave hull. Here’s what the concave hull looks like when applied to the same set of points as in the previous image: Or maybe this one: As you can see, and contrary to the convex hull, there is no single definition of what the concave hull of a set of points is.
What happens when the Alpha of a hull is 1?
An alpha of 1 will result in a convex hull. Then the closer the alpha is to zero, the more flexible the contour of our shape will be. Draw triangles between the points so that there is no overlap between those triangles (this is known as Delauney Triangulation).
Can a concave hull be used as a discriminator?
This is a well-understood algorithm but suffers from the problem of not handling concave shapes, like this one: This shape does not correctly capture the essence of the underlying points. Were it used as a discriminator, some points would be incorrectly classified as being inside the cluster when they are not.
How is the concave hull of a polygon determined?
The algorithm stops on the first K that produces a valid concave hull. My program has a command line parameter to pass a higher K to produce a smoother polygon if so desired. Ideally there would be some visual inspection to determine whether the first K which determines the hull is sufficient, or whether an increased K gives a more pleasing result.
When to compute the hull of a set of points?
The time to compute the hull starting with K =3 increases fairly linearly with the number of input points. However other factors do affect the absolute running time. Because of these factors, one dataset of n points will not compute in the same time as another set of n points.
What does K = 3 mean for a hull?
When K =3 is used by the k -nearest neighbour search it means the three closest points to any test point are found. Too small a K means an enclosing hull doesn’t get found. Too large a K might mean important concavities in the hull are smoothed over.