Re: [boost] [polygon] [GSOC] voronoi diagram of line segments

Subject: Re: [boost] [polygon] [GSOC] voronoi diagram of line segments
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2010-10-26 15:53:10

Hi Luke and Andriy,

congratulations to this great achievement. I was positively surprised when I saw that the proposal was accepted as a GSOC project, and I always enjoyed seeing that Andriy was making good progress. It's nice to see that Andriy even succeeded implementing Voronoi diagrams of line segments and not just Voronoi diagrams of points.

Simonson, Lucanus J wrote:
> The code isn't yet ready for preview or experimentation,
> but I thought the community would appreciate the update
> and sneak peek at the early results generated by the solution
> to this very challenging computatinal geometry problem.

I agree with Luke's assessment. Even the popular Qhull code <http://www.qhull.org/> only computes Voronoi diagrams of points. Of course, CGAL implements Voronoi diagrams of line segments <http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Segment_Delaunay_graph_2/Chapter_main.html>, but CGAL is not "free". I didn't see a "free" implementation in <http://www.geom.uiuc.edu/software/cglist/>, but I think <http://www.cosy.sbg.ac.at/~held/projects/vroni/vroni.html> is at least another non-"free" implementation for Voronoi diagrams of line segments.

> I also want to publically recognize and congratulate the student,
> Andrii Sydorchuk, for his good work and great achievement.

I think Andriy really earned that recognition. However, I noticed that the only other feedback is from Dave. I recall Barend Gehrels complained that the student doing the spatial indexing GSOC project was publicly shot down <http://lists.boost.org/Archives/boost/2008/10/143220.php> and subsequently lost any motivation to continue working on his project. It's not clear to me whether scarce positive feedback is even worse than abundant feedback also containing open critique, but working on such a project may depend more on inner motivation than on external feedback anyway. However, I wonder whether also posting to the Boost.Geometry mailing list <http://lists.osgeo.org/mailman/listinfo/ggl> would be a good idea, at least when the code is ready for review and experimentation. It might generate a bit more feedback, because the people there are at least interested in computational geometry. (But more feedback will normally also contain open critique, so you better be prepared.) As far as I can see, the only relation between Boost.Polygon and the sweepline project at the current moment is that both rely on integer coordinates to provide robustness (and of course the mentor), so that the project is not too closely tied to Boost.Polygon anyway.

I didn't reply earlier because I had a project deadline last Wednesday. And because I was unable to reply immediately, I took the chance to review the current state of the project a bit. I could successfully build the interactive example qt program on linux, and really liked it. I also build the tests, but some of these were extremely memory hungry and also pushed the processor to full power over a long time. I was less successful on win32. I somehow didn't manage to configure qt as to be able to build the example program. (I will have to work this out when I have time.) The test ran out of memory on win32 with the strange error message "cmalloc would have returned NULL". Tests and benchmarks should push the tested library to its limits, not the test machine.

I thought a bit about the occasions in the past where I wished to have a good Voronoi diagram implementation.

- The Voronoi diagram of a point set would have been useful for the case where some measurements (or computations) were given at some suitably placed 2D points without any explicit grid structure, and the goal was to project these measurements onto a given regular grid using piecewise constant interpolation. When we always use the measurement value of the nearest measurement point for the interpolation, we will implicitly compute the Voronoi diagram of the measurement points. The explicit availability of the Voronoi diagram should speedup this procedure.

- The Voronoi diagram of line segments would have been useful for the case where a 3D topography had been defined by a polygonal base and a cross-section. For a point with given x- and y-coordinate, the signed distance from the polygon edges was computed and used to lookup z-positions in the cross-section. In a certain sense, this procedure will implicitly compute the Voronoi diagram of the Polygon edges viewed as line segments. (The task here was also to evaluate the z-positions on a given regular grid in x-y direction.) The explicit availability of the line segments Voronoi diagram should speedup this computation.

- There are many more application of Voronoi diagrams like triagulations, offseting, shape detection, ..., but the above two are the ones that I can actually still remember having encountered in real live.

Regards,
Thomas