If Lucanus Simonson wants to include your code in Boost.Polygon library, no review is needed. If you want this to be an independent library, a review is needed. If you want a review even though it's not needed... I guess that's up to the review wizards.

Personally I would like the Voronoi functionality to be included into the Boost.Polygon library. I would also like to have at least informal review if it's possible.

Anyway, it'll be great to have this in Boost.

Glad to hear.

BTW, I think there's something wrong with http://svn.boost.org/svn/boost/sandbox/gtl/doc/voronoi_predicates.htm My browser displays it as raw HTML.

Thanks, fixed. Cheers, Andrii

Hi Phil,

Your message arrived at an interesting time, as I was looking for a Delaunay triangulation implementation yesterday and got depressed by the quality of what I found elsewhere.

Glad to hear! Although your email mentions Delaunay triangulation, the impression that I

get from the documentation (& code) is that you have not implemented this.

Voronoi diagram data structure is dual to the Delaunay graph. That means you can retrieve all the Delaunay graph information from the Voronoi graph, even do traversal. As this would be weird for many users we are also planning to implement dedicated Delaunay triangulation data structure (this is the first item in the priority list). In case you provide more details on the task you are trying to solve I could help with the code examples. My guess would be that this is a more popular algorithm than the Voronoi

diagram; there are also more existing implementations that you could compare performance with (q-hull, s-hull etc.).

As I mentioned above it's possible to traverse Delaunay graph using Voronoi diagram graph without any performance drawbacks (except that it's a bit weird). Apart from that it corresponds to the medial axis transform of a closed region. It could be also directly used for the path construction algorithms. So construction of Voronoi graph allows to solve many more problems than triangulation itself. Also Voronoi diagram is clearly defined for the input data sets that contain linear segments while it's not for the Delaunay triangulation. Have you investigated how the output of your algorithm(s) could be used as

input to Boost.Graph?

Not, yet :). But this is one of the items in my todo list on the main page: http://svn.boost.org/svn/boost/sandbox/gtl/doc/voronoi_main.htm One practical question: what version of Boost / Boost.Polygon does your

code require?

Voronoi code doesn't depend on the Boost.Polygon library. The intention is to use those libraries side by side. There is a single dependency on Boost: boost/cstdint.hpp. So I bet it compiles with any recent version of Boost within the last 10 years. Andrii

The constrained Delaunay triangulation of polygons is something I'm not sure how to solve using the voronoi diagram of points or segments, though it may be trivial, I just haven't thought it through or looked it up.

I had some thoughts about this already. My basic intuitive idea is that we can construct usual Delaunay triangulation of the initial set of points and endpoints of the segments. Afterwards we could do some edge flipping based on the concrete input segments we have to receive constrained Delaunay triangulation. Intuitive ideas are usually wrong, that's why this would require further investigation. But at least we have something to start with. Thanks, Andrii _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Tim Keitt wrote:

For constrained triangulation, I would check out http://www.cs.cmu.edu/~quake/triangle.html I've found it very useful. Its not so good for voronoi (topologically its of course correct, but the actual segments it generates are sometimes off). But that is because its targeted at mesh generation and not voronoi diagrams.

Yes, we know of Triangle. It has a non-free license. I suppose I should just go do the literature search for constrained Delaunay again, then I'd know how much work it would take to implement it with what we have currently. Thanks, Luke

From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Tim Keitt

Note that underlying predicates library is in the public domain. Dunno if that helps. http://www.cs.cmu.edu/~quake/robust.html

As I understand it, the boost license exists because there is no provision in copyright law to relinquish copyright and place a work in the public domain. We looked into the predicates. It doesn't really help because we actually needed different predicates. I remember Andrii explaining that to me. It turns out to be a much harder problem than I even realized when I posted it as the GSOC 2010 project idea. Fortunately Andrii solved it. Thanks, Luke

For constrained triangulation, I would check out http://www.cs.cmu.edu/~quake/triangle.html I've found it very useful. Its not so good for voronoi (topologically its of course correct, but the actual segments it generates are sometimes off). But that is because its targeted at mesh generation and not voronoi diagrams.

Tim, thanks for the link! We are aware of the Triangle library. Also as a side note it seems that it doesn't construct Voronoi diagram of linear segments. Andrii

Well this is interesting. I've looked some more at your docs and I see that you really haven't used e.g. Boost.Polygon's Point concept at all. Instead you have your own concepts; IIUC, having read the "Basic Tutorial" page, your Point concept requirement is

To make it clear there is no such thing as Boost.Polygon.Voronoi Point. The library would work with any point class that supports x() and y() access methods at the moment. So I'd be interested to know what has happened in this case. Is it simply

that the extra work to use the generic style is too much to ask of the author? (At the time of the review, I had the impression that this style was making life unreasonably difficult for potential library contributors, but I think I was convinced by others that this was worthwhile in order to get more uptake in existing code.) Or is there some other factor that I've missed?

I didn't consider this before as this will require just one small change in the Voronoi builder initialization method. So if this is a permanent requirement for the inclusion I'll do the proper updates. On the other hand I really like current interface as it is very simple and allows to construct Voronoi diagram with one include header and two lines of code. I am wondering if there is a solution that will satisfy both sides. For example changing default implementation of point_traits: template <typename T> static inline coordinate_type get(const T& point, orientation_2d orient) { return point.get(orient); } to: template <typename T> static inline coordinate_type get(const T& point, orientation_2d orient) { return (orient == HORIZONTAL) ? point.x() : point.y(); } This will support my current template interface that accepts anything with x(), y() methods by default and won't break functionality of the Boost Polygon library. Am I right? Regards, Andrii

The problem is somewhat the reverse of that actually. People will want to use their point classes that are already model of Boost.Polygon point_concept with the voronoi diagram API and will not be able to because it expects different traits than the point_concept requires.

Yes, so what I meant is that I could change Voronoi builder initialization step code to operate with the Boost.Polygon point_traits, this will look like this: int32 x = point_traits<PointContainer::iterator::value_type>::get(*it, HORIZONTAL); int32 y = point_traits<PointContainer::iterator::value_type>::get(*it, VERTICAL); My point is that if the default point_traits specialization is changed to the one I mentioned in my previous post, this will fix all the issues: 1) The users will be able to use their legacy point classes by specializing point_traits; 2) The users whose point type supports x() and y() access methods won't be required to do anything. The same will apply for the segment class. If we do some additional clean up to the isotropy.hpp header this won't add any heavy dependencies to the current Voronoi code. Please correct me if I am wrong. Thanks, Andrii

Hi Vadim,

The question concerning fully constructed Voronoi diagram as well as Delaunay triangulation:

"find the nearest neighbor" - for a particular Voronoi cell this could be done in a constant time that depends on the number of Voronoi cell neighbors. You could also compute and store this data for all the sites within the diagram in O(N) time once the Voronoi diagram is constructed (N is total number of input geometries). "insert/erase a vertex" - You mean insertion / removal of vertices from the resulting Voronoi graph, am I right? Or insertion of a new input geometries that will require to rebuild Voronoi diagram? How long, do you think, it can take to parameterize types of coordinates,

points and point predicates?

Coordinate type is already parametrized via coordinate type traits of Voronoi builder. There is no such thing as point parametrization right now. Everything that has x() and y() method will work as a point. Predicates parametrization is already available via template parameter of the Voronoi builder. However I don't think that somebody will use this. Default Voronoi predicate kernel was designed in such a way that it operates with exact predicates at almost no cost for using them. Sounds like a magic, but that's true :-). The thing is that default static methods available in the voronoi.hpp header are not parametrized with any coordinate type traits or predicate kernels. This is made intentionally as in most cases this is not required: http://svn.boost.org/svn/boost/sandbox/gtl/doc/voronoi_advanced_tutorial.htm. In case you really need those you should go for the Voronoi_builder data structure that is completely configurable, (this is also covered in the advanced tutorial). The benefits of the generalized algorithm are quite significant. Many

existing libraries can use this algorithm either directly or with minimal adaptation. The parameterization of point predicates is quite important. For example, in practice, tolerance based predicates are very good alternative to multi and adaptive precision methods.

The library is already fully generalized except input point and segment types. But we are going to resolve this soon. With the right choice of predicates points using floating data types will

be supported too.

Not sure, what you mean by "predicates points". Could you explain with an example? Thanks, Andrii

We can't really change the default now because it is a documented interface and that would be a breaking change.

Agree. If we overload your functions on concept type they would still need to

register their point type by specializing the metafunction that looks up the concept of a given type. The whole point of the Polygon concept type system is to allow overloading of generic functions by concept type.

Sounds like a plan, I need to think about it. This was my vision for the interfaces of voronoi. We can compromise and

just use the point_concept for now with the intention of extending the interface for line segment concepts when they are finished.

Ok. I just want to make it clear for the users that it's still possible to use Voronoi functionality even if the point or segment class doesn't conform to x(), y() / low(), high() access method interface. The example is following: struct Point { int a; int b; }; void construct_voronoi(const std::vector<Point> &vp) { voronoi_builder<int> vb; voronoi_diagram<double> vd; for (std::vector<Point>::iterator it = vp.begin(); it != vp.end(); ++it) vb.insert(it->a, it->b); vb.construct(&vd); } So at the moment one will need to use voronoi_builder structure to construct Voronoi diagram instead of static methods defined in the voronoi.hpp header in the following cases: 1) User provided point/segment class doesn't support x(), y() / low(), high() accessor methods; 2) User provided container doesn't support forward ++ iterator. 3) User wants to configure coordinate types or predicate kernels (don't do that! believe me you want be able to come up with smth. better). The intention of those 3 static methods is to cover 95% of usage cases. For the other 5% of cases it's always possible to use Voronoi builder data structure directly. I am going to add this to the documentation as this seems to confuse people about how parametrized and generic is the library. I think he means he wants to supply his own point comparison and circle

event comparison predicates rather than use the library provided ones because he thinks he can just use the epsilon method with floating point coordinates. I don't think that is a good idea.

Totally, from my experience in algorithm competitions: while the best non-robust algorithm will work in 99.9% of cases, there will be always the case when it fails. Thanks, Andrii

The simplest point predicate is just lexicographical compare using x and y coordinates of two points. In theory, without tolerance points are infinitely small and lines are infinitely thin. Tolerance parameter makes points and lines "thick". Such point predicates can be made problem specific. They work well both for integral and floating data types of coordinates. This is why I am suggesting to generalize your algorithm if this is not too costly.

You don't need to explain to me about what the epsilon method is. No, it does not work well for either integer or floating point based computational geometry. We didn't go to the effort of making voronoi numerically robust because we didn't understand how easy it would be to just use a tolerance in our floating point comparisons. We did it because we understand in detail exactly why epsilon method is a bad idea, exactly what invariants would be violated and exactly what input conditions will lead to a crash or incorrect output. Please just drop it.

The question concerning search and update operations can be reduced to the following: Does this VD support incremental insertion of a new cell?

No, this is not an incremental update VD algorithm. It is sweepline based. Incremental update could be implemented on top of the vornoi diagram data structure and would require roughly constant factor cost to insert a new site if you knew which cell you were inserting the site into since updates would only need to be made local to the insertion site. Locating the insertion site would in theory be O(log n) if you used a spatial index to accelerate it. We might consider it as a future enhancement. Regards, Luke

From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Phil Endecott

Well in case it is useful as a motivating example, my current requirement is to: - Read in a large number of (x,y,attribute) from a file. - Compute the Delaunay triangulation of the (x,y), keeping the edge graph. - Discard some edges based on attributes of the vertices, i.e. equality or inequality. - Partition the modified graph into connected subgraphs (Boost.Graph's connected_components). - For each of those subgraphs, find a Hamiltonian or longest cycle or path (using BFS). - Write the coordinates of the points on those cycles or paths to the output file.

Looks like it would make a smashing good tutorial and help us figure out the glue needed to get VD data structure to work with Boost.Graph. The overhead for computing the voronoi vertices should be minimal, particularly for voronoi of points, which is numerically easier than that of line segments. This should be a straightforward application of the library. Thanks, Luke

Hi Ron, I've received your request and will add it to the review queue. Just to clarify: this is not a request to include a completely new library into the Boost, but rather adding new functionality to the existing one (Boost.Polygon). Please let me know if Lucanus agrees to manage the review. I think he does, but would prefer him to confirm personally. Cheers, Andrii

From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Phil Endecott

I've started to look at your code. The good news it that it does seem to work! Some observations: template <typename PC, typename VD> static inline void construct_voronoi(const PC &points, VD *output, ..... { default_voronoi_builder builder; builder.insert(points.begin(), points.end()); ...... It would be more conventional to pass begin and end iterators in your public interface, rather than a reference to the container. This allows the caller to e.g. pass part of a container, or >pass raw pointers, or pass complex iterators like filtering iterators etc. I.e. template <typename POINT_ITER, typename VD> static inline void construct_voronoi(POINT_ITER begin, POINT_ITER end, VD *output, ..... { default_voronoi_builder builder; builder.insert(begin, end); ...... This is more verbose for the caller, but we are normally prepared to pay that cost (or to use a Range).

Eventually we would like to have a directed_line_segment_set_concept and point_set_concept for which any standard container that supplies forward iterator semantics would be a model. These would just call the iterator pair form of the function by using the begin()/end() traits of the concept instead of member function. We would also supply a concept cast so that you could call: construct_voronoi(view_as<point_set_concept>(my_polygon_set)); to override the semantic of polygon set to use its edges as line segments and instead use just the vertices as a point set.

You said before that the code has no dependency on the rest of Boost.Polygon, but I now see that you are including e.g. isotrophy.hpp and point_concept.hpp. These include other things like mpl. My guess is that I'm looking at code that is changing under my feet! Is there a "stable" version that I can use? I'd like to look at something that is at least consistent with the documentation.

Yes, the code is changing under your feet, prompted actually by your initial feedback. You can always use time stamped checkout of sandbox svn from the date Andrii posted his review request to work with a stable version that matches the documentation. I see that your voronoi_cell and voronoi_edge classes have:

class voronoi_cell/edge { public: void *data() const { return data_; } void data(void *d) const { data_ = d; }

private: mutable void *data_; }; This probably isn't the best way to include user-data, because it is not type-safe and it has overhead when no data is needed. Can't you either pass the type of the user data as a template parameter, or allow the user to supply their own cell and edge (sub-)classes? (Perhaps someone else can suggest a good example of how to do this.)

Although you have this user-data in the voronoi_cell/edge classes, I don't see any way to have additional attributes in my input data copied to, or referenced from, the output. I.e. if my input points have a "name", I'd like that to be accessible in the corresponding voronoi_cell. I am imagining a design where the voronoi_cell contains a copy of the input point-sequence iterator, or a reference to the input point.

I have a similar problem for exposing the generalize line segment intersection algorithm. Internally my algorithm represents association to input line segments by an index. I don't expose that in any documented interface, however. It is tricky to associate intersected line segments with original line segments because of rounding. The output segments will not be collinear with the input segments. As long as there is a way to make the association then it can be the user's problem to propagate properties to the output. In the case of voronoi diagram, the output sites are identical to the input sites, so the association from input to output site can be made easily by hash or log n lookup. Once could always copy the output voronoi diagram to their own data structure that is augmented with whatever data that they want based on association with the input sites. I think that just eliminating this void* data feature and providing an example of copying the diagram into a different graph data structure and looking up input sites in a map to populate some field would be the best way to handle this. I don't know that we currently have code that uses this feature of the cell/edge, do we Andrii?

I am trying to get the edges of the Delaunay triangulation by iterating over the edges of the Voronoi diagram. But I can only see how to get one of the neighbouring cells for each edge, and I need both in order to create a Delaunay edge. Is there some way to do this?

I think building the Delaunay triangulation of a set of points from the voronoi diagram data structure should be provided as example code in the documentation in addition to being a documented API that populates a collection of polygon_concept with triangles. That way people can adapt the example code to populate their own mesh data structure if a container of polygon_concept doesn't map well to what they need. We can make the example code use concrete types for ease of reading and implement the API as a generic algorithm with concept overloading on polygon_concept that would be confusing if shown in example code. Regards, Luke

I think that just eliminating this void* data feature and providing an example of copying the diagram into a different graph data structure and looking up input sites in a map to populate some field would be the best way to handle this. I don't know that we currently have code that uses this feature of the cell/edge, do we Andrii?

Well, I have examples in the basic tutorial on how this data member could be used. Personally I used it to do DFS on the Voronoi graph, by setting visited edges data pointer to themselves. I found this functionality to be very handy: void dfs(const VD::edge_type* edge) { if (edge->data()) return; // do some edge processing here. edge->data(&edge); edge->twin()->data(&edge); const voronoi_diagram<double>::edge_type* e = v->incident_edge(); do { dfs(e); e = e->rot_next(); } while (e != v->incident_edge()); } I think building the Delaunay triangulation of a set of points from the

voronoi diagram data structure should be provided as example code in the documentation in addition to being a documented API that populates a collection of polygon_concept with triangles. That way people can adapt the example code to populate their own mesh data structure if a container of polygon_concept doesn't map well to what they need. We can make the example code use concrete types for ease of reading and implement the API as a generic algorithm with concept overloading on polygon_concept that would be confusing if shown in example code.

True. I am also going to implement dedicated Delaunay triangulation data structure as soon as I have some time. Regards, Andrii

Phil,

It does seem to create a triangulation as you can see here: http://chezphil.org/tmp/delaunay.png

I would also appreciate if you post your system configuration, number of input points on that image and time it took to construct Delaunay triangulation. Thanks, Andrii

on Fri Apr 13 2012, "Simonson, Lucanus J" <lucanus.j.simonson-AT-intel.com> wrote:

From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Andrii Sydorchuk

...

...

It does seem to create a triangulation as you can see here: http://chezphil.org/tmp/delaunay.png

...

I would also appreciate if you post your system configuration, number of input points on that image and time it took to construct Delaunay triangulation.

I'm curious too. My jaw dropped when that png loaded. Pretty impressive.

Mine too. I love computational geometry :-) -- Dave Abrahams BoostPro Computing http://www.boostpro.com

There are about 2e5 input points and 6e5 output edges, and generation takes about 35 seconds on a 1.2GHz Marvell Feroceon 88FR131 (a QNAP TS-119) using g++ version 4.4.2 -O3.

I am wondering if this also includes image generation time. On my nettop with an Intel Celeron U3400 1.07 GHz, g++ 4.4.1 it takes around 3-4 seconds and on my PC with i5-7600 2.8 GHz, g++ 4.6.1 just 0.6 seconds. It needs to be quite a lot faster than that, but it's not a bad start :-) Actually it's already very fast. By performance, construction of Voronoi diagram of 2e5 input points is equivalent to insertion of 2e6 pair<int, int> into std::set. So I guess your result of 35 seconds is very architecture specific or hides some details. My main performance concern is the overhead of doing O(log N) lookup to get

from the output vertices back to the corresponding input points.

As I mentioned I could expose index of the site event within the initial input set, thus this will require O(1) time. I will also need to investigate how much RAM is needed. This is already available in benchmarks. The memory usage of the current Voronoi diagram data structure for the set of 1e5 input points is 23 megabytes. Thanks, Andrii

Correction: those numbers are correct, but the PNG that I linked before is for approximately 1/4 of that data. Try it on your phone.

Ok, that explains things :). Please compare it with q-hull and s-hull, and perhaps with whatever CGAL

offers.

Looks like nobody wants to look at the benchmarks: http://svn.boost.org/svn/boost/sandbox/gtl/doc/voronoi_benchmark.htm I'm not hiding anything; I posted most of the code. But this test was not

constructed as a benchmark, so don't read too much into it.

I suspect that the main difference between this test system and yours is

the cache size.

Yes, you should be right. I just wanted to clarify for the users that Voronoi is indeed fast. Have a look at how Boost.Graph does "bundled properties":

http://www.boost.org/doc/libs/**1_49_0/libs/graph/doc/bundles.**html<http://www.boost.org/doc/libs/1_49_0/libs/graph/doc/bundles.html>

Thanks, I've read it and I like it a lot. However the main problem is that mapping between input geometries and output cells is not one-to-one for Voronoi of segments, because each input segment is treated as three input sites (segment itself and both its endpoints). Nevertheless I am going to investigate "bundled properties" a bit more. Regards, Andrii

Andrii Sydorchuk wrote:

...

Please compare it with q-hull and s-hull, and perhaps with whatever CGAL offers.

Looks like nobody wants to look at the benchmarks: http://svn.boost.org/svn/boost/sandbox/gtl/doc/voronoi_benchmark.htm

Sure, I've looked at the benchmarks. They compare Voronoi diagram generation with CGAL. I'm interested in Delaunay triangulation generation, for which s-hull is possibly the fastest existing implementation. I'd like to see a comparison with that.

I just wanted to clarify for the users that Voronoi is indeed fast.

Fast is a relative term. The GPU in my phone can draw tens of millions of triangles per second. Could this code supply triangles quickly enough? Probably not. Faster is always better. Regards, Phil.

If you need a robust, fast Delaunay triangulation routine as source try

...

S-Hull-Pro. <http://www.s-hull.org/index_files/commercial.html>

Do you want me to compare robust implementation Voronoi provides with non-robust of S-hull? I can do that, but is it fair?

from http://www.s-hull.org/index_files/commercial.html: Binaries for command-line versions of the algorithm are freely available

for Mac OSX, Windows, and Linux.

Seems that I'll be able to do comparison with S-Hull-Pro also! Andrii

I welcome the Voronoi addition to Boost. Alas I've currently no time to dive into this contribution or take part in the discussion. I did look at the PNG of Phil and was quite impressed.

I am starting to think of rendering Voronoi diagram of 1 000 000 segments. Looks like such things are the best way to convince people :-). As a side note, would like to thank Phil for his image! I hope it will be made to work with Boost.Geometry too, in the future. I guess it would be possible to do that on top of the Voronoi builder API. Currently it is very simple and consists just of four methods: http://svn.boost.org/svn/boost/sandbox/gtl/doc/voronoi_builder.htm. However one of the limitations is that Voronoi operates with integer input coordinates. To clarify this is not restricted just to int32, but could be int128 or int1024 types provided by the user. The main point is that you can always scale and snap to the integer grid coordinates. But Andrii also indicated it is independant of it. It's independent in such a way that it could be used via Voronoi builder interface and that wouldn't include any heavy dependencies on Boost libraries (except boost/cstdint.hpp), such as MPL. On the other hand voronoi.hpp header provides static routines that allow to use Voronoi functionality with the full power of the Boost.Polygon concepts, thus making it easy to use with the user provided point/segment/polygon classes. Both libraries could also be used side by side, so users will only benefit from the inclusion. My main point for asking a review was to receive more feedback from the community. I've already got a few outstanding advices from Luke, Phil and other folks, thus considering this to be a good decision. Regards, Andrii

Andrii Sydorchuk wrote:

I've just added S-Hull triangulation (non-robust version) to the benchmarks and it appears that it's only a bit faster for the input sizes of around 100 points and only on Linux-64, for all the other cases Boost.Polygon Voronoi dominates (especially for large input data sets).

Updated benchmark page: http://svn.boost.org/svn/boost/sandbox/gtl/doc/voronoi_benchmark.htm

Great, that's exactly the analysis that I wanted to see! Can you update the "Logarithmic Execution Time" graph to include the s-hull results? For completeness you might also like to include q-hull, as I suspect it is probably robust. But the important thing is that you have compared your algorithm with the competitor that claims to be the current fastest. Regards, Phil.

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

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

On Sun, May 20, 2012 at 11:16 AM, Jeffrey Lee Hellrung, Jr. < jeffrey.hellrung@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 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

On Mon, May 21, 2012 at 2:38 AM, Steven Watanabe <watanabesj@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

On Mon, May 21, 2012 at 9:14 AM, Simonson, Lucanus J < lucanus.j.simonson@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

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

On Mon, May 21, 2012 at 6:14 PM, Simonson, Lucanus J < lucanus.j.simonson@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

On Tue, May 22, 2012 at 12:51 PM, Phil Endecott < spam_from_boost_dev@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

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. Regards, Luke

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

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

On Wed, May 23, 2012 at 3:11 PM, Phil Endecott < spam_from_boost_dev@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

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

On Tue, May 22, 2012 at 9:24 PM, Phil Endecott < spam_from_boost_dev@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

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

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