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

Subject: Re: [boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library
From: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2012-04-11 18:45:22

Vadim wrote:
> >> With the right choice of predicates points using floating data types
> will
> >> be supported too.
>
> Andrii wrote:
> >Not sure, what you mean by "predicates points". Could you explain with an
> example?
>
> 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.
>
> Is it practical to use floating point coordinates with an epsilon method
> and have non-robust algorithm when you could snap to integer coordinates
> with rounding error less than your epsilon and get a robust algorithm with
> no significant runtime overhead?
>
>
 Yes, this is correct clarification.

 The simplest point predicate is just lexicographical compare using x and y
coordinates of two points. In theory, without tolerance points are
infinitely small and lines are infinitely thin. Tolerance parameter makes
points and lines "thick".  Such point predicates can be made problem
specific.  They work well both for integral and floating data types of
coordinates.  This is why I am suggesting to generalize your algorithm if
this is not too costly.

The question concerning search and update operations can be reduced to the
following:

Does this VD support incremental insertion of a new cell?

if yes, what is the computational cost?

If no,  does insertion of new cell require re-building the whole VD?

Regards,

Vadim Stadnik