Andriy Sydorchuk wrote:
Basically fast and robust Sweepline Algorithm requires implementation of next data structure: 1) Event Queue (priority queue). 2) Sweep Line (self-balancing binary search tree). 3) Output datastructures (voronoi vertices, triangulation edges, etc.).
These are intersting technical questions. I guess the most important thing to do is "writing the proposal for GSoC". But you are certainly right that a good understanding of the technical details helps writing a good proposal (and helps deciding whether you want to work on this problem at all).
Based on that I got next questions:
- Which kind of self-balancing binary trees is better for that kind of approach? I am thinking about Red-Black Trees in prefer to AVL trees, as sweepline algorithm requires more adding and deletion operations. And AVL trees are better for look up operations.
Most implementations I have seen so far simply tried to keep the implementation effort manageable, and made use of existing stl containers, using suitable custom comparison functors.
- STL library includes two generic implementations of self-balancing binary trees (red-black): map, set.
Indeed.
I am quite new with Boost library, but probably there are some more specific self-balancing binary tree implementations there?
Boost.Intrusive could also be intersting to look at.
- For Voronoi diagram and delaunay triangulation input data is set of points. What about input of the Medial Axis problem?
Strictly speaking, a single polygon (with potential holes). However, the actual input is often a polygonal domain (= set of non-overlapping polygons), and the output is normally equivalent to computing the medial axis for each polygon of the polygonal domain separately. Regards, Thomas