[QGIS-Developer] K-neighbour concave hull algorithm

[Rudi von Staden]

Hi all,

I've been using the concave hull processing algorithm as part of a model
which iterates over species distribution data to create a basic
distribution polygon. I've found that it can produce very unexpected
outputs for certain input data, so I don't think it's a good algorithm to
use 'unsupervised'.

The results from the k-neighbour concave hull algorithm (
https://www.researchgate.net/publication/220868874_Concave_hull_A_k-nearest_neighbours_approach_for_the_computation_of_the_region_occupied_by_a_set_of_points)
are generally more pleasing and will never have strange pinches or ignored
points (although it also doesn't provide for holes). From my testing I
think the outputs correspond more to how someone would naturally
circumscribe a set of points. As such I would argue for it to be included
as one of the default algorithms.

There is an existing plugin (
https://github.com/detlevn/QGIS-ConcaveHull-Plugin) which is pretty decent
but it hasn't been updated to work with QGIS3. I've also come across a C++
implementation (
https://www.codeproject.com/Articles/1201438/The-Concave-Hull-of-a-Set-of-Points)
which seems to have a lot of optimisation advantages.

I see three options:
1. Update the plugin code and streamline it as a qgis algorithm. I'd be
happy to give this a go if there's support and I think it would be
relatively straightforward.
2. Adapt the c++ implementation and add it as a native algorithm. This
would probably have significant performance advantages, but may not be
worth the effort. I'm not that confident with C++ and would at least need a
fair amount of guidance if someone else doesn't want to take it on. I did
reach out to the developer and he'd be happy for his code to be used if it
comes to that.
3. Update the plugin for QGIS3 (or at least the parts of it that I need). I
would do this anyway if we don't proceed with either of the other options.

Any thoughts?

Rudi
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/qgis-developer/attachments/20180815/bbf43126/attachment.html>