Andriy Sydorchuk wrote:
What is your definition of element? Does leaf and node elements contain the same data? I am thinking about element like (leaves and nodes are the same): struct SweepLineElement { private: const Point2d* point_left; const Point2d* point_right;
double getComparerValue(double line_x); }; So each node actually contains information about intersection point of two neighbour arcs from the sweep line, created by point_left and point_right at current X. Probably it's smth similar to the second approach.
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?
This is the main idea of sweep line data structure, isn't it? We insert new items based on comparison functor. Or do you mean precision problems as mentioned further ("If you ever try to use the tree when its invariant that all elements are in strict sorting order is violated you will get undefined behavior and either crash or infinitely loop")?
slope s1 = eval_slope_at_x(e1, x_);
What does "slope" exactly mean?
When working with line segments as I do I use comparison of the "rise over run" slope of the line segments to break ties when two line segments touch the sweepline at the same y value. When working with arcs you could use the tangent slope of arcs. Regards, Luke