Re: [boost] GSoC2010 Sweepline Algorithm

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

> 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:
  bool operator() (const T& node1, const T& node2) const {
  ...
  }
}

template <class T, class Comparer = NodeComparer<T> >
class BeachLine {
public: ...
private: ...
   typedef std::set<T, Comparer > 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: "An Efficient
Implementation of Fortune’s Plane-Sweep Algorithm for Voronoi
Diagrams" KennyWong, Hausi A. Muller. There are also few more nice ideas
there.
-- 
Best regards,
Andrii Sydorchuk