[GRASS-dev] Re: Possible Extension (fwd)

[Paul Kelly]

Hi Markus,
As you are working on v.voronoi you might find the following comments 
about its algorithm from Martin Pavlovsky (developer of v.delaunay2) 
interesting. Basically a more efficient implementation of the current 
algorithm was what he thought was best too---he started work on that but 
never got it finished.

Paul

---------- Forwarded message ----------
Date: Mon, 18 Aug 2008 11:27:41 +0200
From: Martin Pavlovsky <mpavlovsky at gmail.com>
To: Paul Kelly <paul at stjohnspoint.co.uk>
Subject: Re: Possible Extension

[...]
I am just finishing the testing of v.delaunay2 module. The module can output
delaunay triangulation as a set of edges or areas. I will send you the
module itself around noon today. Even though I  haven't encountered any
bugs.and the module has been stable in all tests, I still think that the
code can be improved, therefore I do not recommend it for production use at
this stage. I used GRASS in/out handling from original v.voronoi as a
guideline for in/out of my module.

The original Guibas-Stolfi algorithm was primarily designed for construction
of voronoi diagrams. Computation of voronoi diagram can be greatly
simplified by working with its dual delaunay triangulation. This allows a
clean separation of topological properties from geometrical properties.
Voronoi diagram can be then easily computed from delaunay. Therefore
Delaunay triangulation can be considered as a by-product of the algorithm.
However, this is true only for original version of G-S alg. I implemented a
modified version which uses a winged edge data structure instead of
quad-edge. This saves memory and makes the algorithm much faster. On the
other hand the "switching" from delaunay to voronoi cannot be done so
easily/cheaply.

Now I have two options, how to proceed with v.voronoi2, which I haven't
created yet. I can change winged-edge for quad-edge, which I should be able
to do in less than a week. This means that most of the code will be shared
between the modules. Module v,delaunay2 will continue utilise winged-edge as
it does now and v.voronoi2 will use more complex quad-edge. However,
performance of v.voronoi2 will suffer in comparison to v.delaunay2. Or I can
implement Fortune sweepline algorithm, which would take me roughly 4 weeks.
I still have more that 6 weeks of summer holidays, so it wouldn't be a
problem. Advantage of Fortune over G-S with quad-edge is that it can be
roughly 20-25% faster than G-S when implemented with care. Obvious
disadvantage is the time span it takes to write the code of another
algorithm.

[...]