Algorithm for computing positive α-hull for a set of planar closed curves. (October 2015)

• Record Type: Journal Article
• Authors: Venkataraman, Vishwanath A.; Muthuganapathy, Ramanathan
• Is Part Of: Computers & graphics. Volume 51(2015)
• Page Start: 125
• Page End: 135
• Publication Date: 2015-10
• Subjects: Voronoi diagram -- Positive alpha hull -- Curved Boundaries -- Delaunay triangulation; Computer graphics -- Periodicals; 006.6
• DOI: 10.1016/j.cag.2015.05.018
• Languages: English
• ISSNs: 0097-8493

Abstract

Abstract: In this paper, the computation of positive α -hull for a set of planar closed C 1 -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 ( n 2 ) 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. Abstract : Graphical abstract: Abstract : Highlights: 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.