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.
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.
* 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.