GSoC Generic Sweep Algorithm
Hi, I am writing my proposal for GSoC and I'm interested in writing a generic sweep algorithm. I want to write a generic algorithm which takes in functions to determine the priority of the elements to be considered in the sweep line, and a function to perform necessary computations at each such point. And supplement it with inbuilt functions for line sweep, angular sweep about a point for 2 dimensions and plane sweep for 3 dimensions. Also, implement some algorithms like Voronoi diagrams, Delaunay triangulations, visibility problems using the generic sweep algorithm. I have looked through the documentation and could not find anything related to this. Is there something I have missed? Also, could I contact anyone to discuss? Sweta Yamini Fourth Year Student Department of Computer Science And Engineering Indian Institute of Technology, Kharagpur
Hi Sweta, I am pleased to meet you. I guess Lucanus Simonson and other will happily help you to come up with a good proposal. I just want to comment on "plane sweep for 3 dimensions" and the "visibility problem". Sweta Yamini wrote:
And supplement it with inbuilt functions for line sweep, angular sweep about a point for 2 dimensions and plane sweep for 3 dimensions.
Neither Boost.Polygon nor Boost.Geometry currently have a good support for 3 dimensions. So it's better not to spend too much effort (or thoughts) on a plane sweep for 3 dimensions.
Also, implement some algorithms like Voronoi diagrams, Delaunay triangulations, visibility problems using the generic sweep algorithm.
The visibility problem also exists in 2D. We acually have to solve it for certain applications. I have no idea how our implementation works, but I wasn't aware that it could be solved by a sweepline algorithm. So if you really want to implement a solution for the visibility problem, it would even make sense for the 2D case.
I have looked through the documentation and could not find anything related to this.
Which documentation are you refering to? Do you mean <https://svn.boost.org/trac/boost/wiki/SoC2010> ? Or do you mean the documenation of Boost.Polygon or Boost.Geometry?
Is there something I have missed? Also, could I contact anyone to discuss?
I don't think there is anything you have missed. We expect that you discuss it with us on this mailing list. Regards, Thomas
Thomas Klimpel wrote:
Also, implement some algorithms like Voronoi diagrams, Delaunay triangulations, visibility problems using the generic sweep algorithm.
The visibility problem also exists in 2D. We acually have to solve it for certain applications. I have no idea how our implementation works, but I wasn't aware that it could be solved by a sweepline algorithm. So if you really want to implement a solution for the visibility problem, it would even make sense for the 2D case.
My preferred method for computing visibility in a direction (as opposed to 360 visibility) is to slice whitespace between polygons into trapezoids with slicing lines parallel to the visibility direction and then you can do connectivity extraction between original polygons and whitespace trapezoids. The output is a connectivity graph that shows which polygons are visible from eachother through which trapezoids. In the special case of manhattan geometry and axis-parallel visibility directions we have quite a bit of application for this. Both trapezoidization and connectivity extraction are solved by sweepline in my implementation of them, and could be conbined into a single pass of sweepline to solve (directional) visibility. I have not studied for given much thought to general 360-degree visibility. Since we use polarized light and axis-parallel polygons we tend to only care about axis parallel visibility. However, my hunch is that it is also solveable by sweepline, and that Sweta is thinking in exactly the right direction. Visibility is a very useful problem to have solved, and other problems like largest enclosed rectangle depend on visibility. Regards, Luke
Sweta Yamini wrote:
I have looked through the documentation and could not find anything related to this.
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. Regards, Luke
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.
participants (3)
-
Simonson, Lucanus J -
Sweta Yamini -
Thomas Klimpel