Boost logo

Boost :

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 {
  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

Best regards,
Andrii Sydorchuk

Boost list run by bdawes at, gregod at, cpdaniel at, john at