Re: [boost] GSoC2010 Sweepline Algorithm

Subject: Re: [boost] GSoC2010 Sweepline Algorithm
From: Andriy Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2010-03-31 19:05:26

>
> 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_;
}

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.

Yes, I've read about this kind of approach at this article  .