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 15:43:53

>
> We can't really change the default now because it is a documented
> interface and that would be a breaking change.

Agree.

If we overload your functions on concept type they would still need to
> register their point type by specializing the metafunction that looks up
> the concept of a given type.
> The whole point of the Polygon concept type system is to allow overloading
> of generic functions by concept type.

Sounds like a plan, I need to think about it.

This was my vision for the interfaces of voronoi.  We can compromise and
> just use the point_concept for now with the intention of extending the
> interface for line segment concepts when they are finished.

Ok. I just want to make it clear for the users that it's still possible to
use Voronoi functionality even if the point or segment class doesn't
conform to x(), y() / low(), high() access method interface. The example is
following:

struct Point {
  int a;
  int b;
};

void construct_voronoi(const std::vector<Point> &vp) {
   voronoi_builder<int> vb;
   voronoi_diagram<double> vd;
   for (std::vector<Point>::iterator it = vp.begin(); it != vp.end(); ++it)
     vb.insert(it->a, it->b);
   vb.construct(&vd);
}

So at the moment one will need to use voronoi_builder structure to
construct Voronoi diagram instead of static methods defined in the
voronoi.hpp header in the following cases:
1) User provided point/segment class doesn't support x(), y() / low(),
high() accessor methods;
2) User provided container doesn't support forward ++ iterator.
3) User wants to configure coordinate types or predicate kernels (don't do
that! believe me you want be able to come up with smth. better).
The intention of those 3 static methods is to cover 95% of usage cases. For
the other 5% of cases it's always possible to use Voronoi builder data
structure directly. I am going to add this to the documentation as this
seems to confuse people about how parametrized and generic is the library.

I think he means he wants to supply his own point comparison and circle
> event comparison predicates rather than use the library provided ones
> because he thinks he can just use the epsilon method with floating point
> coordinates.  I don't think that is a good idea.

Totally, from my experience in algorithm competitions: while the best
non-robust algorithm will work in 99.9% of cases, there will be always the
case when it fails.

Thanks,
Andrii