Andriy Sydorchuk wrote:
Using double for the comparer value won't be robust. If the coordinate type is a built-in it is better to store points by value in you data structures because you save one level of pointer indirection and get better cache utilization. What happens when a new input event comes in with a point between point_left and point_right?
...
Basically we find a node that corresponds to (point_left, point_right). Find to which point intersection with new arc corresponds and insert to new arcs, like: (point_left, new_point), (new_point, point_left).
That's what I thought. Why not use a point plus implicit parabola above and below as your sweepline element instead of point pair and implicit parabolas between? That way instead of two points your element contains only one and inserting a new point doesn't require the removal of any elements. Regards, Luke