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-05-23 14:32:25

On Wed, May 23, 2012 at 2:27 AM, Simonson, Lucanus J <
lucanus.j.simonson_at_[hidden]> wrote:

> >Assuming some data associated with the original sites there is no way to
> make that association directly to the output cells with the current voronoi
> diagram algorithm.
> >To get the altitude for the points annotated onto the voronoi diagram you
> would need to look them up in a directory.
> >You could use binary search in a sorted vector of input sites as the
> fastest, lowest memory directory data structure.
> >The cost of that lookup would be dominated by the sweepline algorithm.
> >Carrying properties of the input through to the output is something we
> have thought about, but we haven't come up with a generic solution.
> >It is a separate concern from the void* member of the output data
> structure.
>
> Replying to my own email here...
>
> We could provide a Boost.Any based overload for insert:
>
> template <typename site_type>
> voronoi_builder::insert(const site_type& site, any property);
>
> template <typename site_type>
> voronoi_builder::insert(const site_type& site) {
>        insert(site, any());
> }
>
> and carry the any value through the algorithm to the output cell
> associated with the site.  The same think would be applicable to
> generalized line segment intersection, which we are laying the groundwork
> for reimplementating soon.  Both algorithms have a strong need for carrying
> through of input properties to output data structures, and a type safe
> generic solution that is consistent between the two would be highly
> desirable.  In the case of line segment intersection we would need to
> represent overlapping sub segments by duplicate output segments each
> carrying the property of the input segment it is derived from.
>
> The dependency on Boost.Any would be highly intrusive into the core
> algorithm, but we can template it so that the dependency is explicit only
> at the interface and under the hood it is just a T with value semantics
> that gets copied eventually into the output data structure.  The output
> voronoi_cell type would then be expected to have a member that is an (any)
> named property and the constructors would then need to accept an (any) as
> an additional parameter.
>

I would like to keep voronoi_builder data structure as pure computational
geometry algorithm implementation that is decoupled from the input and
output.
It's not responsibility of voronoi_builder to support data association, it
should operate just with a geometry primitives by their coordinates, not
concepts. The concept customization is achieved using public static methods
in voronoi.hpp header that retrieve coordinates of the input objects. It is
responsibility of the output object builder (voronoi_diagram_builder) to do
mapping to the initial input set and voronoi_builder can just provide
enough information (like indexes in the previous post) to simplify this
procedure.

Regards,
Andrii