Algorithm for computing positive α-hull for a set of planar closed curves

• Computation for planar closed curves without sampling the curves into point-sets or polylines.
• No Voronoi diagram or Delaunay triangulation have been employed.
• Results indicate that the algorithm is amenable for implementation.
• Complexity, running time, etc. have been discussed.

In this paper, the computation of positive α-hull for a set of planar closed C1-continuous curves has been addressed without sampling the curves into point-sets or polylines. Positive α-hull, so far, has been computed only for a set of points, using the farthest Delaunay triangulation, a dual of farthest Voronoi diagram. However, Delaunay triangulation does not exist for a set of curved boundaries and the computation of Voronoi diagram for such a set is still a topic of active research. The key insight behind our algorithm is to merge adjacent pairs of curves on the convex hull into a set of triplets. Along with a directed-cyclic graph and a R-List (list of radii), α-neighbours are derived. Using the constraint equations, α  -discs are then computed. The algorithm is first provided for convex non-intersecting closed curves, but later explained how it can be generalized for non-convex curves. We show that the algorithm has time complexity of O(n2)O(n2) time where n is the number of curves, which leads to a practical implementation with a reasonable running time in seconds for a few dozen curves. By directly operating on the curves, our method is both robust and accurate thus avoiding the problems that arise on polyline/point-set approximations of the curve networks.

Figure optionsDownload high-quality image (120 K)Download as PowerPoint slide