Re: [boost] GSoC2010 Sweepline Algorithm

Subject: Re: [boost] GSoC2010 Sweepline Algorithm
From: Andriy Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2010-04-03 19:53:22

Maybe it is better to write proposal at first and after that discuss
technical questions. But still I didn't get everything.

>  Each will require that elements need to be removed from the sweepline and
> new elements inserted.

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.

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?

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?

An alternative approach would be to make the comparison depend on the
> current Y.

It should depend on the current Y in anyway, or am I wrong? Site events with
different y-coordinates change sweep line data in different ways.

Thanks,
Andrii Sydorchuk