I just wanted to update the boost dev community on the progress of the GSOC project from this summer implementing voronoi diagram of points and line segments, which leads to delauney triangulation, medial axis of polygons and nearest neighbor. The student has the sweepline implementation of voronoi for line segments working for several test cases and has provision in the code to handle numerical robustness with the caveot that input coordinates must be integer. I have attached an appealing screenshot showing the result produced by the new code for a small test case. Since the sweepline algorithm implementation is optimal O (n log n) and can be made robust given the techniques employed to compute predicates I believe we may be able to release new features in Boost.Polygon based on this work in 2011. 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 also want to publically recognize and congratulate the student, Andrii Sydorchuk, for his good work and great achievement. Regards, Luke

Hey, very appealing! I have a soft place in my heart for computational geometry, but it's been a long time since I've studied it and I'd never seen a voronoi diagram for points *and* line segments before. So (just guessing when I could look it up), every line segment gets a perpendicular line through its endpoints and the curved lines are equidistant between each line segment and its nearest point(s)? The voronoi diagram is constructed using the bisectors (the locus of points equidistant from the two objects) between pairs of objects. Bisector of two points is a line. While the bisector of two disjoint segments is a simple curve that may consist up to seven sections (line or parabola). To simplify everything each segment is divided onto three parts: two endpoints and segment itself. This way the bisector between any two objects consists of one section (line or parabola) and falls into one of four categories: 1) both objects are points - bisector is the line bisecting them; 2) a segment and its endpoint - bisector is the line perpendicular to segment through endpoint; 3) a segment and disjoint point - bisector is the section of parabola; 4) both objects are segments - bisector is the line segment. I guess this simplified explanation will help to understand how it works for people who haven't seen voronoi of segments before. Indeed, congratulations to student and mentor alike! Thanks. Best, Andrii Sydorchuk

Le dimanche 17 octobre 2010 11:01:08, David Abrahams a écrit :

At Fri, 15 Oct 2010 19:54:07 -0700,

Simonson, Lucanus J wrote:

...

I just wanted to update the boost dev community on the progress of the GSOC project from this summer implementing voronoi diagram of points and line segments, which leads to delauney triangulation, medial axis of polygons and nearest neighbor. The student has the sweepline implementation of voronoi for line segments working for several test cases and has provision in the code to handle numerical robustness with the caveot that input coordinates must be integer. I have attached an appealing screenshot showing the result produced by the new code for a small test case.

Hey, very appealing! I have a soft place in my heart for computational geometry, but it's been a long time since I've studied it and I'd never seen a voronoi diagram for points *and* line segments before. So (just guessing when I could look it up), every line segment gets a perpendicular line through its endpoints and the curved lines are equidistant between each line segment and its nearest point(s)?

There is an implementation of that class of diagram in CGAL: http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Segment_Delaunay_grap... It could be interresting to compare with.

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

Thanks to all of You! 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.

The test configuration includes tests with 1 000 000 input points. This was helpful to figure out some longrun bugs. Probably you should run those tests with release option. Using release it takes me around 20 secs to run all the tests and around 60 secs to run benchmark tests. The algorithm implementation uses stl vectors, lists, maps and queues. Those data structure are slower in the debug mode especially when you run large inputs. I was less successful on win32. I somehow didn't manage to configure qt as

to be able to build the example program.

I've updated build script, you shouldn't have any troubles now. 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.

Did you use mingw or cygwin to compile it? I am using msvc 9.0 compiler on win32 and it works fine. However I received the same message using cygwin + gcc. In my case this was failing on the 1 000 000 points test. Best, Andrii On Tue, Oct 26, 2010 at 11:20 PM, Mateusz Loskot <mateusz@loskot.net> wrote:

On 26/10/10 20:53, Thomas Klimpel wrote:

...

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.

Thomas,

Andrey's achievement and solid work hasn't slipped unnoticed, certainly not.

Good point though and I have just forwarded this thread there.

Best regards, -- Mateusz Loskot, http://mateusz.loskot.net Charter Member of OSGeo, http://osgeo.org Member of ACCU, http://accu.org _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

-- Best regards, Andrii Sydorchuk

mloskot wrote:

I tried to find details on this project, but it looks there is no dedicated page on the Wiki The only information I found is the proposal

https://svn.boost.org/trac/boost/wiki/SoC2010

and lot of archived discussions, of course.

I'm not sure where to look for current codes. Has it been published? Perhaps it would make sense to have a dedicated wiki page like:

https://svn.boost.org/trac/boost/wiki/SoC2010SweeplineAlgorithm

We don't yet have documentation. Once we do I planned to integrate it into the boost.polygon documentation on the trunk along with the code. There will also be a paper and possibly a boostcon presentation at some point. We want to focus on getting the implementation of the algorithm correct first. Once it is ready for an API layer to go on top I'll engage the community on what kind of interface to provide for it. I have a prototype for a line segment concept in boost.polygon and we'll want to be sure to provide the diagram as a graph compatible with boost.graph. There are quite a few things still to do. I'm not sure I want to add a wiki to the list. Thanks, Luke

Andrii Sydorchuk wrote:

The test configuration includes tests with 1 000 000 input points. This was helpful to figure out some longrun bugs. Probably you should run those tests with release option.

Ah yes, benchmarking the debug version is a certainly not a good idea.

...

I was less successful on win32. I somehow didn't manage to configure qt as to be able to build the example program.

I've updated build script, you shouldn't have any troubles now.

Great, it works for me now. However, I have to admit that my own mistake was much simpler: I added the line "using qt : /Qt/4.7.0 ;" to the "wrong" user-config.jam file. But I checked that your fix is really required.

Did you use mingw or cygwin to compile it? I am using msvc 9.0 compiler on win32 and it works fine. However I received the same message using cygwin + gcc.

You're right, this was cygwin + gcc. I wasn't patient enough to wait for the results with MSVC-9 (as you mentioned before, the std debug checks can slow things down considerably, and MSVC-9 really takes these debug checks serious), but later forgot that I was using cygwin. Regards, Thomas

Thomas Klimpel wrote:

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.

Thanks for the link to vroni, I didn't know of its existence.

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.

I watched the whole thing play out with the GSOC 2006 spacial indexes project. That particular GSOC project was a special case in that it would have been reasonable for the mentor to fail the student, in my opinion, based on lack of progress and poor quality of the code. That's a tough call for a mentor to make, and I hope I'm never in the position where I have to make it. I feel very fortunate to have found a strong student this year.

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.

Should Andrii eventually provide for floating point numerical robustness I would expect that his work could be integrated into Boost.Geometry, perhaps as an extension that depends on minimal Boost.Polygon detail header files authored by Andrii. As you say, he has not coupled his implementation to my library so far. We will need to figure out the policies about cross library dependency between Polygon and Geometry, but that can wait until the first instance of such is suggested. Regards, Luke

Fernando Cacciola wrote:

...

Thanks for the link to vroni, I didn't know of its existence.

Have in mind that Vroni (which indeed is not free) does not use exact predicates so it is not robust. At least last time I checked (this is many many years ago) Martin might have have updated it since then though.

Yes, I noticed his discussion of relaxing epsilon and panic mode with some alarm. Depending on the details of his license we might benchmark against his library. Most non-free licenses allow benchmarking without charge. I didn't see a link to the code, and the web site implied that he does not give it out except by request. Regards, Luke