Vorosweep: A Fast Approximate Generalized Voronoi Diagram generator.

Thibaud Mouton and Eric Bechet
Version 0.1
Release Date: Sept 29, 2014

What is Vorosweep ?
Vorosweep is an algorithm written in C++ which is the reference implementation of a generalized Voronoļ diagram algorithm in two dimension. This algorithm consists in a sweep of the plane by a wavefront from each generator sites associated to an arbitrary convex metric.

To generate a diagram, a set of data points in 2d is given. These points are preprocessed into a hashing data structure in such a way that collisions between wavefronts are only computed locally. As a consequence, only a limited amount of these events are finally rejected, resulting in an efficient computation of the diagram. In Vorosweep, the distance between two points is mainly not symmetrical. Indeed Vorosweep assumes that the distance between two sites is measured by using the local metric associated to the site from which the distance is measured. The class of distance functions implemented are the so called Minkowski metrics. Moreover, anisotropy and orientation can be also specified for each point site. Nevertheless, this range of metric can be easily extended.

To our knowledge, no other implementation allowing to generate a Voronoļ diagram is as flexible as Vorosweep. It can generate diagram of thousands of sites in a reasonable amount of time, let say 1000 generators per 2-3 sec on modern computers with a good accuracy.

Next developments will focus on extending the generators to approximate open and closed curves, thus increasing the range of the generalization.

The Vorosweep package can generate the data structures of the Voronoļ diagram under a triangulated description of each cell as well as graphical outputs.

Why approximate Voronoi diagrams?
Computing exact Voronoi bisector between 2 sites with very different metrics can be from hard to very hard, resulting in a high computational cost. Provided that accuracy can be specified, the approximation error can be decreased to meet the requirements of an application, thus allowing to control the tradeoff between accuracy and running time.

Conditions of Use
Vorosweep is distributed under the terms of the GNU Public License. Please also check out the copyright and license terms.

The authors make no representations about the suitability or fitness of this software for any purpose. It is provided "as is" without express or implied warranty.


System Requirements
Compiling Vorosweep requires an ANSI C++ compiler. It has been successfully compiled and run Linux 3.x platforms using the g++ compiler version 4.9. No compilation test have been made so far under Windows platform.

How can I do with Vorosweep ?
You have to be aware that Vorosweep is still at its early development stage and is not yet stabilized. A number of nasty bugs are still present in the code and crashes can occur frequently. But we are working on it and we are expecting to often release more and more usable versions. Moreover, the datastructure that vorosweep produces is still rather poor. But the more enthusiastic you will be and the fastest things will progress, so do not hesitate to ask for new features.

How can I get Vorosweep anyway ?
The latest version of Vorosweep can be downloaded here.

Questions/Comments?
If you have questions or comments, please email them to Thibaud Mouton : thibaud (dOt) mouton (aT) gmail (Dot) com.

Acknowledgments
We would like to thank the potential user's of Vorosweep who would make contributions in the form of suggestions and finding bugs. We would also like to acknowledge the support of the Walloon region of Belgium under grants 1017074 DOMHEX.


Last updated on Oct 2, 2014.