[GRASS-dev] [SoC] Status Report: Reimplementation of v.voronoi and v.delaunay in GRASS GIS

[Wolf Bergenheim]

Thanks for the update Martin! Yes the quad-edge is a nice structure, 
unfortunately it is quite expensive memory-wise. You might want to look 
at the winged-edge data structure also, which is very memory 
conservative. An idea could be to use different algorithms basing on 
size of the map and perhaps as a user choice.

Some references you should look up:

* Worboys, M.: GIS: A computing Perspective (http://worboys.duckham.org/)

* Delaunay triangulations in TIN creation: an overview and a linear-time 
algorithm (http://tinyurl.com/3s4s4h)

(I have more references should you want more)
--Wolf

On 14.06.2008 00:51, Martin Pavlovsky wrote:
> Hello everybody,
> 
> Status report #2 for week ending on 13th June, 2008.
> 
> This week I studied Guibas-Stolfi algorithm in much more depth. I am 
> getting a pretty good understanding of
> the underlying quad-edge data structure, which has some very neat 
> properties, such as is stores a graph and its dual, which is great, 
> since Voronoi diagram and Delaunay triangulation are dual to each other. 
> This can be used for very cheap switching from one to the other.
> 
> Next week I will be implementing the above mentioned algorithm.
> 
> There has not been any blockers so far. However, I had some duties at 
> the college,
> therefore my progress was slower than I expected.
> 
> Regards,
> 
> Martin Pavlovsky
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> grass-dev mailing list
> grass-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/grass-dev

-- 

<:3 )---- Wolf Bergenheim ----( 8:>