Re: [boost] GSoC2010 Sweepline Algorithm

Subject: Re: [boost] GSoC2010 Sweepline Algorithm
From: Andriy Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2010-04-01 20:31:56

>
> You want to use a map instead of a set because each element in the
> sweepline will need to have a data structure associated with it storing
> whatever data the problem you are solving requires.

Well, we still can use set for this kind of a problem and store all the
information in a key. But I will definitely agree that it is better to split
key and value data using map.

 My sweeplines are often parameterized on the element type for the map and I
> use the same sweepline template for polygon clipping and connectivity
> extraction, for example, which require different data be stored on the
> sweepline associated with the line segments crossing the sweepline.

I will have a look at your implementations. Thanks for the reference.

 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.

-- 
Best,
Andrii Sydorchuk