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

Subject: Re: [boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2012-04-11 19:36:40

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

You don't need to explain to me about what the epsilon method is.  No, it does not work well for either integer or floating point based computational geometry.  We didn't go to the effort of making voronoi numerically robust because we didn't understand how easy it would be to just use a tolerance in our floating point comparisons.  We did it because we understand in detail exactly why epsilon method is a bad idea, exactly what invariants would be violated and exactly what input conditions will lead to a crash or incorrect output.  Please just drop it.

>The question concerning search and update operations can be reduced to the
>following:
>Does this VD support incremental insertion of a new cell?

No, this is not an incremental update VD algorithm.  It is sweepline based.  Incremental update could be implemented on top of the vornoi diagram data structure and would require roughly constant factor cost to insert a new site if you knew which cell you were inserting the site into since updates would only need to be made local to the insertion site.  Locating the insertion site would in theory be O(log n) if you used a spatial index to accelerate it.  We might consider it as a future enhancement.

Regards,
Luke