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

Subject: Re: [boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library
From: Jeffrey Lee Hellrung, Jr. (jeffrey.hellrung_at_[hidden])
Date: 2012-05-20 05:16:12

On Sun, May 20, 2012 at 1:25 AM, Andrii Sydorchuk <
sydorchuk.andriy_at_[hidden]> wrote:

> >
> > Can you clarify this? This sounds like something which could be policy
> > driven via a template parameter rather than specified globally via a
> macro,
> > but I'm not really sure what you're referring to.
>
>
> To clarify things a bit:
>
> Voronoi diagram data structure contains three arrays of: Voronoi vertices,
> Voronoi edges, Voronoi cells:
> http://svn.boost.org/svn/boost/trunk/boost/polygon/voronoi_diagram.hpp.
>

It'll take me some time to parse through that :) But I do have some
comments based on your descriptions and rationale below.

All thee data structures that represent vertex/edge/cell are interconnected
> via pointers to each other.
>
> Apart from topology information it's usually useful to be able to associate
> some information with the primitive (vertex/edge/cell).
> At the moment this is implemented via mutable void pointer, thus
> simplifying template interface for the above data structures

Doesn't Boost.Graph have something similar via Boost.PropertyMap? I'm not
very familiar with Boost.Graph so I'm completely guessing here :/ But, at
least, it sounds similar to the problem that Boost.PropertyMap is trying to
address (IIRC, it's been a while since I've gone through the documentation).

As discussed previously on this list, such a pointer adds additional memory
> overhead in case user is not associating any data with Voronoi primitives.
> That's why I added compile time directives to disable data field at compile
> time.
>

Well, that makes it difficult for 2 different uses of the Voronoi
algorithms, one which has additional data and one which doesn't, to coexist
within the same application, right?

> Making this data field as a template parameter, would add additional
> complexity to those data structures.
>

It would seem to me that the marginal additional complexity would be low,
but I admit I just glanced through the linked hpp so I don't know how much
complexity already exists.

Also it would imply circular dependency as each of the Voronoi structures
> needs to know the type of the others two (and they could have different
> type of data associated with them).
>

I can see this maybe being nontrivial to work out clearnly. Is it possible
to use derivation to your advantage here? E.g., each vertex structure, with
some template parameter controlling its associated data, inherits from a
common base class, and the other structures contain pointers to this base
class.

> Plus it wouldn't solve the issue with memory overhead if this member is not
> required.
>

Well I don't necessarily mean to literally have the member be a template
parameter, but rather, e.g., use (a) (partial) specialization or (b) use
boost::compressed_pair and default the data type to be an empty struct.

Those are the reasons I consider the mutable void* data member enclosed
> into precompiler directives to be a better design.
>

It seems to me like the inability to use both options within the same
application is a serious restriction. Do you consider that not a realistic
use case?

Also, please pardon any glaring ignorance on my part as I'm not familiar
with this additional component to Boost.Polygon!

Andrii
>

- Jeff