[GRASS-dev] [SoC] Status Report: Reimplementation of v.voronoi
and v.delaunay in GRASS GIS
Wolf Bergenheim
wolf+grass at bergenheim.net
Fri Jun 13 18:17:04 EDT 2008
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:>
More information about the Soc
mailing list