
Boost : 
Subject: Re: [boost] GSoC2010 Sweepline Algorithm
From: Andriy Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 20100406 16:30:18
>
> Using double for the comparer value won't be robust. If the coordinate
> type is a builtin 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(xcoord) 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 ycoordinate.
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 ycoord return xcoord.
if (DOUBLE_EQ(point_left>y, line_y))
return point_left>x;
// If right point and sweep line have the same ycoord return xcoord.
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 ycoords, 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 xcoord 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk