VRONI: Voronoi Diagrams of Points, Segments and Circular Arcs in 2D

In an editorial, Fortune wrote that "it is notoriously difficult to obtain a practical implementation of an abstractly described geometric algorithm". According to my personal experience this remark is particularly true for the implementation of Voronoi diagrams (VDs) of line segments and circular arcs.

This page shows Voronoi diagrams generated by my Voronoi code, VRONI. My code is reliable and efficient, and it can cope with any form of polygonal input data, be it clean or not. The design and implementation of VRONI is based on the following four corner stones:

Sugihara and Iri's topology-oriented approach;
a very careful implementation of the numerical computations required;
an automatic relaxation of epsilon thresholds; and
a multi-level recovery process combined with desperate mode.

The algorithm was implemented in ANSI C, based on standard floating-point arithmetic. (Recently, it was ported to C++ and made thread-safe.) The concept of desperate mode has been borrowed from my triangulation code FIST. To my knowledge, VRONI is the first code for computing Voronoi diagrams of points, line segments and circular arcs which is both reliable and fast. The handling of circular arcs is joint work with Stefan Huber: We developed the ArcVRONI extension which allows VRONI to handle genuine circular arcs without approximation. That is, VRONI can compute Voronoi diagrams of true arcs, with genuine conic arcs as bisectors.

Based on the Voronoi diagram, VRONI can also compute offset patterns or perform buffering. (See my WWW pages on pocket machining for an application of Voronoi-based offsetting.) Since VRONI computes a Voronoi diagram of points as its first stage, the code also supports the reliable computation of point Voronoi diagrams and of Delaunay triangulations. A recent extension can compute a maximum inscribed circle and can extract a (weighted) medial axis transformation (wMAT) from the Voronoi diagram. The code has been tested on polygonal and curvilinear datasets containing up to several milion points, segments and/or arcs.

As stated above, VRONI is able to compute (families of) offset curves that consist of straight-line segments and circular arcs. Of course, those offset curves may form the basis for a machining tool path. However, assembling those offset curves into a "decent" tool path is left to the user. Depending on what "decent" means this may be trivial or difficult. Since VRONI is used heavily in the CAD/CAM industry, I conclude that it is not horribly difficult to implement a machining algorithm on top of VRONI. Similarly, I know that VRONI has been included successfully into GIS packages for computing buffer zones, doing distance analysis, or computing the nesting order ("contour tree") of contours.

I appreciate your interest in VRONI. Still, VRONI creates quite a bit of email traffic, and you would save yourself and myself time by not asking whether VRONI can do anything in addition to what is described above. Let me clearly state that

VRONI is no ready-to-use fully featured CNC machining package;
VRONI does not output G-code;
VRONI does not compute feed rates for CNC machining;
VRONI does not generate mitered or purely polygonal offsets (except in the interior of a convex shape);
VRONI cannot triangulate a polygon; see my tesselation code "FIST" if you are in need of a triangulation routine;
VRONI does not compute a constrained Delaunay triangulation (CDT); and
there is no "simple" way to extend VRONI to make it handle 3D data.

Thank you for your understanding of the limitations of VRONI.

The source codes for VRONI and ArcVRONI are available for both academic and commercial use. Indeed, VRONI has been in wide-spread use, both commercially and within academic research projects. Send me an email and I will let you know the details of how you could use my code. However, in order to avoid disappointment, let me warn you upfront that neither VRONI nor ArcVRONI have been released into the public domain!

Recent parts of this research were supported by the Austrian FWF Grant L367-N15.

Related publications:

M. Held, W. Mann (2011):
"An Experimental Analysis of Floating-Point Versus Exact Arithmetic".
Proc. 23rd Canadian Conf. on Computational Geometry, p. 261-266, Toronto, Canada, Aug 2011.

M. Held (2011):
"VRONI and ArcVRONI: Software for and Applications of Voronoi Diagrams in Science and Engineering".
Proc. 8th Int. Symp. on Voronoi Diagrams in Science and Engineering, p. 3-12, Qingdao, China, June 2011.

M. Held (2010):
"Analytical Computation of Arc Menisci Configuration Under Primary Drainage in Convex Capillary Cross Sections".
Computat. Geosciences, 14(2):311-317, March 2010.

M. Held, S. Huber (2009):
"Topology-Oriented Incremental Computation of Voronoi Diagrams of Circular Arcs and Straight Line-Segments".
Computer-Aided Design, 41(5):327--338, May 2009.

M. Held, R.B. Williamson (2004):
"Creating Electrical Distribution Boundaries Using Computational Geometry".
IEEE Transactions on Power Systems 19(3):1342-1347, Aug. 2004.

M. Held (2001):
"VRONI: An Engineering Approach to the Reliable and Efficient Computation of Voronoi Diagrams of Points and Line Segments".
Computational Geometry: Theory and Applications 18(2): 95-123, 2001.

VRONI has been tested on several thousands of synthetic and real-world data sets. In particular, it was run on hundreds of GIS data sets, with longitude/latitude regarded as standard x,y-coordinates. The following images show Voronoi diagrams which were computed by means of VRONI. (Click on an image icon in order to see the full-size image. The full-size images have 950x950 pixels.) Please note: all visible discontinuities are nothing but graphics artifacts - of course, the Voronoi diagram and the offsets are formed by continuous curves! (If you see truly odd graphics artifacts then, please, make sure that your browser displays the images at their original scale.) The tests were run on a Linux machine with a 3,2GHz Pentium 4 processor.

A tribute to VRONI's designer: this data consist of 4 segments and 480 (tangent-continuous) circular arcs. You may also want to have a look at some interior offsets computed by VRONI. The entire computation (of the Voronoi diagram, the medial axis, the maximum inscribed circle and all offsets) took 463 milliseconds; the Voronoi diagram itself was obtained in 381 milliseconds.

Skyline of Salzburg: This data set consists of 1,079 line segments, and the entire computation (of the Voronoi diagram, the medial axis, the maximum inscribed circle and all offsets) took 25 milliseconds. You may want to have a look at some interior offsets computed by VRONI, or at the medial axis.

MRI slice of human organs: This data set consists of 1,570 line segments, and the entire computation (of the Voronoi diagram, the medial axis, the maximum inscribed circle and all offsets) took 34 milliseconds. You may also want to have a look at some interior offsets computed by VRONI, or at the medial axis. (Data courtesy of Gill Barequet).

Mechanical part: This data set consists of 84 line segments and 134 circular arcs, and the entire computation (of the Voronoi diagram, the medial axis, the maximum inscribed circle and all offsets) took 204 milliseconds. You may also want to have a look at a family of interior offsets computed by VRONI; please note that the offsets of the arcs are genuine arcs. (Data courtesy of Markus Thoma.)

Offset pattern: This data set was generated by computing inwards and outwards offsets of a (synthetic) star-shaped polygon by means of VRONI. That family of offsets was again subjected to VRONI. It consists of 962 line segments and 898 circular arcs, and the entire computation (of the Voronoi diagram and the medial axis) took 2,037 milliseconds. See also a zoomed view of the input and a zoomed view of the Voronoi diagram computed.

Contour lines for tile "ss28_30" of a map of Antarctica: This data set consists of 101,045 line segments, and computing the Voronoi diagram and the medial took 3,062 milliseconds. (Data courtesy of Antarctic Digital Database of the British Antartic Survey.)

Network of the primary roads of India: This data set consists of 159,032 line segments, and computing its Voronoi diagram and medial axis took 4,598 milliseconds. (Data courtesy of the "Digital Chart of the World" project, which seems to have been taken offline.)

Hawk Creek - Yellow Medicine River Major Watershed: This data set consists of 248,987 line segments, and computing the Voronoi diagram and the medial axis took 7,111 milliseconds. (Data courtesy of Minnesota River Basin Data Center.)

Map of the Baltic Sea Region: This data set consists of 456,357 line segments, and computing its Voronoi diagram and medial axis took 11,894 milliseconds, See also a zoomed view of the area around Danemark: input, Voronoi diagram. (Data courtesy of Baltic Drainage Basin Project.)

Biarcs: Voronoi diagram of the biarc approximation of a "random" polygon generated by means of our random polygon generator RPG. This data set consists of 162 (tangent-continous) circular arcs, and the entire computation (of the Voronoi diagram, the medial axis, the maximum inscribed circle and all offsets) took 432 milliseconds. You may want to have a look at some interior offsets computed by VRONI; please note that the offsets of the arcs are genuine arcs.

Random sites: Voronoi diagram of "random" straight-line segments and circles. This data set consists of 353 circular arcs and 38 line segments, and the entire computation (of the Voronoi diagram, the medial axis, and all offsets) took 465 milliseconds. You may want to have a look at a family of offsets computed by VRONI; please note that the offsets of the arcs are genuine arcs.

file last modified: Friday, 14-Apr-2023 08:21:11 CEST