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