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 17:04:45

Phil Endecott wrote:

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

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.

Given that we require sorted input for the sweepline, but don't require sorted input at the interface we make a copy and sort.  The sort should be dominated by the sweepline and the copy dominated by the size of the output data structure.  The user can always declare their own output data structure that conforms to the expectations of the voronoi builder's template parameter, including one that directly constructs the delauney triangulation (of points) rather than going through the intermediate step of voronoi diagram.  The copy at the output at least can be eliminated, but I don't expect that to be the common usage.

Regards,
Luke