Re: [boost] GSoC2010 Sweepline Algorithm

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

Andriy Sydorchuk wrote:
>> 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.
> 
> 
> That was the first idea I was thinking: creating generic wrapper
> around set datastructure (Adapter pattern) with definition of node
> comparer. So it will look smth like this:
> template <class T>
> struct NodeComparer {
> public:
> 
> }
> template <class T>
> class BeachLine {
> public: ...
> private: ...
>    typedef std::set<T, NodeComparer<T> > bl_set;
>    ...
>    bl_set beach_line_;
> }

Yep, from my code for the arbitrary angle polygon formation sweepline algorithm:

template <typename Unit>
class polygon_arbitrary_formation : public scanline_base<Unit> {
 ...
protected:
 typedef std::map<vertex_half_edge, active_tail_arbitrary*, less_vertex_half_edge> scanline_data;
 typedef typename scanline_data::iterator iterator;
 typedef typename scanline_data::const_iterator const_iterator;

 //data
 scanline_data scanData_;
 Unit x_;  //current x location
 bool justBefore_; //how to break ties using slope comparison
 ...
};

In my code I call it scanline instead of sweepline.  You want to use a map instead of a set because each element in the sweepline will need to have a data structure associated with it storing whatever data the problem you are solving requires.  My sweeplines are often parameterized on the element type for the map and I use the same sweepline template for polygon clipping and connectivity extraction, for example, which require different data be stored on the sweepline associated with the line segments crossing the sweepline.

Another tip that will help you with the sweepline algorithm is to use my approach of comparing keys in the sweepline by breaking ties based on slope comparion.  Typically sweepline considers keys to be equal if they evaluate to the same y value at the current x.  However, this makes it hard to manage the data structure if you are using a std::map without epsilon hackery.  Instead you can remove all elements from the sweepline data structure that are going to cross at the current x location and reinsert them in the reverse order by having a pointer to justBefore_ in the comparison functor that breaks ties in y value by slope in reverse order when removing elements and forward order when reinserting elements.  That way the data structure maintains its full proper ordering (and all important invariant) at all points during the execution of the algorithm.

> Yes, I've read about this kind of approach at this article: "An
> Efficient Implementation of Fortune's Plane-Sweep Algorithm for
> Voronoi 
> Diagrams" KennyWong, Hausi A. Muller. There are also few more nice
> ideas there.

I'll have to have a look at this paper.  Thanks for posting the reference.

Regards,
Luke