Re: [boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library

Subject: Re: [boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library
From: Andrii Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2012-04-11 12:24:33

Hi Vadim,

> The question concerning fully constructed Voronoi diagram as well as
> Delaunay triangulation:

"find the nearest neighbor" - for a particular Voronoi cell this could be
done in a constant time that depends on the number of Voronoi cell
neighbors. You could also compute and store this data for all the sites
within the diagram in O(N) time once the Voronoi diagram is constructed (N
is total number of input geometries).

"insert/erase a vertex" - You mean insertion / removal of vertices from the
resulting Voronoi graph, am I right? Or insertion of a new input geometries
that will require to rebuild Voronoi diagram?

How long, do you think, it can take to parameterize types of coordinates,
> points and point predicates?

Coordinate type is already parametrized via coordinate type traits of
Voronoi builder.
There is no such thing as point parametrization right now. Everything that
has x() and y() method will work as a point.
Predicates parametrization is already available via template parameter of
the Voronoi builder. However I don't think that somebody will use this.
Default Voronoi predicate kernel was designed in such a way that it
operates with exact predicates at almost no cost for using them. Sounds
like a magic, but that's true :-).

The thing is that default static methods available in the voronoi.hpp
header are not parametrized with any coordinate type traits or predicate
kernels. This is made intentionally as in most cases this is not required:
http://svn.boost.org/svn/boost/sandbox/gtl/doc/voronoi_advanced_tutorial.htm.
In case you really need those you should go for the Voronoi_builder data
structure that is completely configurable, (this is also covered in the
advanced tutorial).

The benefits of the generalized algorithm are quite significant. Many
> existing libraries can use this algorithm either directly or with minimal
> adaptation. The parameterization of point predicates is quite important.
> For example, in practice, tolerance based predicates are very good
> alternative to multi and adaptive precision methods.

The library is already fully generalized except input point and segment
types. But we are going to resolve this soon.

With the right choice of predicates points using floating data types will
> be supported too.

Not sure, what you mean by "predicates points". Could you explain with an
example?

Thanks,
Andrii