bodhisattwa-chakraborty/Concave​_Hull_Generation

Concave hull generation using KNN approach

This program generates a concave hull (an envelope surrounding the point data set) around any two-dimensional data set. The algorithm uses K-nearest neighbour approach to compute the concave hull. This approach is based on the paper "CONCAVE HULL: A K-NEAREST NEIGHBOURS APPROACH FOR THE COMPUTATION OF THE REGION OCCUPIED BY A SET OF POINTS," GRAPP 2007 - International Conference on Computer Graphics Theory and Applications, pp. 61-68, 2007, by Adriano Moreira and Maribel Yasmina Santos. (http://repositorium.sdum.uminho.pt/bitstream/1822/6429/1/ConcaveHull_ACM_MYS.pdf). The convex hull is being computed using Matlab inbuilt 'convhulln' function. A comparative analysis based on the area covered by the convex and concave hull and the run time for each method is also presented. The 'degree of concaveness' is calculated based on the difference between the convex hull and concave hull.