Use point set to shape mapping to improve polygon annotation widget

[ibayer]

Motivation

The polygon annotation widget nbs/01d_polygon_canvas.ipynb #5 (not yet included in the public github release) supports only sequential polygon annotation. Adding additional boundary points after creating an initial polygon depends on the creation order of the boundary points which is not very intuitive and also slow to execute.

Defining the polygon by a set of points instead of a list would make adding and removing of points much simpler.

Alpha-Concave Hull

In computational geometry, an alpha shape, or α-shape, is a family of piecewise linear simple curves in the Euclidean plane associated with the shape of a finite set of points. They were first defined by Edelsbrunner, Kirkpatrick & Seidel (1983). The alpha-shape associated with a set of points is a generalization of the concept of the convex hull, i.e. every convex hull is an alpha-shape but not every alpha shape is a convex hull.
source: https://en.wikipedia.org/wiki/Alpha_shape

Alpha-Concave Hull [0] is one such algorithm that could be interested for us.

Suggested steps.

• literature review to find simple algorithm to associate shape with set of points.
• poc implementation of algorithm in 01d_polygon_canvas.ipynb
• create minimal sequence diagram https://plantuml.com/sequence-diagram to specify expected user iteration for creating and deleting points
• refactor current polygon annotation widget to support the new algorithm

[0] Alpha-Concave Hull, a Generalization of Convex Hull

Note: This is an internal issue till the polygon annotation widget #5 is released.

[ibayer]

Concave hull algorithms with pseudo code

• Moreira, A. and Santos, M.Y., 2007, Concave Hull: A K-nearest neighbors approach for the computation of the region occupied by a set of points PDF
  • python implementation: https://github.com/sebastianbeyer/concavehull
  • blog discussion + reference to python implementation https://towardsdatascience.com/the-concave-hull-c649795c0f0f
• Duckham, Matt, et al. "Efficient generation of simple polygons for characterizing the shape of a set of points in the plane." Pattern recognition 41.10 (2008): 3224-3236. PDF
  • https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.Delaunay.html

The k-NN approach seems simpler to implement.

• also interesting (at least for testing) but a bit heavy as dependency "Toolbox for generating n-dimensional alpha shapes." https://github.com/bellockk/alphashape
• related discussion: https://stackoverflow.com/questions/83593/is-there-an-efficient-algorithm-to-generate-a-2d-concave-hull