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-05-22 20:27:50

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

  voronoi_cell(const point_type &p1,
               const point_type &p2,
               voronoi_edge_type *edge,
        any property);

private:
  point_type point0_;
  point_type point1_;
  voronoi_edge_type *incident_edge_;
  std::size_t color_;
  any property_;
};

Note that this suggestion is in addition to the color member of the output elements because association to the input objects is orthogonal to the need to store a color or otherwise modify data related to an element of the voronoi diagram during graph algorithms.

This would make the algorithm much easier to use, because as Phil rightly pointed out the use of a directory to make this association would be a total pain for the user of the library, and the need to do so will be the common case, not the exception.

Regards,
Luke