Re: [boost] GSoC2010 Sweepline Algorithm

Subject: Re: [boost] GSoC2010 Sweepline Algorithm
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2010-03-31 13:14:45

Andriy Sydorchuk wrote:
> Hi, Boost Community!
> 
> I am interested in participation in GSoC 2010.
> The project I liked the most is the generic implementation of
> Sweepline Algorithm.
> 
> 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.). 
> 
> 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.
>    - STL library includes two generic implementations of
>    self-balancing binary trees (red-black): map, set.
>    I am quite new with Boost library, but probably there are some more
>    specific self-balancing binary tree implementations there?
>    - For Voronoi diagram and delaunay triangulation input data is set
>    of points.
>    What about input of the Medial Axis problem?

You should absolutely use stl map or set.  See:

Ruud, B. Building a Mutable Set, 2003. Retrieved March 3,
2009, from Dr. Dobb's Portal:
http://www.ddj.com/cpp/184401664

For an explanation of how to use map or set for a sweepline.  You don't need to use the optimization of casting away const of the key.  Just remove and reinsert with a new key.  That's what I do.

I have already implemented something like 12 sweepline algorithms in Boost.Polygon using the STL data structures.

You can use a map or set for the event queue, otherwise use a stl vector with the stl heap operations if you are performance conscious.  This is an optimization that can be performed after you get the algorithm working.  It is better to take all of your original input events and sort them in a vector then merge them with events generated by the sweepline itself on the fly.  Since a sorted vector satisfies the properties of a heap you could use it with the stl heap operations, however, it requires that your sweep algorithm know the data structure its input is coming from, and I have always abstracted that away with iterator interfaces.  It is reasonable to assume that the input is a vector, however.

If you implement Medial Axis with sweepline that works on non-convex polygons with holes you have implmented an algorithm that can also handle multiple non-overlapping polygons.

Regards,
Luke