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 <

[hidden email]>

To: Paul Kelly <

[hidden email]>

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.

[...]

_______________________________________________

grass-dev mailing list

[hidden email]
http://lists.osgeo.org/mailman/listinfo/grass-dev