Geometry Boost List: [ggl] Fwd: Re: [boost] [polygon] [GSOC] voronoi diagram of line segments

Subject: [ggl] Fwd: Re: [boost] [polygon] [GSOC] voronoi diagram of line segments
From: Mateusz Loskot (mateusz)
Date: 2010-10-26 16:20:09

Hi,

Thomas refers to our projects, so I thought it's good to notify the list:

Mat

-------- Original Message --------
Subject: Re: [boost] [polygon] [GSOC] voronoi diagram of line segments
Date: Tue, 26 Oct 2010 21:53:10 +0200
From: Thomas Klimpel <Thomas.Klimpel_at_[hidden]>
Reply-To: boost_at_[hidden]
To: boost_at_[hidden] <boost_at_[hidden]>

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
_______________________________________________
Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost