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

Subject: Re: [boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2012-05-22 15:51:35

Hi Luke,

Simonson, Lucanus J wrote:
> I guess it depends on whether the user wants to traverse the 
> voronoi diagram data structure as the input to their algorithm 
> or copy it over to their own graph data structure.  I tend to 
> think that copying to their own data structure will be pretty 
> common.  It looks like the user can look up the input site for 
> each cell in your voronoi_cell data structure.  If they hash or 
> map the site to whatever data they want associated with the site 
> they can at least make the association between the voronoi diagram 
> and its input.  Unless there is a compelling reason I'd suggest 
> just removing the user data interface.  As you mentioned, the user 
> can always roll their own voronoi diagram data structure to use with 
> the voronoi builder that they can extend with whatever additional 
> data they want.

I find these comments pretty surprising considering the background of 
Boost.Polygon; as I recall, the rationale for its design was that its 
algorithms could be adapted to work with whatever "legacy" data 
structures the user was already using.  Now in this case, your view 
seems to be that the user can copy from their existing data structures 
into Andrii's input data structure, run his algorithm, and then copy 
from his output back into their existing structure, with some extra 
hashmaps thrown in to tie all these multiple copies of the data together.

For the example that I posted before, I just needed to record the 
altitude of each point and an enum for the kind of each edge.  In a 
memory-constrained environment with a large data set, it would be much 
better to have just a single copy of this data with minimal extra 
overhead.  In principle, I could have N * 80 bytes per vertex, sort it 
in-place, then O(sqrt(N)) temporarily for the beach line, and O(N) 
storage for the edges (2*sizeof(size_t) per edge, if they're vertex 
indexes).  I think that's at least quadrupled by your suggestion.

Regards,  Phil.