Re: [boost] GSoC Generic Sweep Algorithm

Subject: Re: [boost] GSoC Generic Sweep Algorithm
From: Sweta Yamini (koolkitty113_at_[hidden])
Date: 2010-04-09 07:31:15

Thank you very much for your prompt reply, and I am very sorry for not
keeping up on the mailing list as I had a very rough week.

Please see my documentation here:
> https://svn.boost.org/svn/boost/sandbox/gtl/doc/index.htm
>
> On this page you will find the Boostcon paper and presentation helpful.
>  Some of the references from the paper will also be helpful.
>

I have read the references, thank you once again, and it helped me a lot to
understand the basics. I have drafted a proposal, but I am not sure if I got
the details right.

Woul the following proposal cover the basic points of the problem described?

The following are the components of a sweepline algorithm which must be
available/customizable.

   - A priority queue of event points. The points can be static and
   predefined, or dynamically generated at each event point.
   - A scanline or beechline holding the intermediate data, typically a
   binary search tree.
   - Output, partly generate at each step to cumulatively give the output.

Event Points -

Input to the algorithm needs a list of points, or start point. A comparator
to compare the points to form the priority queue. An interface for addition
of new event points if generated at a later stage.

Scanline -

A generic class to contain details about the data to be stored for scanline.
A comparator to compare eventpoint with scanline data to pinpoint the left
and right scanline structures to the event point.

Process -

A function which will perform the necessary operations to be done at each
eventpoint to generate output an update scanline.

Output -

Output will be generated as the user desires.

The following are particular functions written which the user can directly
use instead of writing the code again. These are to make the use of the
sweepline more easy.

   - The commonly used sweeplines are line sweep and angular sweep in two
   dimensions. So, implement comparators for these two types. x sweep, y sweep
   [by using a flag parameter] clockwise sweep, anticlockwise sweep [againt
   using a flag parameter].
   - Commonly used scanline data structures are line segments. So, implement
   scanline type linesegment, and write comparator functions to find the two
   lines on either end of a point, in both line an angular sweep, i.e using the
   evenpoint comparators.

Implement basic algorithms - Voronoi diagrams, medial axis problem, 360
egree visibility problem, to serve as both a ready-made solutions and
guidelines / sample problems to help user use the generic sweepline
algorithm.

Deliverables of the project -

   - A generic sweepline implementation.
   - A set of assisting functions to simplify usage of the sweepline
   algorithm.
   - A set of implemented algorithms.
   - Unit tests for each module.
   - A tutorial on how to use the generic sweepline algorithm to perform any
   sweep.
   - Manuals and documentation.