Re: [boost] GSoC2010 Sweepline Algorithm

Subject: Re: [boost] GSoC2010 Sweepline Algorithm
From: Andriy Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2010-04-06 16:30:18

>
> 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