orange3-text icon indicating copy to clipboard operation
orange3-text copied to clipboard
verified publisher icon biolab

[FIX] Reimplement concave hull

Open PrimozGodec opened this issue 3 years ago • 1 comments

Issue

Current concave hull search implementation (required for annotator) is occasionally missing points (some points stay out of the cluster) and is dependent on the DBSCAN's parameter (which is not sufficient for GMM clustering)

Description of changes

Reimplement concave hull with modified k-nearest neighbour implementation. The implementation is made based on the KNN method described in https://repositorium.sdum.uminho.pt/handle/1822/6429 and is modified so that it does not need an initial k and speedup is made in the incrementation of k when it is too small (replaced by bisection)

Includes
  • [X] Code changes
  • [X] Tests
  • [ ] Documentation

PrimozGodec avatar May 11 '22 15:05 PrimozGodec

We discussed reimplementing this functionality with the concept of alpha-shapes using the Shapely and alphashape libraries. If alphashape takes too long to find a good alpha value, we can reimplement this search. Otherwise, we can reimplement the entire procedure using Shapely (example - https://gist.github.com/dwyerk/10561690)

thocevar avatar Jun 03 '22 10:06 thocevar

@thocevar I finally found some time to finish this one. Now it is ready for review.

PrimozGodec avatar Feb 23 '23 10:02 PrimozGodec