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

[Andrii Sydorchuk]

I would like to update the inclusion status.

At the moment library passes all the major tests on trunk:
http://www.boost.org/development/tests/trunk/developer/polygon.html

It's also possible to use voronoi edge/cell/vertex structures without data
member if this is considered as significant memory overhead.
This is supported via precompiler directives: NO_VORONOI_VERTEX_DATA,
NO_VORONOI_CELL_DATA,
NO_VORONOI_EDGE_DATA.

If there are no other major comments, I would like to update Polygon
library for the upcoming Boost release.

Regards,
Andrii

>

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Jeffrey Lee Hellrung, Jr.]

On Sat, May 19, 2012 at 11:09 PM, Andrii Sydorchuk <
sydorchu...@gmail.com> wrote:

> I would like to update the inclusion status.
>
> At the moment library passes all the major tests on trunk:
> http://www.boost.org/development/tests/trunk/developer/polygon.html
>
> It's also possible to use voronoi edge/cell/vertex structures without data
> member if this is considered as significant memory overhead.
> This is supported via precompiler directives: NO_VORONOI_VERTEX_DATA,
> NO_VORONOI_CELL_DATA,
> NO_VORONOI_EDGE_DATA.
>

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.

> If there are no other major comments, I would like to update Polygon
> library for the upcoming Boost release.
>
> Regards,
> Andrii
>

- Jeff

[Andrii Sydorchuk]

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

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

Making this data field as a template parameter, would add additional
complexity to those data structures.
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).
Plus it wouldn't solve the issue with memory overhead if this member is not
required.
Those are the reasons I consider the mutable void* data member enclosed
into precompiler directives to be a better design.

Andrii

[Jeffrey Lee Hellrung, Jr.]

On Sun, May 20, 2012 at 1:25 AM, Andrii Sydorchuk <
sydorchu...@gmail.com> 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

[Phil Endecott]

Andrii Sydorchuk wrote:
> 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

This void* "user data" thing is something that I commented on before.
It struck me as a rather old-school "C" way of doing things. If this
contribution had been subject to a full review as a new library I
believe it would not have been accepted in this form. I see it as a
weakness of the Boost process that this has "slipped through", i.e. we
have different rules for additions to existing libraries even when they
are by different authors and have little or no dependency on the
existing work.

Having briefly experimented with Andrii's code, I have since them
implemented an incremental constrained Delaunnay triangulation using
Boost.Graph. This has some problems of its own, but it neatly solves
the issue of per-vertex or per-edge user data via template parameters.

Andrii, your work has many good points including performance and
correctness. To be really great, in my view it would benefit from
some attention to issues like this one.


Regards, Phil.

[Simonson, Lucanus J]

>Making this data field as a template parameter, would add additional complexity to those data structures.
>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).
>Plus it wouldn't solve the issue with memory overhead if this member is not required.
>Those are the reasons I consider the mutable void* data member enclosed into precompiler directives to be a better design.

Provided that you make the type of the other two template parameters there is no problem with circular dependency. You must forward declare, of course.

If you make the template parameter for the extra data default to void and make the template parameters for the other two voronoi graph types default then you can make the three types template parameters of voronoi_diagram defaulting to their instantiation with void. This means that you pretty much have to propagate the template parameter through all the code, but it is zero cost if you instantiate with void and would eliminate the macro and error prone void* pointer semantics.

Regards,
Luke

[Simonson, Lucanus J]

>Andrii Sydorchuk wrote:
>> 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

Phil Endecott wrote:
>This void* "user data" thing is something that I commented on before.
>It struck me as a rather old-school "C" way of doing things.
>If this contribution had been subject to a full review as a new library I believe it would not have been accepted in this form.
>I see it as a weakness of the Boost process that this has "slipped through", i.e. we have different rules for additions to existing
>libraries even when they are by different authors and have little or no dependency on the existing work.

Nothing has slipped through. It isn't on the release branch yet. The reason we are talking about it on the list is to get feedback for changes the community would like to see made before it is released.

Apparently there is already use of Andrii's core algorithm inside google, and use of metaprogramming at google is restricted. They won't use the library through the Polygon interfaces because of the MPL dependency. Presumably the void* pointer interface already has usage and Andrii may be reluctant to change it for that reason. The macro allows us to de-feature the void* pointer in boost usage without requiring a fork of the code. Alternately we can simply not document the void* interface and view it as an implementation detail for internal use in implementing voronoi based algorithms. The third option is to bite the bullet and implement the template based solution I suggested previously.

Upon reflection it seems ridiculous to recompile a complex algorithm for no good reason to make it composable with an unrelated pointer type. I typically use an index instead of a void* pointer, but I don't really see one as being much better than the other.

>Having briefly experimented with Andrii's code, I have since them implemented an incremental constrained Delaunnay triangulation using Boost.Graph.
>This has some problems of its own, but it neatly solves the issue of per-vertex or per-edge user data via template parameters.

I'd be interested in learning more about this. Are you willing to share the code or at least expand a little on your description?

Regards,
Luke

[Steven Watanabe]

AMDG

On 05/20/2012 05:17 PM, Simonson, Lucanus J wrote:
>
> Upon reflection it seems ridiculous to recompile a complex algorithm for no good reason to make it composable with an unrelated pointer type. I typically use an index instead of a void* pointer, but I don't really see one as being much better than the other.
>

One solution is to wrap/unwrap the void* around
the algorithm, so that the implementation sees
void*, but the user sees whatever his real type is.
Not having looked at the interface in question at
all, I don't know whether this technique is applicable,
but it's something to think about.

In Christ,
Steven Watanabe

[Andrii Sydorchuk]

On Sun, May 20, 2012 at 11:16 AM, Jeffrey Lee Hellrung, Jr. <
jeffrey....@gmail.com> wrote:

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

I could probably miss something about Boost.PropertyMap.
But it doesn't look different from using a hash table to associate data.

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

If both are required, nothing stops the user from implementing the second
one.

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

I guess we try to avoid inheritance for the basic data structures, because:
1) it increases size of the data structure by a pointer to a virtual
functions table;
2) it results in a performance dropdown for the virtual function calls;
3) for this case it doesn't seem to solve design problems.

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

It could be realistic for some cases. And if it is, nothing stops the user
from providing his own voronoi diagram data structure with primitives
configuration via voronoi diagram traits.

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

I am happy to discuss any details that would improve library design.

[Andrii Sydorchuk]

On Sun, May 20, 2012 at 7:09 PM, Phil Endecott <
spam_from...@chezphil.org> wrote:

> This void* "user data" thing is something that I commented on before. It
> struck me as a rather old-school "C" way of doing things.

Correct and this is something I replied before. I'd prefer to use simple
old-school "C" way than new-school complicated "C++" way, especially if the
second one doesn't have explicit benefits.
However in case somebody has a really nice design solution, I would give up
my old-school "C" way.

> If this contribution had been subject to a full review as a new library I
> believe it would not have been accepted in this form. I see it as a
> weakness of the Boost process that this has "slipped through", i.e. we have
> different rules for additions to existing libraries even when they are by
> different authors and have little or no dependency on the existing work.
>

As noticed Luke, I don't see why this slipped through. I am actually
willing to discuss this and the library is not in the release.

Regards,
Andrii

[Andrii Sydorchuk]

>
> Apparently there is already use of Andrii's core algorithm inside google,
> and use of metaprogramming at google is restricted. They won't use the
> library through the Polygon interfaces because of the MPL dependency.
> Presumably the void* pointer interface already has usage and Andrii may be
> reluctant to change it for that reason. The macro allows us to de-feature
> the void* pointer in boost usage without requiring a fork of the code.
> Alternately we can simply not document the void* interface and view it as
> an implementation detail for internal use in implementing voronoi based
> algorithms.

>From the discussion raised around wrong design of the voronoi diagram data
structure I would like to stick to the one of the alternatives.

> The third option is to bite the bullet and implement the template based
> solution I suggested previously.
>

I had some thoughts about such an implementation and didn't manage to
resolve this properly. Some prototypes would be helpful.

Regards,
Andrii

[Andrii Sydorchuk]

On Mon, May 21, 2012 at 2:38 AM, Steven Watanabe <watan...@gmail.com>wrote:

> One solution is to wrap/unwrap the void* around
> the algorithm, so that the implementation sees
> void*, but the user sees whatever his real type is.
> Not having looked at the interface in question at
> all, I don't know whether this technique is applicable,
> but it's something to think about.
>

The main point is that this void* data member is not used by the algorithm
at all. And is only exposed to simplify data association with voronoi
primitives.

>From the user perspective the good practice would be to use data
access functions instead of direct class methods to retrieve associated
data:

template <typename T>
UserDataType* data(const voronoi_edge<T>& edge) {
return static_cast<UserDataType*>(edge.data());
}

Regards,
Andrii

[Simonson, Lucanus J]

Andrii Sydorchuk wrote:

>The main point is that this void* data member is not used by the algorithm at all. And is only exposed to simplify data association with voronoi primitives.

Does it currently have any usage at all?

>From the user perspective the good practice would be to use data
>access functions instead of direct class methods to retrieve associated
>data:
>template <typename T>
>UserDataType* data(const voronoi_edge<T>& edge) {
> return static_cast<UserDataType*>(edge.data());
>}

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.

Regards,
Luke

[Jeffrey Lee Hellrung, Jr.]

On Mon, May 21, 2012 at 9:14 AM, Simonson, Lucanus J <
lucanus.j...@intel.com> wrote:

> Andrii Sydorchuk wrote:
>
> >The main point is that this void* data member is not used by the
> algorithm at all. And is only exposed to simplify data association with
> voronoi primitives.
>
> Does it currently have any usage at all?
>
> >From the user perspective the good practice would be to use data
> >access functions instead of direct class methods to retrieve associated
> >data:
> >template <typename T>
> >UserDataType* data(const voronoi_edge<T>& edge) {
> > return static_cast<UserDataType*>(edge.data());
> >}
>
> 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 may have some suggestions on how to implement this user data, but yes,
Luke's suggestion looks to be the simplest solution. Andrii, do you have an
example use case for storing the data in situ with the voronoi primitive
objects? Looking at a concrete use case might help ground the discussion.

- Jeff

[Phil Endecott]

Simonson, Lucanus J wrote:
>>Andrii Sydorchuk wrote:
>>> 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
>
> Phil Endecott wrote:
>>This void* "user data" thing is something that I commented on before.
>>It struck me as a rather old-school "C" way of doing things.
>>If this contribution had been subject to a full review as a new library
>>I believe it would not have been accepted in this form.
>>I see it as a weakness of the Boost process that this has "slipped
>>through", i.e. we have different rules for additions to existing
>>libraries even when they are by different authors and have little or no dependency on the existing work.
>
> Nothing has slipped through. It isn't on the release branch yet. The reason
> we are talking about it on the list is to get feedback for changes the community
> would like to see made before it is released.

OK, good. My comment was based on a previous post by Andrii where he
said that you (Luke) had approved the contribution.

> Upon reflection it seems ridiculous to recompile a complex algorithm for no
> good reason to make it composable with an unrelated pointer type.

The library is already header-only, so there is plenty of "ridiculous
unnecessary recompilation" going on, as with very many other
libraries. The extra bit of recompilation occurs when there is more
than one variant in the same compilation unit. I suspect this will not
be a common use case. Anyway, despite the complexity of the algorithm
I found it to compile quickly in practice; it is not a "compiler stress
test" like some Boost things...

> I typically use an index instead of a void* pointer, but I don't really see
> one as being much better than the other.

Boost.Graph's vertex (and edge?) descriptors seem to be essentially
indexes that can be used to look up properties stored in e.g. vectors
in O(1) time.

Indexes look more type-safe than casting a void*, but I think there is
an equivalent risk of indexing into the wrong vector. I think the main
benefit of indexes is that they might not need to be stored at all,
i.e. they are implicit; if your vertices are stored in a vector you can
get the index from a pointer to the vertex by subtracting &vertices[0].

>>Having briefly experimented with Andrii's code, I have since them
>> implemented an incremental constrained Delaunnay triangulation using
>> Boost.Graph.
>>This has some problems of its own, but it neatly solves the issue of
>> per-vertex or per-edge user data via template parameters.
>
> I'd be interested in learning more about this. Are you willing to
> share the code or at least expand a little on your description?

I naively made Boost.Graph's vertices and edges correspond to vertices
and edges of the Delaunay triangulation. As a result, my code spends
most of its time studying the relative directions of edges, e.g. given
a vertex v and and edge e that is incident to v, find the two edges d
and f that are incident to v and adjacent respectively clockwise and
anticlockwise of e. This could be improved by storing the edge
incidence list ordered by direction. Better, though, would be to use a
half-edge data structure or similar where each node has explicit links
to nodes representing adjacent edges in each direction from the same
source node (as Andrii seems to have done). Boost.Graph may not be the
best starting point for either of these alternatives, though I see that
some things related to planar graphs are on the Boost.Graph to-do list.

To build a Delaunay triangulation incrementally, it's important to be
able to find the existing triangle (or edge) that contains the new
point efficiently. In my case the input data was sequences of points
with good spacial locality, so I simply used the previously-added point
as a hint for the new point and located the containing triangle in
worst-case O(N). In general, some sort of spacial index of the
triangles is needed and adds considerably to the complexity. Because
of this, I think sweep-line or similar is better than incremental
construction, unless there is some particular need for incremental.

At the top level, my code looks something like this:

// Default vertex type; user code could use a subclass of this to add
// per-vertex attributes.
struct Vertex {
typedef int coord_t;
typedef std::pair<coord_t,coord_t> point_t;
point_t pos;
};

// Default edge type:
struct Edge {
bool constrained;

Edge(): constrained(false) {}
Edge(bool constrained_): constrained(constrained_) {}
};


// A DelaunayTriangulation is-a Boost.Graph Mutable Graph; it's
templated on
// vertex and edge types (see above), and adds methods for triangulation.
template <typename VERTEX_T = Vertex, typename EDGE_T = Edge>
class DelaunayTriangulation:
public boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
VERTEX_T, EDGE_T>
{
public:
vertex_descriptor add_vertex_near_vertex(vertex_t v,
vertex_descriptor hint,
edge_t e = edge_t());

edge_descriptor add_constrained_edge(vertex_descriptor src,
vertex_descriptor tgt,
edge_t e = edge_t());

// etc.
};


Then my "application" code then subclasses from that:

struct CGVertex:
public Vertex
{
typedef int alt_t;
alt_t alt;
};

struct CGEdge:
public Edge
{
char type;
};

class ContourGraph:
public DelaunayTriangulation<CGVertex,CGEdge>
{
// etc.
};


(Note to Andrii: in another post, you object to inheritance because of
the storage of a virtual function table pointer and the speed for
virtual function indirection; note that here I'm using inheritance, but
nothing is virtual; if there are no virtual functions, there is no
virtual function table pointer or other overhead.)

I can now refer to edges and vertices using Boost.Graph's
vertex_descriptor and edge_descriptor, and lookup the CGVertex and
CGEdge objects using operator[]:

ContourGraph g;
ContourGraph::vertex_descriptor v = g.add_vertex_near_vertex(....);
g[v].alt = 42;


Anyway, back to the subject of what Andrii's code should ideally look
like: I think there is at least one other issue, namely the
voronoi_diagram_builder class (not to be confused with voronoi_diagram
or voronoi_builder!), which seems superfluous to me. I would have the
voronoi_builder call methods of the voronoi_diagram directly. Having
to mimic this in my Delaunay class just added extra typing. Any comments?


Regards, Phil.

[Andrii Sydorchuk]

On Mon, May 21, 2012 at 6:14 PM, Simonson, Lucanus J <
lucanus.j...@intel.com> wrote:

> Andrii Sydorchuk wrote:
>
> >The main point is that this void* data member is not used by the
> algorithm at all. And is only exposed to simplify data association with
> voronoi primitives.
>
> Does it currently have any usage at all?

Just in the examples (basic tutorial and voronoi visualizer). For voronoi
visualizer (Qt application to render voronoi diagrams used for testing
purposes) I use the data field pointer to mark edges as visited during
depth first search. Will expand this in more details in the next email.

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

Agree, looks like the best way to resolve this design problem is to leave
it to the user.

Regards,
Andrii

[Andrii Sydorchuk]

On Mon, May 21, 2012 at 7:33 PM, Jeffrey Lee Hellrung, Jr. <
jeffrey....@gmail.com> wrote:

> I may have some suggestions on how to implement this user data, but yes,
> Luke's suggestion looks to be the simplest solution. Andrii, do you have an
> example use case for storing the data in situ with the voronoi primitive
> objects? Looking at a concrete use case might help ground the discussion.
>

There are two examples on data association usage:

1) Basic tutorial (non-practical examples that shows how to use this
functionality):
http://svn.boost.org/svn/boost/trunk/libs/polygon/doc/voronoi_basic_tutorial.htm
Section: "Associating User Data with Voronoi Primitives".

2) Voronoi visualizer:
http://svn.boost.org/svn/boost/trunk/libs/polygon/example/voronoi_visualizer.cpp
Uses depth first search to remove Voronoi edges outside of the polygon
bounds.
The data field is used to mark edges as visited (I added some comments):

void remove_exterior(const VD::edge_type* edge) {
if (edge->data()) // visited edge, don't proceed
return;
edge->data(&edge); // mark edge as visited
edge->twin()->data(&edge); // mark twin edge as visited also
const voronoi_diagram<double>::vertex_type* v = edge->vertex1();
// if the edge doesn't have endpoint or is not primary stop
if (v == NULL || !edge->is_primary())
return;
// recursively run dfs for each Voronoi edge around current edge endpoint
const voronoi_diagram<double>::edge_type* e = v->incident_edge();
do {
remove_exterior(e);
e = e->rot_next();
} while (e != v->incident_edge());
}

While this example doesn't directly associate any data with Voronoi
edges, it shows additional usage of this field that appeared to be
practical.


Regards,
Andrii

[Andrii Sydorchuk]

On Mon, May 21, 2012 at 9:03 PM, Phil Endecott <
spam_from...@chezphil.org> wrote:
>
> if your vertices are stored in a vector you can get the index from a
> pointer to the vertex by subtracting &vertices[0].
>

We are actually going to use this information to support serialization, but
not in this release.

> Better, though, would be to use a half-edge data structure or similar
> where each node has explicit links to nodes representing adjacent edges in
> each direction from the same source node (as Andrii seems to have done).

Yes, that's exactly how the current voronoi diagram topology is
represented. So no additional evaluation is required.

> To build a Delaunay triangulation incrementally, it's important to be able
> to find the existing triangle (or edge) that contains the new point
> efficiently.

That's one of the reasons incremental algorithm is way slower than
sweepline.

> In my case the input data was sequences of points with good spacial
> locality, so I simply used the previously-added point as a hint for the new
> point and located the containing triangle in worst-case O(N).

Just to clarify: the future implementation of the Delaunay triangulation as
well as the current of the Voronoi diagram is designed to do this with O(1)
worst case complexity.

> I can now refer to edges and vertices using Boost.Graph's
> vertex_descriptor and edge_descriptor, and lookup the CGVertex and CGEdge
> objects using operator[]:
>
> ContourGraph g;

> ContourGraph::vertex_**descriptor v = g.add_vertex_near_vertex(....)**;

> g[v].alt = 42;
>

I would look closer at this approach to investigate memory/performance
overheads of such a design.
Anyway providing Boost.Graph interface for Voronoi diagram data structure
is something that could be added within the future releases.
And could coexist with the current implementation (without data member).
Will you agree?

It would be still easy to expand current interface for an additional data
member (plus configuring voronoi diagram traits):

template <typename T, typename Value>
class voronoi_edge_with_data : voronoi_edge<T> {
public:
const Value& data() const { return value_; }
...
private:
Value value_;

};


> Anyway, back to the subject of what Andrii's code should ideally look
> like: I think there is at least one other issue, namely the
> voronoi_diagram_builder class (not to be confused with voronoi_diagram or
> voronoi_builder!), which seems superfluous to me. I would have the
> voronoi_builder call methods of the voronoi_diagram directly. Having to
> mimic this in my Delaunay class just added extra typing.

If everybody else agrees that this is superfluous than I am going to remove
it. However my arguments on such a design are following:
1) it splits construction and functionality of an object;
2) it hides construction methods from the user;
3) it represents implementation of the classical builder pattern (
http://en.wikipedia.org/wiki/Builder_pattern):
voronoi_builder (director), voronoi_diagram_builder (concrete builder),
voronoi_diagram (product).

Any comments?
>

Would you agree that without a data field member current implementation of
the Voronoi diagram is worth of the release?

Regards,
Andrii

[Simonson, Lucanus J]

Andrii Sydorchuk wrote:

>There are two examples on data association usage:
>1) Basic tutorial (non-practical examples that shows how to use this
>functionality):

>2) Voronoi visualizer:

>Uses depth first search to remove Voronoi edges outside of the polygon bounds.
>The data field is used to mark edges as visited (I added some comments):

>While this example doesn't directly associate any data with Voronoi edges, it shows additional usage of this field that appeared to be practical.

The objection to void* is a style objection. I think if you made the field an int (preferably std::size_t ) then you could name it color instead of data and it would be clear it was intended for graph algorithms. As a std::size_t it would be usable as an index into a vector of arbitrary type to allow complex data to be associated with the graph elements in O[1] time for more complex use cases. That way you preserve the ability to implement graph algorithms directly on the data structure and can update your example without needing to declare your own classes.

Regards,
Luke

[Andrii Sydorchuk]

>
> The objection to void* is a style objection. I think if you made the
> field an int (preferably std::size_t ) then you could name it color instead
> of data and it would be clear it was intended for graph algorithms. As a
> std::size_t it would be usable as an index into a vector of arbitrary type
> to allow complex data to be associated with the graph elements in O[1] time
> for more complex use cases. That way you preserve the ability to implement
> graph algorithms directly on the data structure and can update your example
> without needing to declare your own classes.

This actually sounds pretty good to me.

So now we have two possible solutions:
1) removing data field member completely;
2) substitute it with size_t color member.

I am satisfied with both solutions (the second one is more flexible as it
allows to execute graph algorithms directly).

Regards,
Andrii

[Phil Endecott]

Andrii Sydorchuk wrote:

> On Mon, May 21, 2012 at 9:03 PM, Phil Endecott wrote:
>> I can now refer to edges and vertices using Boost.Graph's
>> vertex_descriptor and edge_descriptor, and lookup the CGVertex and CGEdge
>> objects using operator[]:
>>
>> ContourGraph g;

>> ContourGraph::vertex_descriptor v = g.add_vertex_near_vertex(....);

>> g[v].alt = 42;
>>
>
> I would look closer at this approach to investigate memory/performance
> overheads of such a design.
> Anyway providing Boost.Graph interface for Voronoi diagram data structure
> is something that could be added within the future releases.

It would be an interesting test of the Boost.Graph concepts to see if
they fit a half-edge or dart or similar planar graph representation.
Maybe some Boost.Graph experts could comment on this.

>> Anyway, back to the subject of what Andrii's code should ideally look
>> like: I think there is at least one other issue, namely the
>> voronoi_diagram_builder class (not to be confused with voronoi_diagram or
>> voronoi_builder!), which seems superfluous to me. I would have the
>> voronoi_builder call methods of the voronoi_diagram directly. Having to
>> mimic this in my Delaunay class just added extra typing.
>
> If everybody else agrees that this is superfluous than I am going to remove
> it. However my arguments on such a design are following:
> 1) it splits construction and functionality of an object;
> 2) it hides construction methods from the user;
> 3) it represents implementation of the classical builder pattern (
> http://en.wikipedia.org/wiki/Builder_pattern):
> voronoi_builder (director), voronoi_diagram_builder (concrete builder),
> voronoi_diagram (product).

It seems to me that what you've got here is an input data structure, an
output data structure, and an algorithm. In your current code the
algorithm is spread around in methods of the input and output data
structures. I would prefer it to be a separate thing outside either of them.

If I were you, I'd have:

- An input data structure based on your current voronoi_builder with
just its insert*() methods.
- An output data structure, which could maybe be Boost.Graph-based but
for now could be a simplified version of your voronoi_diagram class.
- Then put all of the beach line algorithmic stuff in an algorithm that
reads the input and creates the output.

I.e. rather than:

voronoi_builder vb;
vb.insert(......);
voronoi_diagram vd;
vb.construct(&vd);

instead:

voronoi_input i;
i.insert(.......);
voronoi_output o;
make_voronoi_diagram(i,o);

This really does hide implementation details from the user much more completely.

(One advantage of your current arrangement is that it has a split at
the right place to get both the Voronoi diagram and the Delaunay
triangulation by changing the back-end. This needs to be preserved,
but it doesn't justify the current structure.)

Let me say again that your code is great in many important ways
including performance and correctness. The restructuring that I'm
suggesting shouldn't affect the essence of the hard parts of the code
at all; it's just a matter of moving things around.


I encourage others to try out this code. I don't like being the only
person to comment on it!


Regards, Phil.

[Phil Endecott]

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.

[Jeffrey Lee Hellrung, Jr.]

On Tue, May 22, 2012 at 12:51 PM, Phil Endecott <
spam_from...@chezphil.org> wrote:

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

I was under the impression that the voronoi algorithm was decoupled from
the provided voronoi primitive structures...? I.e., one could use their own
primitive structures (with any desired associated user data) with the
algorithm. Is this not the case???

[...]

- Jeff

[Jeremiah Willcock]

On Tue, 22 May 2012, Phil Endecott wrote:

> Andrii Sydorchuk wrote:
>> On Mon, May 21, 2012 at 9:03 PM, Phil Endecott wrote:
>>> I can now refer to edges and vertices using Boost.Graph's
>>> vertex_descriptor and edge_descriptor, and lookup the CGVertex and CGEdge
>>> objects using operator[]:
>>>
>>> ContourGraph g;
>>> ContourGraph::vertex_descriptor v = g.add_vertex_near_vertex(....);
>>> g[v].alt = 42;
>>>
>>
>> I would look closer at this approach to investigate memory/performance
>> overheads of such a design.
>> Anyway providing Boost.Graph interface for Voronoi diagram data structure
>> is something that could be added within the future releases.
>
> It would be an interesting test of the Boost.Graph concepts to see if they
> fit a half-edge or dart or similar planar graph representation. Maybe some
> Boost.Graph experts could comment on this.

You might want to look at how CGAL does this mapping; I think they use
concepts that are slightly different natively, then have wrappers that
model Boost.Graph concepts. I'm not familiar with Boost.Graph's own
planar graph code.

-- Jeremiah Willcock

[Simonson, Lucanus J]

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

[Simonson, Lucanus J]

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

[Phil Endecott]

Simonson, Lucanus J wrote:
> 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.

Yes, I have confused myself a bit because I've been thinking primarily
about the Delaunay triangulation. In the Voronoi diagram, the output
vertices are new entities. In the case of the Delaunay triangulation,
the input vertices ARE the output vertices and only the edges are new.
So the triangulation algorithm can in principle operate in-place,
adding edges to an existing graph.

To make that a bit more concrete, the Delaunay algorithm could be:

template <typename IN_VERTEX_ITER_T, typename OUT_EDGE_ITER_T>
// IN_VERTEX_ITER_T is a random access iterator to a sequence of points that
// model the Boost.Polygon point concept.
// OUT_EDGE_ITER_T is an output iterator to a sequence of edges, which
could be
// pairs of IN_VERTEX_ITER_Ts.
void make_inplace_delaunay_triangulation(IN_VERTEX_ITER_T begin,
IN_VERTEX_ITER_T end,
OUT_EDGE_ITER_T out)
{
std::sort(begin,end,pred); // The input is re-ordered in place.
// Alternatively, use more memory and sort a sequence
of pointers.
...... // Run the sweep-line algorithm, and append edges to out.
}

// Usage:
std::vector< std::pair<int,int> > vertices_t;
vertices_t vertices = .....;
typedef std::pair<vertices_t::const_iterator> edge_t;
std::vector<edge_t> edges;
make_delaunay_triangulation(vertices.begin(),vertices.end(),back_insert_iterator(edges));



Regards, Phil.

[Andrii Sydorchuk]

On Tue, May 22, 2012 at 9:24 PM, Phil Endecott <
spam_from...@chezphil.org> wrote:

> I.e. rather than:
>
> voronoi_builder vb;
> vb.insert(......);
> voronoi_diagram vd;
> vb.construct(&vd);
>

The expected library usage is actually different:

voronoi_diagram<double> vd;
construct_voronoi(begin(input), end(input), &vd);

OR (with C++11):

voronoi_diagram<double> vd = construct_voronoi(begin(input), end(input));

The builder interface is supposed to be used directly only when additional
customization is required.

> The restructuring that I'm suggesting shouldn't affect the essence of the
> hard parts of the code at all; it's just a matter of moving things around.
>

I understand importance of those changes and willing to commit them as soon
as they are clear and don't make current interface overcomplicated.

Regards,
Andrii

[Andrii Sydorchuk]

On Wed, May 23, 2012 at 3:11 PM, Phil Endecott <
spam_from...@chezphil.org> wrote:

> Simonson, Lucanus J wrote:
>
>> 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.
>>
>
> Yes, I have confused myself a bit because I've been thinking primarily
> about the Delaunay triangulation. In the Voronoi diagram, the output
> vertices are new entities. In the case of the Delaunay triangulation, the
> input vertices ARE the output vertices and only the edges are new. So the
> triangulation algorithm can in principle operate in-place, adding edges to
> an existing graph.
>

For the Voronoi diagram output Voronoi cells (not Voronoi vertices) contain
information about input vertices/segments.

> To make that a bit more concrete, the Delaunay algorithm could be:
>
> template <typename IN_VERTEX_ITER_T, typename OUT_EDGE_ITER_T>
> // IN_VERTEX_ITER_T is a random access iterator to a sequence of points
> that
> // model the Boost.Polygon point concept.
> // OUT_EDGE_ITER_T is an output iterator to a sequence of edges, which
> could be
> // pairs of IN_VERTEX_ITER_Ts.

> void make_inplace_delaunay_**triangulation(IN_VERTEX_ITER_T begin,

> IN_VERTEX_ITER_T end,
> OUT_EDGE_ITER_T out)
> {
> std::sort(begin,end,pred); // The input is re-ordered in place.
> // Alternatively, use more memory and sort a sequence of
> pointers.
> ...... // Run the sweep-line algorithm, and append edges to out.
> }
>
> // Usage:
> std::vector< std::pair<int,int> > vertices_t;
> vertices_t vertices = .....;

> typedef std::pair<vertices_t::const_**iterator> edge_t;
> std::vector<edge_t> edges;
> make_delaunay_triangulation(**vertices.begin(),vertices.end(**
> ),back_insert_iterator(edges))**;
>

One important detail that you forgot here is duplicates elimination. Apart
from that I don't see how this is going to be generalized for segment
inputs.


I am going back to mention my previous idea to expose indices of input
sites within the voronoi_builder interface.
This will allow the user to implement the following data structure:

template<UserPointType>
struct inplace_delaunay_triangulation {
// Should be the same container that was used during construction.
inplace_delaunay_triangulation(const INPUT_RANDOM_ACCESS_CONTAINER
&input) : input_containers_(input);

template <typename SEvent>
std::pair<void*, void*> insert_new_edge (const SEvent &site1, const SEvent
&site2) {
int ind1 = site1.index();
int ind2 = site2.index();
// operate with data within input data set.
}

private:
const INPUT_RANDOM_ACCESS_CONTAINER& input_container_;
}

This approach doesn't require any hashmaps or smth. like this. The library
could provide version of inplace containers for inputs that consist only of
points.

Regards, Andrii

[Andrii Sydorchuk]

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

[Simonson, Lucanus J]

Andrii Sydorchuk wrote:

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

I'm fine with it being an index. This is how my own algorithms work. For example the connectivity graph extraction and the map overlay are index based. Below is the implementation of the interface for the general polygon connectivity extraction algorithm. You construct the connectivity_extraction object, insert into it with its insert member function, which returns an int, which is the index of your inserted object. The output data structure passed into the extract() function is required to be indexable with [] operators using the indexes returned. In the case of voronoi diagram you can return an index for each site inserted into the voronoi builder and write that index to a member of the voronoi cell at the output. If the user wants to index to a vector of altitude that is pretty easy, they just push the altitude back onto a vector at the time they insert the site into the voronoi builder.

namespace boost { namespace polygon {
//ConnectivityExtraction computes the graph of connectivity between rectangle, polygon and
//polygon set graph nodes where an edge is created whenever the geometry in two nodes overlap
template <typename coordinate_type>
class connectivity_extraction{
private:
typedef arbitrary_connectivity_extraction<coordinate_type, int> ce;
ce ce_;
unsigned int nodeCount_;
public:
inline connectivity_extraction() : ce_(), nodeCount_(0) {}
inline connectivity_extraction(const connectivity_extraction& that) : ce_(that.ce_),
nodeCount_(that.nodeCount_) {}
inline connectivity_extraction& operator=(const connectivity_extraction& that) {
ce_ = that.ce_;
nodeCount_ = that.nodeCount_; {}
return *this;
}

//insert a polygon set graph node, the value returned is the id of the graph node
inline unsigned int insert(const polygon_set_data<coordinate_type>& ps) {
ps.clean();
ce_.populateTouchSetData(ps.begin(), ps.end(), nodeCount_);
return nodeCount_++;
}
template <class GeoObjT>
inline unsigned int insert(const GeoObjT& geoObj) {
polygon_set_data<coordinate_type> ps;
ps.insert(geoObj);
return insert(ps);
}

//extract connectivity and store the edges in the graph
//graph must be indexable by graph node id and the indexed value must be a std::set of
//graph node id
template <class GraphT>
inline void extract(GraphT& graph) {
ce_.execute(graph);
}
};
}}

Regards,
Luke

[Andrii Sydorchuk]

On Wed, May 23, 2012 at 9:12 PM, Simonson, Lucanus J <
lucanus.j...@intel.com> wrote:
>
> I'm fine with it being an index. This is how my own algorithms work. For
> example the connectivity graph extraction and the map overlay are index
> based. Below is the implementation of the interface for the general
> polygon connectivity extraction algorithm. You construct the
> connectivity_extraction object, insert into it with its insert member
> function, which returns an int, which is the index of your inserted object.
> The output data structure passed into the extract() function is required
> to be indexable with [] operators using the indexes returned. In the case
> of voronoi diagram you can return an index for each site inserted into the
> voronoi builder and write that index to a member of the voronoi cell at the
> output. If the user wants to index to a vector of altitude that is pretty
> easy, they just push the altitude back onto a vector at the time they
> insert the site into the voronoi builder.
>

That sounds good to me. Such implementation allows to build inplace output
data structure around user provided input.

As a side note, we would probably need to have two counters: one for points
and one for segments. Additional point sites (segment endpoints) that are
not actually part of the input could have the same index as related input
segment and its up to the output data structure to decide how to treat them
for the inplace implementation.

Regards,
Andrii

[Simonson, Lucanus J]

Andrii Sydorchuk

>As a side note, we would probably need to have two counters: one for points and one for segments.
>Additional point sites (segment endpoints) that are not actually part of the input could have the same index as
>related input segment and its up to the output data structure to decide how to treat them for the inplace implementation.

I think a single index would be simpler on our side and if the user requires different data types for point and segment they can handle that on their end with a simple abstraction on top of the index such as indexing to a boost any. Having two different types of index doesn't enable anything, it simply makes one specific use case more convenient. Common use cases will be only points or only segments in the input, so complicating the interface for the mixed case seems like over design.

Regards,
Luke

[Phil Endecott]

Andrii Sydorchuk wrote:
> On Tue, May 22, 2012 at 9:24 PM, Phil Endecott <
> spam_from...@chezphil.org> wrote:
>
>> I.e. rather than:
>>
>> voronoi_builder vb;
>> vb.insert(......);
>> voronoi_diagram vd;
>> vb.construct(&vd);
>>
>
> The expected library usage is actually different:
>
> voronoi_diagram<double> vd;
> construct_voronoi(begin(input), end(input), &vd);

Ah yes, I'd forgotten that. But construct_voronoi is just a 3-line
function that does what I was doing. In my case, it was simpler to
call insert() inside a for loop rather than trying to create some sort
of range adaptor to pass to the free function.


Regards, Phil.

[Andrii Sydorchuk]

By this point it seems that the only concern about Voronoi implementation
is the Voronoi diagram data structure design.
I had enough time to read the whole thread again and here is my vision of
how the main issues should be resolved:

============================
1) [MAIN ISSUE] Decoupling input data from the output.
I think I've managed to come up with a pretty nice solution:
a) voronoi_diagram would not contain coordinates of the input geometries,
that means that voronoi_cell data structure will represent a cell, not
geometry (point or segment) inside it.
b) according to the above, new voronoi_cell data stucture will look like:
struct voronoi_cell {
// Specifies type of the geometry that forms the cell.
CellSourceCategory source_category;
// Unique id of the source object that is inside the cell.
size_t geometry_id;
voronoi_edge* incident_edge;
size_t color;
};

enum CellSourceCategory {
POINT = 0,
SINGLE_POINT = 0, // if divided by 4 falls into POINT root category.
FIRST_POINT = 1, // if divided by 4 falls into POINT root category.
SECOND_POINT = 2, // if divided by 4 falls into POINT root category.

SEGMENT = 1,
INITIAL_SEGMENT = 4, // if divided by 4 falls into SEGMENT root
category.
OPPOSITE_SEGMENT = 5, // if divided by falls into SEGMENT root category.
};

Note: as one may admit CellSourceCategory requires just 3 bits, thus it
could be packed with geometry_id member.

c) CellSourceCategory is required to encapsulate edge geometries topology
within the voronoi diagram data structure.
E.g. checking whether the edge is curved or linear, primary or not without
accessing input geometries list.

d) geometry id corresponds to the index of the site (point, segment)
retrieved from the voronoi_builder during insertion.
It is given sequentially starting from 0. Thus will correspond to the input
geometry index within a container if inserting elements sequentially.
Note: both segment endpoints and segment itself will have the same
geometry_id, while all of them have dedicated voronoi cell in the output.
We identify them using CellSourceCategory.

e) voronoi_utils interface will be changed as voronoi diagram primitives
don't contain information about input geometries coordinates.
e.g. to sample curved voronoi_edge we will also need to pass random access
container holding input geometries in the order they were passed to the
voronoi builder.

============================
2) Each of the primitive types has size_t color member. Which could be
basically used to associate data with primitives or execute graph
algorithms.
Considering the new design of the voronoi_cell this produces 9/50 ~= 20%
(details could be provided on request) memory overhead.
Compiler directives could be used to enable/disable this data member if
approved by the community.

Note:
Please keep in mind that users are always free to implement their own
primitives types.
The current voronoi diagram topology implementation is one of the most
compact, considering the fact that it gives complete freedom on voronoi
graph traversal.
Thus I don't think that 20% overhead is significant.

============================
3) [QUESTIONABLE ISSUE] Voronoi diagram builder.
The main point of this build class is encapsulation of the voronoi diagram
construction methods.
At the moment it is implemented as part of the voronoi diagram structure
(Java style) and just redirects construction calls to the voronoi_diagram
private routines.
If required could be implemented as a friend class of the voronoi_diagram.

As always comments are welcome (especially on the solution of the first
issue).

Thanks,
Andrii