Minimum enclosing polygons for point clusters

Asked Jul 26 '21 at 04:20

Active Jul 27 '21 at 07:53

Viewed 53 times

I am trying to find an algorithm that can create minimum enclosing polygons from a set of points. The existing algorithms such as. Convex Hull, Concave Hull (both Alpha shapes and K nearest Neighbors), Delaunay Triangulations do not work well for some of the point clusters as shown in the image. Existing algorithms in the Processing Toolbox do not work for the sample data that I have attached.

Another suggestion was to use "Points to Path" algorithm and convert the results to Polygon. That works only if the points are in order. For point groups created using clustering, this doesn't work.

Would prefer a QGIS or Python solution.

Link to sample data points.gpkg

edited Jul 27 '21 at 07:53

asked Jul 26 '21 at 04:20

spatialthoughts

6,106
28
49

2

I think you also forget to mention the "Concave hull (alpha shapes)" and the "Concave hull (k-nearest neighbor)", did not you? Check this thread: Creating polygon around set of points using PyQGIS. – Taras Jul 26 '21 at 05:13
for python, https://stackoverflow.com/a/57378168/9326457 https://pypi.org/project/alphashape/ – AMA Jul 26 '21 at 07:26
I tried both alpha shapes and k-nearet neighbors, but the result is still not ideal (it gives the same as convex gull). I did a batch process with multiple parameters but none give the result as the 'desired polygon'. Updated the question with a link to the sample data. – spatialthoughts Jul 27 '21 at 07:48

Minimum enclosing polygons for point clusters

0 Answers0