Re: [boost] GSoC2010 Sweepline Algorithm

Subject: Re: [boost] GSoC2010 Sweepline Algorithm
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2010-04-05 14:50:39

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