Re: [boost] GSoC2010 Sweepline Algorithm

Subject: Re: [boost] GSoC2010 Sweepline Algorithm
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2010-04-01 21:16:44

Andriy Sydorchuk wrote:
>  Instead you can remove all elements from the sweepline data
> structure that 
>> are going to cross at the current x location and reinsert them in the
>> reverse order by having a pointer to justBefore_ in the comparison
>> functor that breaks ties in y value by slope in reverse order when
>> removing elements and forward order when reinserting elements.
> 
> 
> I am a little bit confused. Lets say we have poitns A (0, 1), B (0,
> -1), C (1, 0). Our sweep line is moving along OX axis. Lets assume
> that points A and B are already processed by algorithm. So the next
> event is site C. Our map in this case will contain just one node with
> references to A and B points. So when we are adding point C we
> compare it's y-coord with y-coord of intersection of arcs made by A
> and B points. As you said in this case keys will be considered equal,
> as they have the same y-coordinate. Did I understood everything
> correctly by this moment? After that you proposed to remove current
> node (A, B) and reinsert new nodes (A, C), (C, B), am I right? Could
> you explain also "a pointer to justBefore_" meaning? Thank you
> forward. 

What I mean by a pointer to justBefore_ has to do with what you have to do in the eventuality that you need to remove and insert many elements in the sweepline data structure at more than one colinear point.  Imagine you have a 10x10 matrix of sites in the set of points that are arranged in a rectangular grid and a sweeline that is vertical and moving along the X axis.  The sweepline will reach 10 points simultaneously at the same x stopping point.  Each will require that elements need to be removed from the sweepline and new elements inserted.  If you try to remove elements and then insert elements for each of the ten points one at a time how do you manage the sweepline data structure such that the invariant that all its elements are in strict sorting order at all stages of execution?  The way I do it is by breaking ties in y intercept on the sweepline with the slope of the intercept on the sweepline.  I remove all elements first using a reverse sorting order on slope and then change the sorting order on slope to forward and then insert all new elements.  The justBefore_ value tells the comparison functor to sort slopes in reverse order if it is true, otherwise forward order.

An alternative approach would be to make the comparison depend on the current Y.  You scan event points from low to high on the sweepline.  Your comparison functor can compare slopes in reverse order if their y intercept is larger than the current y and forward order if it is less than or equal to the current y.

 template <element_type>
 struct less_functor_by_x_and_y {
    coordinate *x_;
    coordinate *y_;
    less_functor_by_x_and_y (coordinate x, coordinate y) : x_(x), y_(y) {}
    bool operator()(const element_type& e1, const element_type& e2) {
        coordinate y1 = eval_at_x(e1, x_);
        coordinate y2 = eval_at_x(e2, x_);
      if(y1 < y2) return true;
      if(y2 < y1) return false;
      slope s1 = eval_slope_at_x(e1, x_);
      slope s2 = eval_slope_at_x(e2, x_);
      if(y1 < y_) return s2 < s1; //compare slopes in reverse order
      return s1 < s1; //y_ >= y1 and y2, compare slopes in forward order
    }
 }; 

The order of elements that are going to cross at a certain x and y are in the correct sorting order when the sweepline reaches that point if their slopes are compared in reverse order.  To remove and reinsert those elements such that they are effectively swapped you remove them then update y_ to be equal to y and reinsert them.

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.

It is managing the sweepline data structure and getting the comparison functor right that is the tricky part of implementing sweepline.  If your eval_at_x and eval_slope_at_x are not numerically robust then you can't ensure a strict ordering of elements in the sweepline and the execution of the code will fail catastrophically.

Regards,
Luke