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.
|