Boost logo

Boost :

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


Andriy Sydorchuk wrote:
>> 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.
>
>
> The reason is I read such kind of approach in this book:
> "Computational Geometry: Algorithms and Applicatoins" by* *Mark de
> Berg.
>
>
> Quota (page 156): "The beach line is represented by a balanced binary
> search tree T; it is the status structure. Its leaves correspond to
> the arcs of the beach line - which is x-monotone - in an ordered
> manner; the leftmost leaf represents the leftmost arc, the next leaf
> represents the second leftmost arc, and so on. Each leaf L stores the
> site that defines the arc it represents. The internal nodes of T
> represent the breakpoint on the beach line. A breakpoint is stored at
> an internal node by an ordered tuple of sites (pi, pj), where pi
> defines the parabola left of the breakpoint and pj defines the
> parabola to the right".
> I simplified this approach to be used without leaves, in this case all
> elements of the map will be the same structures.
>
> Why not use a point...
>
> Do you mean intersection point of above and below parabolas, or just
> site point?
> If the answer is intersection point, you may skip next questions.
> In case our element contains only one point, how would you implement
> insertion operation? For example we insert new element, how do we
> compare new element with elements from sweep line (we only know site
> point corresponding to the element, it seems to me that this
> information is not enough)?

I see now that your element is actually a bisector of two sites, the moving point at which two parabolas intersect that traces line segments of the veronoi diagram as the sweepline advances.

Regards,
Luke


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk