Re: [boost] [GSoC 2010] Sweepline algorithm

Subject: Re: [boost] [GSoC 2010] Sweepline algorithm
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2010-03-27 22:46:56

Marcin Fatyga wrote:
> Hello,
> My name is Marcin Fatyga and I am doing double degree program in
> computer science and mathematics on Warsaw University. I would like
> to participate in GSoC 2010 - I would like to implement the sweepline
> algorithm and use it to solve the problems related to it.

I am pleased to meet you.

> In my project I would like to implement the sweepline and then use
> Fortune's Algorithm to solve the Voronoi Diagram's problem. Then I
> would provide some modifications to solve the two remaining connected
> problems : Delanuay triangulation and medial axis. All of these
> problems have many applications in differnet fields of science and
> solving them could be useful to may 
> users.

I too feel that a boost implementation of solutions for these problems would be useful.  The problems were solved decades ago with several different approaches and have become "text book" computational geometry.  I would suggest that you don't read text books and don't read licensed code.  Instead read academic papers.  Just because a problem was solved thirty years ago doesn't mean there is no value in solving it again.  Sometimes when a wheel is reinvested a better wheel is invented.  Cars wouldn't go very fast with wheels made of wood.  Progress in language and libraries raises all boats, and the polygon clippers of today put those from the '80s and '90s to absolute shame, but the problem was first solved in 1979.

> Though I don't have quite much experience with the boost library
> itself, I 
> am particularly interested in algorithms and have some experience
> with both C++ and generic programming.

I'd like to find out more about your background and experience.  You may prefer to discuss such details with me off list.

> Though there is no geometry library in current release, I can see it
> is in development phase. Should the project be integrated with it/use
> it? 

My suggestion would be to integrate to the degree helpful to you with the Boost.Polygon library currently accpeted to boost.  Its interfaces are not changing.  The Boost.Geometry library interfaces will become interoperable with Boost.Polygon when it is made ready for release.  In this way you will eventually be compatible with both libraries and won't be aiming at a moving target.

At this stage what is most important for you is to craft a compelling project proposal.  I would suugest reading past project proposals (if they are freely available) to get an idea what the program is looking for.  Also you should take the spatial indexes project as an object lesson, both in the success it had in becoming a project and the trouble it had in execution.  A world class 2D spatial index is something that could be expected to take nine months to implement.  It is not at all obvious to most people why that should be the case.  A good project proposal for solving these problems will address the challenge involved and show an understanding of what those challenges are and how they can be overcome in the timeframe of the project.  A review of academic literature that discusses what the problems are and how they were originally solved would be a good first step in that direction.  A plan and schedule for the implementation that shows progression on a laddered set of goals over time where each rung builds on the previous one is what I would propose.  I would be happy to answer any questions you might have.  I have implemented something like 12 sweepline algorithms in the boost Polygon library including overcoming challenges related to numerical robustness.  Understanding how I did it might help you craft your proposal.

Regards,
Luke