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?
Well it depends on the type of input event: 1) Site event: a) Find, position where new node should be inserted, using lower_bound function with temporary node in the sweep line. For using lower_bound function we implement our NodeComparer: template <class T> struct NodeComparer { const double& line_y_; NodeComparer(double line_y) : line_y_(line_y) {} // Compares two nodes based on the parabolas interection points. bool operator() (const T& t1, const T& t2) const { return t1.getComparerValue(line_y) < t2.getComparerValue(line_y_); } }; getComparerValue may be implemented in such a way (but as you said there probably might be problems with precisions): // Get intersection point(x-coord) of parabolic arcs made by points from current node and sweep line at line_y. double SweepLineElement::getComparerValue(double line_y) const { // If right and left points have the same y-coordinate. if (DOUBLE_EQ(point_left->y, point_right->y)) return (point_left->x + point_right->x) / 2.0; // If left point and sweep line have the same y-coord return x-coord. if (DOUBLE_EQ(point_left->y, line_y)) return point_left->x; // If right point and sweep line have the same y-coord return x-coord. if (DOUBLE_EQ(point_right->y, line_y)) return point_right->x; // Parabola representation: y = a*X*X + b*X + c. // We get our parabola parameters based on: // (x - point->x)^2 + (y - point->y)^2 = (y - line_y)^2. // Left parabola parameters. double a1 = 0.5 / (point_left->y - line_y); double b1 = -a1 * 2.0 * point_left->x; double c1 = a1 * SQR(point_left->x) + point_left->y + line_y; // Right parabola parameters. double a2 = 0.5 / (point_right->y - line_y); double b2 = -a2 * 2.0 * point_right->x; double c2 = a2 * SQR(point_right->x) + point_right->y + line_y; // As left and right points don't have the same y-coords, there // will be two intersection points. We can find them from next condition: // a1*X^2 + b1*X + c1 = a2*X^2 + b2*X + c2 or // (a1 - a2)*X^2 + (b1 - b2)*X + c1 - c2 = 0. double a = a1 - a2; double b = b1 - b2; double c = c1 - c2; double sqrt_D = sqrt(SQR(b) - 4.0 * a * c); double x1 = (-b - sqrt_D) * 0.5 / a; double x2 = (-b + sqrt_D) * 0.5 / a; // We are interested only in intersection point x-coord that is created // by left parabola on the left and right parabola on the right. double deriv1 = 2.0 * a1 * x1 + b1; double deriv2 = 2.0 * a2 * x1 + b2; if(deriv1 > deriv2) return x1; return x2; } b) Insert two new nodes in our sweep line structure at appropriate postions, update circle events queue, update output data structures. 2) Circle event: a) erase nodes that made current circle event; b) insert new node, update circle events queue, update output data structures. 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). 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.
Probably the reason I misunderstood you at first, is that voronoi sweep line functionality differs a little bit from finding intersections of set of segment. -- Best regards, Andrii Sydorchuk