Header menu link for other important links
X
Computation of voronoi diagram of planar freeform closed convex curves using touching discs
Published in IEEE Computer Society
2013
Pages: 361 - 368
Abstract
Voronoi diagram (VD) is an extensively studied geometric entity since it has applications in fields such as computer graphics, computer vision, geometric modeling etc. In this paper, an algorithm for computing the VD of a set of planar freeform closed convex curves has been developed, without approximating the curves using points or lines. Algorithms for VD predominantly lie on computing the bisectors, a geometrically complex and a high degree curve even for inputs of low degree. Hence, a lot of processing is required to compute bisector segments that contribute to VD as well as in the computation of branch points. In this paper, it has been shown that computation of a branch point is possible without first computing either the bisector or segments of it. The algorithm uses the minimum antipodal discs (MADs) for all pairs of curves. Three touch discs (TTD) (circles touching three curves) are computed only for a specific set of three curves. Decision criteria for a TTD to become a branch disc (BD, i.e. empty TTD) have been addressed without using explicit curve containment check. Local computations of Voronoi segments are then done. The algorithm gives all branch points via centers of the branch discs along with the segments of curves that will contribute to VD. Results of implementation are provided along with analysis of the algorithm. © 2013 IEEE.
About the journal
JournalData powered by TypesetProceedings - 13th International Conference on Computer-Aided Design and Computer Graphics, CAD/Graphics 2013
PublisherData powered by TypesetIEEE Computer Society
Open AccessNo
Concepts (10)
  •  related image
    Algorithms
  •  related image
    Computational geometry
  •  related image
    Computer aided design
  •  related image
    Graphic methods
  •  related image
    ANTIPODAL DISTANCE
  •  related image
    BISECTORS
  •  related image
    FREE FORM CURVE
  •  related image
    TOUCHING DISC
  •  related image
    Voronoi diagrams
  •  related image
    Computer graphics