Polygon-based Vector Voronoi Diagram Implementation

다국어 초록 (Multilingual Abstract)

Implementing a Voronoi diagram for a set of points on a two-dimensional plane is a technique very often used for non-realistic or stylized rendering. However, looking at implementation methods of existing studies, a method of calculating Voronoi cells in a pixel-based image space is used. The implementation of the vector-based Voronoi diagram is a method that can directly express the boundary where cells meet. In the case of the pixel-based method, the boundary between Voronoi cells can be obtained through edge extraction image processing after first making it in the form of an image, and the accuracy is determined by the resolution, which is inevitably less accurate than the vector-based method. That is, the pixel-based Voronoi diagram generation method mainly calculates the Voronoi cell area and does not explicitly have data on clear boundaries. In contrast, the vector-based Voronoi diagram generation method can be said to be a highly accurate expression method because it directly includes the boundary line data of the Voronoi diagram. However, because the pixel-based implementation method is a more intuitive and easy implementation method, existing studies are using the pixel-based implementation method. In this study, we propose a method for calculating Voronoi diagrams in 3D space using polygon geometry directly at points. Both the Euclidean distance and the Manhattan distance can be used, and it is proposed to be used for the extension of the Voronoi diagram for line segments.

참고문헌 (Reference)

1 A. Secord, "Weighted Voronoi stippling" 37-43, 2002

2 D. Mould, "Stipple placement using distance in a weighted graph" 45-52, 2007

3 A. Hausner, "Simulating decorative mosaics" 573-578, 2001

4 Paul Haeberli, "Paint by numbers: abstract image representations" 24 (24): 207-214, 1990

5 Esteban A. L. Hufstedler, "Modified Voronoi Diagrams and Stippling"

6 Esteban A.L. Hufstedler, "Modified Voronoi Diagrams and Stippling"

7 Black, Paul E, "Manhattan distance, Dictionary of Algorithms and Data Structures"

8 Minkowski, H., "Geometrie der Zahlen" Teubner 1910

9 O. Deussen, "Floating points: A method for computing stipple drawings" 19 (19): 40-51, 2000

10 S. Hiller, "Beyond stippling – methods for distributing objects on the plane" 22 (22): 515-522, 2003

11 Domingo Martín, "A survey of digital stippling" 67 : 24-44, 2017

12 Worley, Steven, "A cellular texture basis function" 291-294, 1996