Re: [boost] GSoC2010 Sweepline Algorithm

Subject: Re: [boost] GSoC2010 Sweepline Algorithm
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2010-04-06 18:00:22

Andriy Sydorchuk wrote:
>> 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? 
> 
...
>
> 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).

That's what I thought.  Why not use a point plus implicit parabola above and below as your sweepline element instead of point pair and implicit parabolas between?  That way instead of two points your element contains only one and inserting a new point doesn't require the removal of any elements.

Regards,
Luke