Self-Refining Mesh Algorithm to Determine the Voronoi Diagram
David Ochoa1; Joao Ferreira1
1 Universidade Federal de Santa Catarina
doi:10.20906/CPS/CILAMCE2015-0204
Resumo
The Voronoi diagram and other skeleton or centerline representations of a shape (e.g. the medial axis) are commonly used as tools that allow their transformation and analysis. In those representations the geometric information of the boundaries, usually given as an input, is substituted or complemented by a shape's centerline geometry (centerline in the case of a 2D polygon). This kind of diagram is widely used in many areas, including ecology, material sciences, computer animation, and computer-aided manufacturing. Many algorithms have been proposed to obtain the Voronoi diagram from a group of geometric elements, called sites, usually varying from the type of geometric elements that can be used (i.e. points, linear segments, curves, and patches). When used to find the centerline geometry of a given shape, the shape's boundary elements are used as sites. All the points that are nearer to a given site than any other point form that site's Voronoi region. The combination of all the geometrical boundaries of every Voronoi region forms the complete Voronoi diagram. It is important to notice that the elements (points, line segments, and patches) that compose those boundaries are always a relationship between two or more sites. The difficulty in determining a shape diagram depends on two factors: the geometric complexity of the boundary elements and the amount of elements. Therefore, using high order curves (or patches) in the boundary description will produce high order segments in the Voronoi diagram. On the other hand, a high amount of elements usually leads to a diagram formed by a higher number of distinguishable segments. In this work a self-refining mesh-based algorithm for finding every element in a Voronoi region composed of 2D shapes is presented, which has the following stages: (a) a regular mesh of the region is created, and for every cell a possibly related list of influence sites is calculated; (b) the cells with two or more related sites are subdivided into smaller cells and the process is repeated. Thi
Palavras-chave: Voronoi Diagram; Self-refining Mesh; Medial Axis; Computer-Aided Manufacturing