Subject: Re: [boost] GSoC2010 Sweepline Algorithm
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2010-03-31 06:35:33
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