Re: [boost] GSoC Generic Sweep Algorithm

Subject: Re: [boost] GSoC Generic Sweep Algorithm
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2010-03-31 12:53:22

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