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

Subject: Re: [boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library
From: Andrii Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2012-05-21 19:08:09

On Mon, May 21, 2012 at 9:03 PM, Phil Endecott <
spam_from_boost_dev_at_[hidden]> 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