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. 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. 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. 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? Best wishes Marcin Fatyga
on 27.03.2010 at 11:15 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.
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.
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.
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?
hi there are you familiar with "Numerical Recipies" book? in the third edition there is given a complete solution to the delanuay triangulation and voronoi diagram problems perhaps the problem your are trying to solve is already solved -- Pavel
On Sat, Mar 27, 2010 at 01:06:04PM +0300, DE wrote:
are you familiar with "Numerical Recipies" book? in the third edition there is given a complete solution to the delanuay triangulation and voronoi diagram problems perhaps the problem your are trying to solve is already solved
The code from the Numerical Recepies in X books is licensed under a bunch of licenses, all that are completely unusable for Boost (or in my opinion, anyone). Basically, the only license they have that doesn't cost you money is the "immediate license" in which you have to type the code in onto your personal computer, and may not redistribute the code or binaries using the code, nor use it for commercial purposes. Heck, I'd guess that being inspired by the code would probably count as a derived work and be useless as well. (this is all according to my Numerical Recepies in C 2e) -- Lars Viklund | zao@acc.umu.se
on 27.03.2010 at 14:48 Lars Viklund wrote :
The code from the Numerical Recepies in X books is licensed under a bunch of licenses, all that are completely unusable for Boost (or in my opinion, anyone).
Basically, the only license they have that doesn't cost you money is the "immediate license" in which you have to type the code in onto your personal computer, and may not redistribute the code or binaries using the code, nor use it for commercial purposes.
Heck, I'd guess that being inspired by the code would probably count as a derived work and be useless as well.
(this is all according to my Numerical Recepies in C 2e) i were talking about algorithms, not the code
algorithms are not licensed even if so there are references in the book where you always can find an algorithm free of charge (or just paying for the book) -- Pavel
DE wrote:
on 27.03.2010 at 14:48 Lars Viklund wrote :
The code from the Numerical Recepies in X books is licensed under a bunch of licenses, all that are completely unusable for Boost (or in my opinion, anyone).
Basically, the only license they have that doesn't cost you money is the "immediate license" in which you have to type the code in onto your personal computer, and may not redistribute the code or binaries using the code, nor use it for commercial purposes.
Heck, I'd guess that being inspired by the code would probably count as a derived work and be useless as well.
(this is all according to my Numerical Recepies in C 2e) i were talking about algorithms, not the code
algorithms are not licensed
But in some countries they are patented..
even if so there are references in the book where you always can find an algorithm free of charge (or just paying for the book)
..Which makes the unusable regardless of the reference source. But I don't know the particular algorithm in question so perhaps it's not a problem :-) -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org (msn) - grafik/redshift-software.com -- 102708583/icq - grafikrobot/aim,yahoo,skype,efnet,gmail
DE wrote:
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. [SNIP] 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?
hi there are you familiar with "Numerical Recipies" book? in the third edition there is given a complete solution to the delanuay triangulation and voronoi diagram problems perhaps the problem your are trying to solve is already solved
Pavel, do you really think your comment is useful for a student inquiring about the "Sweepline Algorithm" project idea from <https://svn.boost.org/trac/boost/wiki/SoC2010>? You could have discussed your objections with Lucanus Simonson when he proposed the idea: <http://lists.boost.org/Archives/boost/2010/03/162870.php>. Regards, Thomas
on 27.03.2010 at 15:37 Thomas Klimpel wrote :
Pavel,
do you really think your comment is useful for a student inquiring about the "Sweepline Algorithm" project idea from <https://svn.boost.org/trac/boost/wiki/SoC2010>? You could have discussed your objections with Lucanus Simonson when he proposed the idea: <http://lists.boost.org/Archives/boost/2010/03/162870.php>.
sorry, i missed that post anyway i think more info on the problem is better than lack of it you can choose from a variety of opportunities and its better late than never -- Pavel
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.
Hi Marcin, I think that there was some discussion a week or two ago on this topic. You might want to check the mailing list archives to see what the outcome was (if any). Andrew Sutton andrew.n.sutton@gmail.com
Marcin Fatyga wrote:
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?
You could look at the 'Spatial Indexes' project from a previous GSoC: <http://lists.boost.org/Archives/boost/2008/09/142219.php>. In that case, the project itself just used Boost.Geometry, and the integration into Boost.Geometry was done by Barend Gehrels: <http://lists.boost.org/Archives/boost/2009/03/150165.php>. Just because I used Boost.Geometry in my explanation doesn't mean that the project should use Boost.Geometry. It's probably more a Boost.Polygon project, because Lucanus Simonson is a possible mentor for it. Also, integer coordinates could make the impossible task at hand a bit easier, and Boost.Polygon already has some algorithms that are only implemented for integer coordinates.
In my project I would like to implement the sweepline and then use Fortune's Algorithm to solve the Voronoi Diagram's problem.
I would love to comment a bit on this, but I guess it is better to just make clear that you are welcome, and let Lucanus Simonson, Barend Gehrels, Mateusz Loskot and the other geometry experts do the discussions about the technical details. Regards, Thomas
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
participants (7)
-
Andrew Sutton -
DE -
Lars Viklund -
Marcin Fatyga -
Rene Rivera -
Simonson, Lucanus J -
Thomas Klimpel