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.
Well, we still can use set for this kind of a problem and store all the information in a key. But I will definitely agree that it is better to split key and value data using map. 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.
I will have a look at your implementations. Thanks for the reference. 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.
I am a little bit confused. Lets say we have poitns A (0, 1), B (0, -1), C (1, 0). Our sweep line is moving along OX axis. Lets assume that points A and B are already processed by algorithm. So the next event is site C. Our map in this case will contain just one node with references to A and B points. So when we are adding point C we compare it's y-coord with y-coord of intersection of arcs made by A and B points. As you said in this case keys will be considered equal, as they have the same y-coordinate. Did I understood everything correctly by this moment? After that you proposed to remove current node (A, B) and reinsert new nodes (A, C), (C, B), am I right? Could you explain also "a pointer to justBefore_" meaning? Thank you forward. -- Best, Andrii Sydorchuk