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.