Header menu link for other important links
X
Algorithm for computing positive α-hull for a set of planar closed curves
Published in Elsevier Ltd
2015
Volume: 51
   
Pages: 125 - 135
Abstract
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) 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. © 2015 Elsevier Ltd.
About the journal
JournalData powered by TypesetComputers and Graphics (Pergamon)
PublisherData powered by TypesetElsevier Ltd
ISSN00978493
Open AccessNo
Concepts (13)
  •  related image
    Computational geometry
  •  related image
    Directed graphs
  •  related image
    Graphic methods
  •  related image
    Triangulation
  •  related image
    CONSTRAINT EQUATION
  •  related image
    CURVED BOUNDARY
  •  related image
    DELAU-NAY TRIANGULATIONS
  •  related image
    DIRECTED CYCLIC GRAPHS
  •  related image
    POSITIVE ALPHA HULL
  •  related image
    Running time
  •  related image
    Time complexity
  •  related image
    Voronoi diagrams
  •  related image
    Computational complexity