[SoC] Summer of Code Project Ideas
I'm officially soliciting ideas for student projects for this year's 2010 Summer of Code. If you're maintaining or contributing to a library and have some non-trivial items on a TODO list, then suggesting that as a possible student project may be a viable idea. Unlike the previous years, I think that proposing work on sandbox libraries would also be a good idea. There is a substantial amount of work in the sandbox that might be well-suited for student projects and eventual (I hope) acceptance to Boost. In general student projects should be tightly focused with a clear set of goals to getting their work integrated into a mainline development branch (be that trunk or sandbox). In general, we've noticed that ground-up libraries almost always fail to be integrated or released independently since they require a commitment longer than the summer. There are, of course, notable exceptions to this rule. If you are going to propose a student project, please keep in mind the following things: 1. Students tend to go away in the fall. 2. If their work isn't tended after August, then it's largely forgotten 3. If the student is gone and their work is forgotten, then the project didn't really succeed. If you write down or submit a project, please include your expectations for that work. And try to keep it small. That said, if you're too precise in the specifications, we'll going to get a couple dozen proposals that simply reiterate your expectations. But that's the nature of the beast. Good ideas for projects might be: == Data Structures and Algorithms== Admittedly these have little impact on overall quality of Boost, but make a nice sandbox for students to work in and can result in surprisingly good code. Over the course of the summer 1 or 2 related data structures or a family of related generic algorithms seems to make a nicely packaged project. ==Extensions for Existing Libraries== There are a number of Boost libraries that are very amenable to extension (e.g., BGL, GIL, Math, etc.). Basically any library that doesn't have a finite feature space. Non-intrusive changes (i.e., those that don't require hacking on the existing bits) typically make good summer of code projects. == Infrastructure Projects== Projects that aren't part of Boost, but help us improve the quality of Boost might make decent projects, but we've never had one proposed or accepted that I'm aware of. Remember, we can't accept documentation projects so "Write my documents" will not be a good student project (unfortunately ;) ==Applications of Boost== This is a little different... It might be a good idea to have students build real (example?) applications that use the Boost C++ Libraries. There are a number of real benefits to having students work in this space. First, these applications are very obvious clients of Boost. They can provide immediate feedback on issues with the interface, usability, correctness, performance, documentation, etc. Second, they might make really good examples of best practice for using Boost. Third, they probably make nice student projects. If you have any ideas, let's hear them. And remember, funded projects need mentors. Andrew Sutton andrew.n.sutton@gmail.com
I'm officially soliciting ideas for student projects for this year's 2010 Summer of Code.
A quick follow-up... Each project idea should give some indication of prerequisites for the student. For example BGL projects have a basic prerequisite of graph theory. You can browse ideas from previous years here: https://svn.boost.org/trac/boost/wiki/SoCPrevious The current list of projects is here: https://svn.boost.org/trac/boost/wiki/SoC2010 Andrew Sutton andrew.n.sutton@gmail.com
On 03/08/2010 08:52 AM, Andrew Sutton wrote:
I'm officially soliciting ideas for student projects for this year's 2010 Summer of Code.
If you have any ideas, let's hear them. And remember, funded projects need mentors.
Here are two project ideas that have come up quite recently (one on IRC, the other on the boost.python list), and which I'd both be willing to mentor: * I started a 'boost.xml' library (right now in https://svn.boost.org/svn/boost/sandbox/xml/) a long time ago, which I have never found enough time and energy to bring to a formal boost submission. Having a proper XML library as part of boost would be very useful, in particular if "proper XML" goes beyond the basics such as parsing. (There already are lots of half-baked XML parsers, but few fully conform to the spec, or yield well performing in-memory representations that can be traversed via XML-specific tools such as XPath.) * Boost.Python has a couple of domains that could be improved. Here are two: - Add (better) support for NumPy bindings. - Improve the converter registry to avoid conflicts when multiple extension modules try to expose the same C++ types. - Add bindings for other Python C API functions, such as exception handling. All of the above can be formulated in a way to yield bite-sized deliverables, increasing the chance that at least some of it may be completed and included into boost by the end of the summer. Thanks, Stefan -- ...ich hab' noch einen Koffer in Berlin...
Here are two project ideas that have come up quite recently (one on IRC, the other on the boost.python list), and which I'd both be willing to mentor:
Thanks Stefan. I tweaked the submissions a little bit. I like the re-proposal of the XML library. I think that should be expanded to include concrete goals. Where does it stand now? What would you like to see finished in 4-5 months time? Andrew Sutton andrew.n.sutton@gmail.com
Il 08/03/2010 14:52, Andrew Sutton ha scritto:
I'm officially soliciting ideas for student projects for this year's 2010 Summer of Code.
[...]
==Applications of Boost== This is a little different... It might be a good idea to have students build real (example?) applications that use the Boost C++ Libraries. There are a number of real benefits to having students work in this space. First, these applications are very obvious clients of Boost. They can provide immediate feedback on issues with the interface, usability, correctness, performance, documentation, etc. Second, they might make really good examples of best practice for using Boost. Third, they probably make nice student projects.
Hi all, I'm developing a symbolic circuit solutor based on Qt and Boost for my degree thesis and it will be ready in his first beta version on June. What about using this as base for an example of Application of Boost? I use BGL, Property Tree, Any, Variant and so on, so I think it's a good example of how boost libraries can work together. Michele
==Applications of Boost== This is a little different... It might be a good idea to have students build real (example?) applications that use the Boost C++ Libraries. There are a number of real benefits to having students work in this space. First, these applications are very obvious clients of Boost. They can provide immediate feedback on issues with the interface, usability, correctness, performance, documentation, etc. Second, they might make really good examples of best practice for using Boost. Third, they probably make nice student projects.
Hi all, I'm developing a symbolic circuit solutor based on Qt and Boost for my degree thesis and it will be ready in his first beta version on June.
What about using this as base for an example of Application of Boost?
I use BGL, Property Tree, Any, Variant and so on, so I think it's a good example of how boost libraries can work together.
I think I may have opened a can of worms that I'm not quite prepared to address :) There are a number of issues with proposing an application. It's could be the case that applications like this will never be part of the BGL core release since they tend to be very application-specific and somebody would have to commit time and effort to maintaining them (which is actually a huge problem). If the work includes the extension of the library (e.g., new algorithms to the BGL), then there's inherent value for that library. You would probably have to find some kind of "sweet spot" in the proposal. How much are you contributing back to the library or Boost in general, vs. just using the libraries. Andrew Sutton andrew.n.sutton@gmail.com
Il 08/03/2010 17:10, Andrew Sutton ha scritto:
I think I may have opened a can of worms that I'm not quite prepared to address :)
There are a number of issues with proposing an application. It's could be the case that applications like this will never be part of the BGL core release since they tend to be very application-specific and somebody would have to commit time and effort to maintaining them (which is actually a huge problem).
If the work includes the extension of the library (e.g., new algorithms to the BGL), then there's inherent value for that library. You would probably have to find some kind of "sweet spot" in the proposal. How much are you contributing back to the library or Boost in general, vs. just using the libraries.
Andrew Sutton andrew.n.sutton@gmail.com
Of course, I've not just used BGL but also developed new generic algorithms to use with my software. I have to work a little bit again on those algorithms before propose them, however code just works fine.
If the work includes the extension of the library (e.g., new algorithms to the BGL), then there's inherent value for that library. You would probably have to find some kind of "sweet spot" in the proposal. How much are you contributing back to the library or Boost in general, vs. just using the libraries.
I know :) I was actually referring to the code your Jan/Feb submission. If you submit a proposal, you might consider focusing more on the BGL side of proposal. Consider extending your work or adding a couple more algorithms. It would be a lot easier to accept. Your thesis project could be described as a "testing ground" for that work, although it probably has great value as an example also. Hopefully, you don't take from what I just wrote that I think that BGL are more important than your thesis. I'm just referring to how you might write the proposal to make it more competitive. Andrew Sutton andrew.n.sutton@gmail.com
Il 08/03/2010 22:16, Andrew Sutton ha scritto:
Hopefully, you don't take from what I just wrote that I think that BGL are more important than your thesis. I'm just referring to how you might write the proposal to make it more competitive.
Sure, don't worry about! ;-) What's the timeline for BGL-algorithms proposal? My idea is to submit two kind of algorithms as solution of the same problem, two-graphs common-tree problem, where the latter is the refinement of the former (better performance, about 300%!). Authors are Grimbleby for the former, and Schach for the latter. MRT-based (Schach) implementation is ready, generic as BGL algorithms need to be, and it works fine (I use it in my degree thesis). I've not found since January/February a little bit of time to develop the other algorithm, I'm very sorry. However, I can write down not-generalized pseudo-code for the Grimbleby algorithm (to drive to C++ code, of course), and submit the one by Schach, as-is. What about this way? Michele
What's the timeline for BGL-algorithms proposal? My idea is to submit two kind of algorithms as solution of the same problem, two-graphs common-tree problem, where the latter is the refinement of the former (better performance, about 300%!). Authors are Grimbleby for the former, and Schach for the latter. MRT-based (Schach) implementation is ready, generic as BGL algorithms need to be, and it works fine (I use it in my degree thesis). I've not found since January/February a little bit of time to develop the other algorithm, I'm very sorry. However, I can write down not-generalized pseudo-code for the Grimbleby algorithm (to drive to C++ code, of course), and submit the one by Schach, as-is.
What about this way?
Student submissions don't start for a couple of weeks so there's a lot of time to refine your proposal. The actual SoC timeline is here: http://socghop.appspot.com/document/show/gsoc_program/google/gsoc2010/timeli... Hit the HTML link for a Google Calendar, if you want a more informative view. Andrew Sutton andrew.n.sutton@gmail.com
Andrew Sutton wrote:
==Extensions for Existing Libraries== There are a number of Boost libraries that are very amenable to extension (e.g., BGL, GIL, Math, etc.).
Boost.Geometry Within Boost.Geometry, we have discussed participation in the GSoC a bit. However, we've decided to not to propose or mentor any projects due to amount of work we need to get done ASAP to include the library in one of the upcoming Boost releases. I have mentored one GSoC project myself (though, not for Boost) and I would not be able to commit to mentoring while working on the library preparation at the same time. However, I personally thing, that if someone else would be interested in mentoring a student working on some project for Boost.Geometry, that would be great.
== Infrastructure Projects== Projects that aren't part of Boost, but help us improve the quality of Boost might make decent projects, but we've never had one proposed or accepted that I'm aware of. Remember, we can't accept documentation projects so "Write my documents" will not be a good student project (unfortunately ;)
What could that be? Compilation farm? Developing regression resting? May be something like integrating Boost regression tests with existing systems like Buildbot, Hudson, etc. This could increase potential of attaching new test environments.
==Applications of Boost== This is a little different... It might be a good idea to have students build real (example?) applications that use the Boost C++ Libraries. There are a number of real benefits to having students work in this space. First, these applications are very obvious clients of Boost. They can provide immediate feedback on issues with the interface, usability, correctness, performance, documentation, etc. Second, they might make really good examples of best practice for using Boost. Third, they probably make nice student projects.
It could also include projects for integrating/collaboration between Boost libraries. For instance, number of ideas have been discussed about integrating Boost Geometry and Boost Polygon libraries in terms of using types of one with algorithms of the other one, etc. Another interesting proposals could be projects integrating GIL (rasters) with Geometry (vectors). For example, implementation of algorithms for rasterisation of vectors or vectorization of rasters seem to be ideal candidates for extensions. Best regards, -- Mateusz Loskot, http://mateusz.loskot.net Charter Member of OSGeo, http://osgeo.org
Mateusz Loskot wrote:
Andrew Sutton wrote:
== Infrastructure Projects== Projects that aren't part of Boost, but help us improve the quality of Boost might make decent projects, but we've never had one proposed or accepted that I'm aware of. Remember, we can't accept documentation projects so "Write my documents" will not be a good student project (unfortunately ;)
What could that be?
* GotBoost? Website http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?Google_Summer... A Cookbook-like website for Boost sounds as a good idea for this category.
==Applications of Boost== This is a little different... It might be a good idea to have students build real (example?) applications that use the Boost C++ Libraries. There are a number of real benefits to having students work in this space. First, these applications are very obvious clients of Boost. They can provide immediate feedback on issues with the interface, usability, correctness, performance, documentation, etc. Second, they might make really good examples of best practice for using Boost. Third, they probably make nice student projects.
It could also include projects for integrating/collaboration between Boost libraries. For instance, number of ideas have been discussed about integrating Boost Geometry and Boost Polygon libraries in terms of using types of one with algorithms of the other one, etc.
Another interesting proposals could be projects integrating GIL (rasters) with Geometry (vectors). For example, implementation of algorithms for rasterisation of vectors or vectorization of rasters seem to be ideal candidates for extensions.
Another example dug out from previous proposals, I think worth reconsideration, could be * A graphical front-end to Boost.Test http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?Google_Summer... ly_graph Best regards, -- Mateusz Loskot, http://mateusz.loskot.net Charter Member of OSGeo, http://osgeo.org
Within Boost.Geometry, we have discussed participation in the GSoC a bit. However, we've decided to not to propose or mentor any projects due to amount of work we need to get done ASAP to include the library in one of the upcoming Boost releases.
I have mentored one GSoC project myself (though, not for Boost) and I would not be able to commit to mentoring while working on the library preparation at the same time.
However, I personally thing, that if someone else would be interested in mentoring a student working on some project for Boost.Geometry, that would be great.
That's too bad. I was actually thinking that this library is ideal for SoC projects. A good student might be able to work on extensions to your library that don't affect primary submission, but can be integrated after eventual acceptance. I'm not sure that anybody else would be a better mentor. It's your library, so you have have all the knowledge and expertise :)
== Infrastructure Projects==
What could that be?
Compilation farm? Developing regression resting? May be something like integrating Boost regression tests with existing systems like Buildbot, Hudson, etc. This could increase potential of attaching new test environments.
Vladimir Prus has some suggestions on the Boost wiki ( https://svn.boost.org/trac/boost/wiki/SoC2010#Boost.Build).
It could also include projects for integrating/collaboration between Boost libraries. For instance, number of ideas have been discussed about integrating Boost Geometry and Boost Polygon libraries in terms of using types of one with algorithms of the other one, etc.
Another interesting proposals could be projects integrating GIL (rasters) with Geometry (vectors). For example, implementation of algorithms for rasterisation of vectors or vectorization of rasters seem to be ideal candidates for extensions.
I think those are great ideas, but they may be a little broad of scope for student projects. I think those proposals might also tend toward the experimental, and while interesting may not have the publishable payoff that some students are looking for. Still... very good ideas. Andrew Sutton andrew.n.sutton@gmail.com
Andrew Sutton wrote:
Within Boost.Geometry, we have discussed participation in the GSoC a bit. However, we've decided to not to propose or mentor any projects due to amount of work we need to get done ASAP to include the library in one of the upcoming Boost releases.
I have mentored one GSoC project myself (though, not for Boost) and I would not be able to commit to mentoring while working on the library preparation at the same time.
However, I personally thing, that if someone else would be interested in mentoring a student working on some project for Boost.Geometry, that would be great.
That's too bad. I was actually thinking that this library is ideal for SoC projects. A good student might be able to work on extensions to your library that don't affect primary submission, but can be integrated after eventual acceptance.
I'm not sure that anybody else would be a better mentor. It's your library, so you have have all the knowledge and expertise :)
== Infrastructure Projects==
What could that be?
Compilation farm? Developing regression resting? May be something like integrating Boost regression tests with existing systems like Buildbot, Hudson, etc. This could increase potential of attaching new test environments.
Vladimir Prus has some suggestions on the Boost wiki ( https://svn.boost.org/trac/boost/wiki/SoC2010#Boost.Build).
Now that you mention it, reimplementing test results reporting would be an excellent project. - Volodya
Vladimir Prus wrote:
Andrew Sutton wrote:
== Infrastructure Projects==
What could that be?
Compilation farm? Developing regression resting? May be something like integrating Boost regression tests with existing systems like Buildbot, Hudson, etc. This could increase potential of attaching new test environments.
Vladimir Prus has some suggestions on the Boost wiki ( https://svn.boost.org/trac/boost/wiki/SoC2010#Boost.Build).
Now that you mention it, reimplementing test results reporting would be an excellent project.
Once upon a time.. I started with step 0 of that. By having bjam be able to output XML of the build results. With the hope of someone taking that XML and processing it into some test reporting tools. Not necessarily rewriting the existing one, but using some externally available ones. Unfortunately the reporting capabilities of existing tools doesn't approach the utility of results we currently get (even if we get them at a high cost). But some integration of the bjam XML output with other web test report tools as a GSoC would be great! -- -- 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
On 03/09/2010 12:26 PM, Rene Rivera wrote:
Vladimir Prus wrote:
Now that you mention it, reimplementing test results reporting would be an excellent project.
Once upon a time.. I started with step 0 of that. By having bjam be able to output XML of the build results. With the hope of someone taking that XML and processing it into some test reporting tools. Not necessarily rewriting the existing one, but using some externally available ones. Unfortunately the reporting capabilities of existing tools doesn't approach the utility of results we currently get (even if we get them at a high cost).
But some integration of the bjam XML output with other web test report tools as a GSoC would be great!
I still believe it would be better for boost if such logic would be out-sourced into externally developed and maintained code. I once offered to help to use QMTest for all the testing harness, including data collection and reporting. But my point here is not to promote my own tools, but rather to encourage boost developers to focus on what (IMO) matters: the boost libraries, not the harnesses that are used to develop and build them. Stefan -- ...ich hab' noch einen Koffer in Berlin...
Stefan Seefeld wrote:
On 03/09/2010 12:26 PM, Rene Rivera wrote:
Vladimir Prus wrote:
Now that you mention it, reimplementing test results reporting would be an excellent project.
Once upon a time.. I started with step 0 of that. By having bjam be able to output XML of the build results. With the hope of someone taking that XML and processing it into some test reporting tools. Not necessarily rewriting the existing one, but using some externally available ones. Unfortunately the reporting capabilities of existing tools doesn't approach the utility of results we currently get (even if we get them at a high cost).
But some integration of the bjam XML output with other web test report tools as a GSoC would be great!
I still believe it would be better for boost if such logic would be out-sourced into externally developed and maintained code. I once offered to help to use QMTest for all the testing harness, including data collection and reporting. But my point here is not to promote my own tools, but rather to encourage boost developers to focus on what (IMO) matters: the boost libraries, not the harnesses that are used to develop and build them.
Would you please list the tools that produce equally useful result tables? I am sure everybody will jump instantly as soon as such tools are identified. - Volodya
Vladimir Prus wrote:
Stefan Seefeld wrote: Would you please list the tools that produce equally useful result tables? I am sure everybody will jump instantly as soon as such tools are identified.
I can't resist the opportunity to flog my own library_status program and library test scripts in the tools/regression/src directory. I derived these from Beman's original compiler_status source. I use it because it provides what I need in a fairly simple way. That is a) it's built with C++ and boost so I didn't need to learn a whole new thing. b) it easily works with one library at a time on my local system c) produces a much more useful table with different columns for different build scenarios - release, dll, etc. d) works well with bjam It doesn't work with all libraries as it has to make certain assumptions about directory structure which are not true for some libraries. It also has a fair amount of hacked code to try to accomodate these situations. But all in all, I find it exactly what I need - No surprise there as I made it to solve my problems. Robert Ramey
Robert Ramey wrote:
Vladimir Prus wrote:
Stefan Seefeld wrote: Would you please list the tools that produce equally useful result tables? I am sure everybody will jump instantly as soon as such tools are identified.
I can't resist the opportunity to flog my own library_status program and library test scripts in the tools/regression/src directory. I derived these from Beman's original compiler_status source. I use it because it provides what I need in a fairly simple way. That is
a) it's built with C++ and boost so I didn't need to learn a whole new thing. b) it easily works with one library at a time on my local system c) produces a much more useful table with different columns for different build scenarios - release, dll, etc. d) works well with bjam
It doesn't work with all libraries as it has to make certain assumptions about directory structure which are not true for some libraries. It also has a fair amount of hacked code to try to accomodate these situations. But all in all, I find it exactly what I need - No surprise there as I made it to solve my problems.
I am not sure what motifications you have made, but unless you have rewritten everything from scratch I fail to see how this can be a solution even remotely comparable to what we have at present. - Volodya
Vladimir Prus wrote:
Robert Ramey wrote:
Vladimir Prus wrote:
Stefan Seefeld wrote: Would you please list the tools that produce equally useful result tables? I am sure everybody will jump instantly as soon as such tools are identified.
I can't resist the opportunity to flog my own library_status program and library test scripts in the tools/regression/src directory. I derived these from Beman's original compiler_status source. I use it because it provides what I need in a fairly simple way. That is
a) it's built with C++ and boost so I didn't need to learn a whole new thing. b) it easily works with one library at a time on my local system c) produces a much more useful table with different columns for different build scenarios - release, dll, etc. d) works well with bjam
It doesn't work with all libraries as it has to make certain assumptions about directory structure which are not true for some libraries. It also has a fair amount of hacked code to try to accomodate these situations. But all in all, I find it exactly what I need - No surprise there as I made it to solve my problems.
I am not sure what motifications you have made, but unless you have rewritten everything from scratch I fail to see how this can be a solution even remotely comparable to what we have at present.
Hmmm - I'm not sure what you mean by "[not] comparable". The points a-c describe how it's different - and in fact superior - in my view. Robert Ramey
Robert Ramey wrote:
Vladimir Prus wrote:
Vladimir Prus wrote:
Stefan Seefeld wrote: Would you please list the tools that produce equally useful result tables? I am sure everybody will jump instantly as soon as such tools are identified. I can't resist the opportunity to flog my own library_status program and library test scripts in the tools/regression/src directory. I derived these from Beman's original compiler_status source. I use it because it provides what I need in a fairly simple way. That is
a) it's built with C++ and boost so I didn't need to learn a whole new thing. b) it easily works with one library at a time on my local system c) produces a much more useful table with different columns for different build scenarios - release, dll, etc. d) works well with bjam
It doesn't work with all libraries as it has to make certain assumptions about directory structure which are not true for some libraries. It also has a fair amount of hacked code to try to accomodate these situations. But all in all, I find it exactly what I need - No surprise there as I made it to solve my problems. I am not sure what motifications you have made, but unless you have rewritten everything from scratch I fail to see how
Robert Ramey wrote: this can be a solution even remotely comparable to what we have at present.
Hmmm - I'm not sure what you mean by "[not] comparable". The points a-c describe how it's different - and in fact superior - in my view.
The point if that we have reporting system having various features, in particular display of result from multiple libraries, on multiple toolchains, with expected failures, etc. You mention a solution that you use for a single library, which works good for you. However, that solution lacks most of features. Therefore, it cannot be used to replace the current reporting system. And if it cannot replace system, it's probably not important what programming language it uses. - Volodya
Vladimir Prus wrote:
Andrew Sutton wrote:
Mateusz Loskot wrote:
Andrew Sutton wrote: == Infrastructure Projects==
What could that be?
Compilation farm? Developing regression resting? May be something like integrating Boost regression tests with existing systems like Buildbot, Hudson, etc. This could increase potential of attaching new test environments.
Vladimir Prus has some suggestions on the Boost wiki ( https://svn.boost.org/trac/boost/wiki/SoC2010#Boost.Build).
Now that you mention it, reimplementing test results reporting would be an excellent project.
Not really a project for Boost Build, but related to it: An idea of Jamfile generator for CMake has been dangling in my mind :) Best regards, -- Mateusz Loskot, http://mateusz.loskot.net Charter Member of OSGeo, http://osgeo.org
Andrew Sutton wrote:
Within Boost.Geometry, we have discussed participation in the GSoC a bit. However, we've decided to not to propose or mentor any projects due to amount of work we need to get done ASAP to include the library in one of the upcoming Boost releases.
I have mentored one GSoC project myself (though, not for Boost) and I would not be able to commit to mentoring while working on the library preparation at the same time.
However, I personally thing, that if someone else would be interested in mentoring a student working on some project for Boost.Geometry, that would be great.
That's too bad. I was actually thinking that this library is ideal for SoC projects.
Yes, I understand it.
A good student might be able to work on extensions to your library that don't affect primary submission, but can be integrated after eventual acceptance.
The problem is not with affecting the Boost.Geometry submission, but the problem is with amount of work required to make the submission happen and our time. As we've discussed internally in team, we need to focus on the after-review tasks first.
I'm not sure that anybody else would be a better mentor. It's your library, so you have have all the knowledge and expertise :)
I assumed, perhaps a bit naively :-), that there may be some developers out there who are already getting well familiar with Boost.Geometry internals and perhaps would be willing to mentor a student. Certainly, I would do my best to provide some support, but I'm not able to offer myself as "full time" mentor before we release the library.
== Infrastructure Projects==
What could that be?
Compilation farm? Developing regression resting? May be something like integrating Boost regression tests with existing systems like Buildbot, Hudson, etc. This could increase potential of attaching new test environments.
Vladimir Prus has some suggestions on the Boost wiki ( https://svn.boost.org/trac/boost/wiki/SoC2010#Boost.Build).
I'll post comments to it separately.
It could also include projects for integrating/collaboration between Boost libraries. For instance, number of ideas have been discussed about integrating Boost Geometry and Boost Polygon libraries in terms of using types of one with algorithms of the other one, etc.
Another interesting proposals could be projects integrating GIL (rasters) with Geometry (vectors). For example, implementation of algorithms for rasterisation of vectors or vectorization of rasters seem to be ideal candidates for extensions.
I think those are great ideas, but they may be a little broad of scope for student projects.
Yes, but I think I gave a broad overview. A student could work on small part, a specific function. For example, to polygonize Boost.GIL raster by creating Boost.Geometry vector for all connected regions of pixels in the raster sharing a common value, It should be feasible in the given time frame.
I think those proposals might also tend toward the experimental, and while interesting may not have the publishable payoff that some students are looking for. Still... very good ideas.
Good point. Best regards, -- Mateusz Loskot, http://mateusz.loskot.net Charter Member of OSGeo, http://osgeo.org
The problem is not with affecting the Boost.Geometry submission, but the problem is with amount of work required to make the submission happen and our time. As we've discussed internally in team, we need to focus on the after-review tasks first.
We'll keep you on the list for next year then :) Yes, but I think I gave a broad overview.
A student could work on small part, a specific function. For example, to polygonize Boost.GIL raster by creating Boost.Geometry vector for all connected regions of pixels in the raster sharing a common value, It should be feasible in the given time frame.
Yes, I can see how there are a number of interesting in that domain. Both rasterizing and vectorizing. Andrew Sutton andrew.n.sutton@gmail.com
Andrew Sutton wrote:
I'm officially soliciting ideas for student projects for this year's 2010 Summer of Code. ... ==Extensions for Existing Libraries== There are a number of Boost libraries that are very amenable to extension (e.g., BGL, GIL, Math, etc.). Basically any library that doesn't have a finite feature space. Non-intrusive changes (i.e., those that don't require hacking on the existing bits) typically make good summer of code projects. ... If you have any ideas, let's hear them. And remember, funded projects need mentors.
2D medial axis, veronoi diagrams and delaunay triangulation are three classical problems in computational geometry. Veronoi diagrams are well known to be the dual graph of delaunay triangulation, so if you solve one you have solved the other. Medial axis is also related to the other two because it can also be solved with sweepline. All three could be solved by a single generic-parameterized implementation of a sweepline algorithm. These problems are difficult to solve primarily due to numerical robustness challenges. If we limit the scope of the problem to inputs with integer coordinates only the numerical robustness challenge is much reduced. I'd be willing to mentor a student to work on solving these classical computational geometry problems as an extension to the features provided by my Boost.Polygon library. This would be a natural extension on the existing functionality provided by Boost.Polygon (it came up during review to ask if I planned on implementing them.) Since my library already provides algorithms that require integer coordinates it is acceptable to me to have extensions with that limitation. I don't believe it is reasonable to expect a student to solve the floating point versions of these problems (with an efficient implementation) in a single summer, but for integer coordinates a strong student could succeed with some expert guidance. If the project produces something of value I would be willing to take on responsibility for maintaining it if the student loses interest. Regards, Luke
Luke, I think that sounds like a great project, and we'd be happy to have you as a mentor. Would you be willing to post on the projects page here: https://svn.boost.org/trac/boost/wiki/SoC2010 2D medial axis, veronoi diagrams and delaunay triangulation are three
classical problems in computational geometry. Veronoi diagrams are well known to be the dual graph of delaunay triangulation, so if you solve one you have solved the other. Medial axis is also related to the other two because it can also be solved with sweepline. All three could be solved by a single generic-parameterized implementation of a sweepline algorithm. These problems are difficult to solve primarily due to numerical robustness challenges. If we limit the scope of the problem to inputs with integer coordinates only the numerical robustness challenge is much reduced. I'd be willing to mentor a student to work on solving these classical computational geometry problems as an extension to the features provided by my Boost.Polygon library. This would be a natural extension on the existing functionality provided by Boost.Polygon (it came up during review to ask if I planned on implementing them.) Since my library already provides algorithms that require integer coordinates it is acceptable to me to have extensions with that limitation. I don't believe it is reasonable to expect a student to solve the floating point versions of these problems (with an efficient implementation) in a single summer, but for integer coordinates a strong student could succeed with some expert guidance.
Andrew Sutton andrew.n.sutton@gmail.com
Simonson, Lucanus J wrote:
Andrew Sutton wrote:
I'm officially soliciting ideas for student projects for this year's 2010 Summer of Code. ... ==Extensions for Existing Libraries== There are a number of Boost libraries that are very amenable to extension (e.g., BGL, GIL, Math, etc.). Basically any library that doesn't have a finite feature space. Non-intrusive changes (i.e., those that don't require hacking on the existing bits) typically make good summer of code projects. ... If you have any ideas, let's hear them. And remember, funded projects need mentors.
2D medial axis, veronoi diagrams and delaunay triangulation are three classical problems in computational geometry.
Luke, these are indeed very good ideas for SoC projects I think.
Veronoi diagrams are well known to be the dual graph of delaunay triangulation, so if you solve one you have solved the other. Medial axis is also related to the other two because it can also be solved with sweepline. All three could be solved by a single generic-parameterized implementation of a sweepline algorithm. These problems are difficult to solve primarily due to numerical robustness challenges. If we limit the scope of the problem to inputs with integer coordinates only the numerical robustness challenge is much reduced.
Would it make sense for you to consider designing parametrized interface of these algorithms, that later could be shared with potential implementation provided by Boost Geometry ? Best regards, -- Mateusz Loskot, http://mateusz.loskot.net Charter Member of OSGeo, http://osgeo.org
Mateusz Loskot wrote:
Simonson, Lucanus J wrote:
Andrew Sutton wrote:
I'm officially soliciting ideas for student projects for this year's 2010 Summer of Code. ... ==Extensions for Existing Libraries== There are a number of Boost libraries that are very amenable to extension (e.g., BGL, GIL, Math, etc.). Basically any library that doesn't have a finite feature space. Non-intrusive changes (i.e., those that don't require hacking on the existing bits) typically make good summer of code projects. ... If you have any ideas, let's hear them. And remember, funded projects need mentors.
2D medial axis, veronoi diagrams and delaunay triangulation are three classical problems in computational geometry.
Luke, these are indeed very good ideas for SoC projects I think.
Veronoi diagrams are well known to be the dual graph of delaunay triangulation, so if you solve one you have solved the other. Medial axis is also related to the other two because it can also be solved with sweepline. All three could be solved by a single generic-parameterized implementation of a sweepline algorithm. These problems are difficult to solve primarily due to numerical robustness challenges. If we limit the scope of the problem to inputs with integer coordinates only the numerical robustness challenge is much reduced.
Would it make sense for you to consider designing parametrized interface of these algorithms, that later could be shared with potential implementation provided by Boost Geometry ?
Are you proposing using the algorithms in Boost.Polygon with interfaces in Boost Geometry, or allowing similar algorithms implemented in Boost Geometry to be used with Boost.Polygon interfaces? Both are the sort of thing I would like to support. I don't provide a "strategy" argument for calling algorithms. I select the algorithm to invoke for a given function call based on the conceptual type of the geometry passed into the function. For cases where this doesn't uniquely identify an algorithm I use different function names to call different algorithms. I expect that if a medial axis implementation were available in Boost.Geometry it would implement a floating point based algorithm for floating point coordinates. I could add in the ability to select that algorithm based on the coordinate traits of the coordinate type used in the geometry argument. I would have to add a "float_like" trait to the coordinate traits that selects the Boost.Geometry algorithm if present and results in SFINAE if absent. That is all easy enough. The trouble I would run into is if Boost.Geometry doesn't provide polygon concept interfaces that support the full range of polygon data types supported by the Boost.Polygon concept interfaces. That would make integrating a Boost.Geometry algorithm into the Boost.Polygon interface awkward. Specifically I would prefer not to require STL container semantics for the data stored in a geometry object. The practical implication of such a requirement is only data structure that provide public access to data members that are stl containers can model the geometry concept. The only reasonable way to interoperate with such an interface is data copy conversion. If your project is considering changing the concept interfaces I'd be interested in reviewing those design decisions so that I can provide feedback on the implications for interoperability with Boost.Polygon. Regards, Luke
Simonson, Lucanus J wrote:
Mateusz Loskot wrote:
Simonson, Lucanus J wrote:
Andrew Sutton wrote:
I'm officially soliciting ideas for student projects for this year's 2010 Summer of Code. ... ==Extensions for Existing Libraries== There are a number of Boost libraries that are very amenable to extension (e.g., BGL, GIL, Math, etc.). Basically any library that doesn't have a finite feature space. Non-intrusive changes (i.e., those that don't require hacking on the existing bits) typically make good summer of code projects. ... If you have any ideas, let's hear them. And remember, funded projects need mentors.
2D medial axis, veronoi diagrams and delaunay triangulation are three classical problems in computational geometry.
Luke, these are indeed very good ideas for SoC projects I think.
Veronoi diagrams are well known to be the dual graph of delaunay triangulation, so if you solve one you have solved the other. Medial axis is also related to the other two because it can also be solved with sweepline. All three could be solved by a single generic-parameterized implementation of a sweepline algorithm. These problems are difficult to solve primarily due to numerical robustness challenges. If we limit the scope of the problem to inputs with integer coordinates only the numerical robustness challenge is much reduced.
Would it make sense for you to consider designing parametrized interface of these algorithms, that later could be shared with potential implementation provided by Boost Geometry ?
Are you proposing using the algorithms in Boost.Polygon with interfaces in Boost Geometry, or allowing similar algorithms implemented in Boost Geometry to be used with Boost.Polygon interfaces?
Initially, I was thinking about the latter option. However, I think that for BG (Boost.Geometry) geometry types instantiated with integer, it would make sense to call implementations from BP (Boost.Polygon). At least, shortly after GSoC delivers those algorithms for BP, with parametrized interfaces, then perhaps they would be applicable to integer-based geometries from BG straight away.
Both are the sort of thing I would like to support.
Sounds as an ideal target.
I don't provide a "strategy" argument for calling algorithms. I select the algorithm to invoke for a given function call based on the conceptual type of the geometry passed into the function. For cases where this doesn't uniquely identify an algorithm I use different function names to call different algorithms.
I see.
I expect that if a medial axis implementation were available in Boost.Geometry it would implement a floating point based algorithm for floating point coordinates.
Yes, that's probably the option to go if implemented in BG. Though, speaking of SoC, it may be a problem for student to switch between the two libraries, BP and BG. Are you thinking of MA implementation for discrete space in Boost Polygon or you mean pushing this functionality to BG completely? (I don't have in-depth knowledge about possible/best algorithmic solutions for MA myself)
I could add in the ability to select that algorithm based on the coordinate traits of the coordinate type used in the geometry argument. I would have to add a "float_like" trait to the coordinate traits that selects the Boost.Geometry algorithm if present and r esults in SFINAE if absent. That is all easy enough.
Sound good. In case that BG applies algorithms from BP to integer-based geometries, it would be nice to be able to pass BP algorithm as strategy.
The trouble I would run into is if Boost.Geometry doesn't provide polygon concept interfaces that support the full range of polygon data types supported by the Boost.Polygon concept interfaces.
Does it mean that, basically, BG is missing the concept of isotropy and associated properties? Perhaps you've already explained this issue in details on the list, so I can just scan the archives, haven't you?
That would make integrating a Boost.Geometry algorithm into the Boost.Polygon interface awkward.
Sound like the other way around should be easier to achieve, right? Perhaps that would be a good direction to go for GSoC project.
Specifically I would prefer not to require STL container semantics for the data stored in a geometry object.
It's availability or adaptability to this semantic is one of the fundamental of types in BG. It seems the significant difference lies down here.
The practical implication of such a requirement is only data structure that provide public access to data members that are stl containers can model the geometry concept. The only reasonable way to interoperate with such an interface is data copy conversion.
I'm not sure that's correct. OK, at the deep end BG does require geometry to look & feel like standard containers, but it does not require geometry to be actual standard container. Wouldn't it be possible to address this issues with adapters?
If your project is considering changing the concept interfaces I'd be interested in reviewing those design decisions so that I can provide feedback on the implications for interoperability with Boost.Polygon.
I can't speak for the rest of the team. We would need to discuss it. Could you list conflicts you've observed so far and give overview of required changes? It Perhaps it would be easier to analyse it. I have to admit, I have not yet evaluated Boost Polygon regarding such adaption, so I may be missing some significant details still. I hope I'll catch up during further discussions. Best regards, -- Mateusz Loskot, http://mateusz.loskot.net Charter Member of OSGeo, http://osgeo.org
Mateusz Loskot wrote:
Simonson, Lucanus J wrote:
I expect that if a medial axis implementation were available in Boost.Geometry it would implement a floating point based algorithm for floating point coordinates.
Yes, that's probably the option to go if implemented in BG. Though, speaking of SoC, it may be a problem for student to switch between the two libraries, BP and BG.
Are you thinking of MA implementation for discrete space in Boost Polygon or you mean pushing this functionality to BG completely?
(I don't have in-depth knowledge about possible/best algorithmic solutions for MA myself)
I was thinking of MA implementation for discrete space in Boost.Polygon with the potential that a floating point MA algorithm might be added to BG at some future point and we would want them to interoperate reasonably well. In other words either library's interface ought to be able to provide access to both algorithms, and conversely, both algorithms should be easily integratable into either interface.
The trouble I would run into is if Boost.Geometry doesn't provide polygon concept interfaces that support the full range of polygon data types supported by the Boost.Polygon concept interfaces.
Does it mean that, basically, BG is missing the concept of isotropy and associated properties? Perhaps you've already explained this issue in details on the list, so I can just scan the archives, haven't you?
No, isotropy is not a factor in compatibility since the adaptor is trivial. I've explained these issues in the past, but the volume of communication from me in the archives may overwhelm your search. You can focus on my feedback during the review of Boost.Geometry, but I provided similar feedback in each preview of the library.
That would make integrating a Boost.Geometry algorithm into the Boost.Polygon interface awkward.
Sound like the other way around should be easier to achieve, right? Perhaps that would be a good direction to go for GSoC project.
Yes, the other way around would be easier to achieve. Are you proposing a GSoC project to provide adaptors for Boost.Polygon algorithms to Boost.Geometry geometry concepts? It sounds interesting and more a student's speed. I think, however, that this effort might require some interaction between the authors of the two libraries and it is better for us to interact directly and do the work ourselves rather than put a third party in the middle because there may be some changes to the libraries themselves. Ideally we should work together on this sort of thing before we release the interfaces in an official boost release and make breaking changes to the interfaces harder to introduce.
Specifically I would prefer not to require STL container semantics for the data stored in a geometry object.
It's availability or adaptability to this semantic is one of the fundamental of types in BG. It seems the significant difference lies down here.
The practical implication of such a requirement is only data structure that provide public access to data members that are stl containers can model the geometry concept. The only reasonable way to interoperate with such an interface is data copy conversion.
I'm not sure that's correct. OK, at the deep end BG does require geometry to look & feel like standard containers, but it does not require geometry to be actual standard container.
Wouldn't it be possible to address this issues with adapters?
It may be possible, but I very carefully chose the word practical in my statement above. It is more than just syntactical differences related to member function names of stl containers, but semantical differences that are troublesome. Non-const reference to data stored in a geometry object is something I avoided in the design of my concepts. Consider a polygon that stores its geometry data in a compressed format that provides lazy iterator decompression and accepts an iterator pair for compression. How do I provide non-const references to objects that model point concept to satisfy the interface of polygon concept for this kind of data structure? Other examples are presumptions of polygon winding direction known at compile time based on object type and last vertex of polygon duplicates first vertex.
If your project is considering changing the concept interfaces I'd be interested in reviewing those design decisions so that I can provide feedback on the implications for interoperability with Boost.Polygon.
I can't speak for the rest of the team. We would need to discuss it. Could you list conflicts you've observed so far and give overview of required changes? It Perhaps it would be easier to analyse it.
I have to admit, I have not yet evaluated Boost Polygon regarding such adaption, so I may be missing some significant details still. I hope I'll catch up during further discussions.
Problems I'm aware of that in adapting Boost.Polygon interfaces to Boost.Geometry algorithms: Non-const references to data members for interior_type. Stl container syntax for data access for interior_type. Assumed winding direction of polygon and holes known at compile time. Assumed "closed" polygon with redundant last vertex. Exterior ring and hole rings assumed to be same type. What I would like to see: Value semantics for access to data stored in geometry objects with direct access implemented as an optimization for data types that provide it. No assumptions about member functions (even if stl standard) for accessing data, and adaptor traits instead, or at least the option for adaptors instead. A trait for getting the winding direction at run time. Handle both "open" and "closed" polygons of the same type. Provide hole_ring_type that defaults to ring type but can be overridden. My wish list touches on many of the traits of the Polygon concept and implicit assumptions (documented of course) about data types that model it, which would require changes to algorithms and not just interfaces. I think my proposed changes are each an improvement to the design of the Boost.Geometry concepts interface because they make it more generic. To the greater extent my suggestions can be implemented in a way that doesn't break existing usage of the Boost.Geometry library. I hope that you do consider them. Thanks, Luke
Simonson, Lucanus J wrote:
Mateusz Loskot wrote:
I expect that if a medial axis implementation were available in Boost.Geometry it would implement a floating point based algorithm for floating point coordinates. Yes, that's probably the option to go if implemented in BG. Though, speaking of SoC, it may be a problem for student to switch between
Simonson, Lucanus J wrote: the two libraries, BP and BG.
Are you thinking of MA implementation for discrete space in Boost Polygon or you mean pushing this functionality to BG completely?
(I don't have in-depth knowledge about possible/best algorithmic solutions for MA myself)
I was thinking of MA implementation for discrete space in Boost.Polygon with the potential that a floating point MA algorithm might be added to BG at some future point and we would want them to interoperate reasonably well. In other words either library's interface ought to be able to provide access to both algorithms, and conversely, both algorithms should be easily integratable into either interface.
OK, to me personally, sounds good.
The trouble I would run into is if Boost.Geometry doesn't provide polygon concept interfaces that support the full range of polygon data types supported by the Boost.Polygon concept interfaces. Does it mean that, basically, BG is missing the concept of isotropy and associated properties? Perhaps you've already explained this issue in details on the list, so I can just scan the archives, haven't you?
No, isotropy is not a factor in compatibility since the adaptor is trivial. I've explained these issues in the past, but the volume of communication from me in the archives may overwhelm your search. You can focus on my feedback during the review of Boost.Geometry, but I provided similar feedback in each preview of the library.
Thanks for pointing relevant parts. I'll read it back to catch up.
That would make integrating a Boost.Geometry algorithm into the Boost.Polygon interface awkward. Sound like the other way around should be easier to achieve, right? Perhaps that would be a good direction to go for GSoC project.
Yes, the other way around would be easier to achieve. Are you proposing a GSoC project to provide adaptors for Boost.Polygon algorithms to Boost.Geometry geometry concepts?
I'd rather say, I'm brainstorming it or proposing but not specifically for GSoC, because I can't get involved myself in the GSoC time frame. I'm more thinking along this: During reviews folks were discussing and suggesting it, so as this subject emerged from GSoC discussions, perhaps it's a good idea to discuss further details. And, perhaps there would be a student interested in and capable to take it up proposing implementation.
It sounds interesting and more a student's speed.
That's what I thought too.
I think, however, that this effort might require some interaction between the authors of the two libraries and it is better for us to interact directly and do the work ourselves rather than put a third party in the middle because there may be some changes to the libraries themselves. Ideally we should work together on this sort of thing before we release the interfaces in an official boost release and make breaking changes to the interfaces harder to introduce.
This is a very good point. In case we start working on that, that's seems as best appraoch. However, as things are moving off the GSoC a bit and toward Boost.Polygon and Boost.Geometry collaboration, I owe you explanation. I personally think it's good and that's what Boost Community suggested. Although, as perhaps you've noticed, I suggested Boost.Geometry related projects for GSoC not as official proposal from BG team, but as my own ideas. In Boost.Geometry team, we're focused on after-review tasks now. I don't want to make any official statements and or promise you any changes in Boost.Geometry on my own, without agreement from Boost.Geometry team.
Specifically I would prefer not to require STL container semantics for the data stored in a geometry object.
It's availability or adaptability to this semantic is one of the fundamental of types in BG. It seems the significant difference lies down here.
The practical implication of such a requirement is only data structure that provide public access to data members that are stl containers can model the geometry concept. The only reasonable way to interoperate with such an interface is data copy conversion. I'm not sure that's correct. OK, at the deep end BG does require geometry to look & feel like standard containers, but it does not require geometry to be actual standard container.
Wouldn't it be possible to address this issues with adapters?
It may be possible, but I very carefully chose the word practical in my statement above. It is more than just syntactical differences related to member function names of stl containers, but semantical differences that are troublesome. Non-const reference to data stored in a geometry object is something I avoided in the design of my concepts.
OK, it summarizes nature of the issue very well.
Consider a polygon that stores its geometry data in a compressed format that provides lazy iterator decompression and accepts an iterator pair for compression. How do I provide non-const references to objects that model point concept to satisfy the interface of polygon concept for this kind of data structure?
It's a good catch and a practical use case indeed. Actually, I've been considering very same use case: processing point clouds in compressed form. That would be indeed an obstacle in such situations. I'd like to see this issue addressed in Boost.Geometry myself.
Other examples are presumptions of polygon winding direction known at compile time based on object type and last vertex of polygon duplicates first vertex.
I assume, you mean in Boost.Geometry. I'm not sure how this could be fixed really.
If your project is considering changing the concept interfaces I'd be interested in reviewing those design decisions so that I can provide feedback on the implications for interoperability with Boost.Polygon. I can't speak for the rest of the team. We would need to discuss it. Could you list conflicts you've observed so far and give overview of required changes? It Perhaps it would be easier to analyse it.
I have to admit, I have not yet evaluated Boost Polygon regarding such adaption, so I may be missing some significant details still. I hope I'll catch up during further discussions.
Problems I'm aware of that in adapting Boost.Polygon interfaces to Boost.Geometry algorithms:
Non-const references to data members for interior_type. Stl container syntax for data access for interior_type. Assumed winding direction of polygon and holes known at compile time.
I'll forward this and the following points to the BG mailing list.
Assumed "closed" polygon with redundant last vertex. Exterior ring and hole rings assumed to be same type.
I suppose this "padlock" is a kind of inheritance from geospatial domains. We have got used to it pretty well in GIS :-)
What I would like to see:
Value semantics for access to data stored in geometry objects with direct access implemented as an optimization for data types that provide it.
Yes, as I mentioned I support this idea.
No assumptions about member functions (even if stl standard) for accessing data, and adaptor traits instead, or at least the option for adaptors instead.
I'm not sure I get this point well. I don't see it solved that way in Boost.Polygon.
A trait for getting the winding direction at run time. Handle both "open" and "closed" polygons of the same type. Provide hole_ring_type that defaults to ring type but can be overridden.
Ouch! :-) Open polygon is quite well against the fundamental concepts in Boost.Geometry. It may be a limitation, but there is variety of types in BG, so users can support their problems well. However, I understand that this stays in contradiction with principles of Boost.Polygon. Considering Boost.Polygon as a user of Boost.Geometry, then it's clear that boost::geometry::polygon does not meet the user's (BP's) requirements, thus boost::geometry::linestring should be used.,
My wish list touches on many of the traits of the Polygon concept and implicit assumptions (documented of course) about data types that model it, which would require changes to algorithms and not just interfaces.
Yes, I'm getting now much better picture of the differences between the two library.
I think my proposed changes are each an improvement to the design of the Boost.Geometry concepts interface because they make it more generic.
I see they are differences. However, I don't see these differences in terms of bad and good choices. I understand well that specifying the requirement of closed polygon is a bad choice in terms of concepts of Boost.Polygon. Though, one may argue that open polygon is a bad choice. To me, it's not black and white, thus I don't agree with the statement that "are each improvement".
To the greater extent my suggestions can be implemented in a way that doesn't break existing usage of the Boost.Geometry library.
I'm sure it's feasible, programmatically. What disturbs me, however, changing principle semantics of current design by dropping the winding requirement and closed vs open polygon are
I hope that you do consider them.
Personally, I am considering it. I can't give any promises on behalf of the whole Boost.Geometry project team. I'm keen to discuss it with Barend and Bruno, so I will forward our discussion to BG list. Luke, thank you for your all the clarifications you've provided. Best regards, -- Mateusz Loskot, http://mateusz.loskot.net Charter Member of OSGeo, http://osgeo.org
Mateusz Loskot wrote:
I see they are differences. However, I don't see these differences in terms of bad and good choices. I understand well that specifying the requirement of closed polygon is a bad choice in terms of concepts of Boost.Polygon. Though, one may argue that open polygon is a bad choice.
Open polygon is an equally bad choice. Since there are different data types in Boost.Geometry for linestring and ring there is no need for the "closed" vertex to signify that a data structure is a polygon and not a linestring. When I say support polygons that are either open or closed I don't mean allow the user to choose one or the other, I mean literally both and that algorithms can accept either and are invariant to whether the last vertex is duplicate of the first or not.
I'm sure it's feasible, programmatically. What disturbs me, however, changing principle semantics of current design by dropping the winding requirement and closed vs open polygon are
Barend has already been working on allowing the user to specify the winding direction at compile time. What I'm asking is to make it a runtime trait of the object and not a complie time trait of the class. That way types that know their winding at compile time can return a constant and types that don't can return a cached winding direction (if they keep it as a data member) or compute it on the fly. This is really no more work in the implementation than supporting compile time winding trait. The open vs. closed issue is similar, and the primary implication of these changes is that you have to test your algorithms for these cases, since the changes in their implementation will typically be small. I want to stress that weakening these semantic requirements for what object types can be a model of ring and polygon is not a breaking change in the interface of the related concepts. All data types and code using Boost.Geometry would still work after the change. What the change does is allow additional data types to be used with Boost.Geometry that cannot be used today. I want you to interpret my suggestions as constructive feedback on ways I think you can make your library interfaces more generic. There are good reasons why we don't require polygon winding to be known at compile time and don't require a redundant last vertex in CAD applications. It is wonderful that GIS applications can make such simplifying assumptions, but unreasonable to expect that everyone else can, particularly since the library is named Boost.Geometry and not Boost.GIS. I know that a graphics application might be really not pleased with storing four points for every triangle. Thanks, Luke
Hi Luke, Mateusz,
Barend has already been working on allowing the user to specify the winding direction at compile time.
That is right.
What I'm asking is to make it a runtime trait of the object and not a complie time trait of the class. That is also foreseen (but not implemented) in the same mechanism:
enum order_selector { clockwise, counterclockwise, order_undetermined }; where undetermined means that it is runtime.
The open vs. closed issue is similar, and the primary implication of these changes is that you have to test your algorithms for these cases, since the changes in their implementation will typically be small.
This must (and will) also be implemented, as it is part of the review report: "Boolean operations: while the library provides a set of Boolean operations those seem to be not complete and/or robust in terms of clockwise/counterclockwise geometries, closed/open polygons. Robust Boolean operations are a strong requirement, so this should be fixed as reported by at least one reviewer." Regards, Barend
Simonson, Lucanus J wrote:
Mateusz Loskot wrote:
I see they are differences. However, I don't see these differences in terms of bad and good choices. I understand well that specifying the requirement of closed polygon is a bad choice in terms of concepts of Boost.Polygon. Though, one may argue that open polygon is a bad choice.
Open polygon is an equally bad choice. Since there are different data types in Boost.Geometry for linestring and ring there is no need for the "closed" vertex to signify that a data structure is a polygon and not a linestring.
Right, it is a redundancy.
When I say support polygons that are either open or closed I don't mean allow the user to choose one or the other, I mean literally both and that algorithms can accept either and are invariant to whether the last vertex is duplicate of the first or not.
Yes, I see your point.
I'm sure it's feasible, programmatically. What disturbs me, however, changing principle semantics of current design by dropping the winding requirement and closed vs open polygon are
Barend has already been working on allowing the user to specify the winding direction at compile time. What I'm asking is to make it a runtime trait of the object and not a complie time trait of the class.
I misunderstood you mean compile-time only.
That way types that know their winding at compile time can return a constant and types that don't can return a cached winding direction (if they keep it as a data member) or compute it on the fly. This is really no more work in the implementation than supporting compile time winding trait.
Yes, point taken.
I want to stress that weakening these semantic requirements for what object types can be a model of ring and polygon is not a breaking change in the interface of the related concepts. All data types and code using Boost.Geometry would still work after the change. What the change does is allow additional data types to be used with Boost.Geometry that cannot be used today.
Good point. I am reviewing my own considerations regarding this. Perhaps it will be discussed within Boost.Geometry. I have forwarded [1] this thread to the Boost.Geometry mailing list [1] http://lists.osgeo.org/pipermail/ggl/2010-March/000675.html
I want you to interpret my suggestions as constructive feedback on ways I think you can make your library interfaces more generic.
I can assure you that I do not interpret your feedback in any other way. Even if I can't guarantee myself that any changes will happen, I'm interested in discussing it. I really appreciate you're willing to share your comments and explain cruxes of the matter to me.
There are good reasons why we don't require polygon winding to be known at compile time and don't require a redundant last vertex in CAD applications. It is wonderful that GIS applications can make such simplifying assumptions, but unreasonable to expect that everyone else can, particularly since the library is named Boost.Geometry and not Boost.GIS. I know that a graphics application might be really not pleased with storing four points for every triangle.
Of course, you are right. I don't mean I appreciated these simplifications myself. It's more that I've learned to live with them, what in turn might be narrowing my perception a bit. Best regards, -- Mateusz Loskot, http://mateusz.loskot.net Charter Member of OSGeo, http://osgeo.org
2D medial axis, veronoi diagrams and delaunay triangulation are three classical problems in computational geometry. Veronoi diagrams are well known to be the dual graph of delaunay triangulation, so if you solve one you have solved the other. Medial axis is also related to the other two because it can also be solved with sweepline. All three could be solved by a single generic-parameterized implementation of a sweepline algorithm.
I posted this much as a project idea on the wiki. I hope that a good proposal would address the issues regarding floating point problems. Plus, I would think that somebody would find your on the problem comments and integrate them into their proposal. Andrew Sutton andrew.n.sutton@gmail.com
Andrew Sutton wrote:
2D medial axis, veronoi diagrams and delaunay triangulation are three classical problems in computational geometry. Veronoi diagrams are well known to be the dual graph of delaunay triangulation, so if you solve one you have solved the other. Medial axis is also related to the other two because it can also be solved with sweepline. All three could be solved by a single generic-parameterized implementation of a sweepline algorithm.
I posted this much as a project idea on the wiki. I hope that a good proposal would address the issues regarding floating point problems. Plus, I would think that somebody would find your on the problem comments and integrate them into their proposal.
I think that paragraph on its own is good enough to communicate the problem statement. I know if I were a student I'd just at that. I really want to underscore the difficulty in implementing (for exmaple) medial axis that is robust to floating point numerical issues. Fernando's contribution to the CGAL project was exactly that and I think he can attest to the fact that it is not a summer project. If we think back to Triangle and Shewchuk's use of Priest's expansions to implement Delaunay triangulation it was more than a summer project and there are very few students like Shewchuck out there. Even my proposal for robust integer coordinate algorithms is an extremely challenging project that would require a solid three months of effort from a student who is a very strong programmer with quite a bit of coaching from me and code reuse from Boost.Polygon. It is likely that students would propose to implement a floating point implementation that is not robust and allow the user to parameterize the coordinate type to allow infinite precision floating point coordinates to be used to achieve robustness. That would be a good student project, but not what I would like to see in boost, and I think Fernando would agree. It does not constitute a solution to numerical robustness to rely heavily on infinite precision floating point because the runtime implications are easy two orders of magnitude. This is a conversation I'll have to have with any students who submit proposals for implementing these algorithms. There is a danger that the student will not be able to gauge difficulty or time required to implement their proposal and we would need to negotiate and compromise on a set of objectives and schedule for the project that is realistic but also worthwhile. Regards, Luke
Simonson, Lucanus J wrote:
Andrew Sutton wrote:
2D medial axis, veronoi diagrams and delaunay triangulation are three classical problems in computational geometry. Veronoi diagrams are well known to be the dual graph of delaunay triangulation, so if you solve one you have solved the other. Medial axis is also related to the other two because it can also be solved with sweepline. All three could be solved by a single generic-parameterized implementation of a sweepline algorithm.
I posted this much as a project idea on the wiki. I hope that a good proposal would address the issues regarding floating point problems. Plus, I would think that somebody would find your on the problem comments and integrate them into their proposal.
I think that paragraph on its own is good enough to communicate the problem statement. I know if I were a student I'd just at that.
I really want to underscore the difficulty in implementing (for exmaple) medial axis that is robust to floating point numerical issues. Fernando's contribution to the CGAL project was exactly that and I think he can attest to the fact that it is not a summer project. If we think back to Triangle and Shewchuk's use of Priest's expansions to implement Delaunay triangulation it was more than a summer project and there are very few students like Shewchuck out there.
I have pleasure to get familiar to some extent with Jonathan Shewchuck's work together with Martin Isenburg for LiDAR data processing and such, and it is a solid piece of complex matter indeed.
Even my proposal for robust integer coordinate algorithms is an extremely challenging project that would require a solid three months of effort from a student who is a very strong programmer with quite a bit of coaching from me and code reuse from Boost.Polygon. It is likely that students would propose to implement a floating point implementation that is not robust and allow the user to parameterize the coordinate type to allow infinite precision floating point coordinates to be used to achieve robustness. That w ould be a good student project, but not what I would like to see in boost, and I think Fernando would agree. It does not constitute a solution to numerical robustness to rely heavily on infinite precision floating point because the runtime implications are easy two orders of magnitude.
This is a conversation I'll have to have with any students who submit proposals for implementing these algorithms. There is a danger that the student will not be able to gauge difficulty or time required to implement their proposal and we would need to negotiate and compromise on a set of objectives and schedule for the project that is realistic but also worthwhile.
I think this kind of clear specification of requirements from a project and mentor is in fact what candidates would eventually appreciate. Best regards, -- Mateusz Loskot, http://mateusz.loskot.net Charter Member of OSGeo, http://osgeo.org
Mateusz Loskot wrote:
Simonson, Lucanus J wrote: [...]
I really want to underscore the difficulty in implementing (for exmaple) medial axis that is robust to floating point numerical issues. Fernando's contribution to the CGAL project was exactly that and I think he can attest to the fact that it is not a summer project. If we think back to Triangle and Shewchuk's use of Priest's expansions to implement Delaunay triangulation it was more than a summer project and there are very few students like Shewchuck out there.
I have pleasure to get familiar to some extent with Jonathan Shewchuck's work together with Martin Isenburg for LiDAR data processing and such, and it is a solid piece of complex matter indeed. [...]
FWIW, I have working implementations of Schewchuk's expansion arithmetic algorithms (in free functions and classes utilizing these free functions), both for fixed-sized expansions (with error estimates) and arbitrary-sized expansions, if you (or anyone) is interested. It's not self-contained (depends on some other components of our code base), but could be a good starting point if you're looking in that direction. We currently use it in an adaptive context to "robustify" our geometric predicates. Of course, it isn't 100% robust, as overflow and underflow could happen, but so far it has not failed. It's also not going to be as efficient as the "tricks" Shewchuk uses in his triangulation (I'm guessing), but it still gets you somewhere. - Jeff
Jeffrey Hellrung wrote:
Mateusz Loskot wrote:
Simonson, Lucanus J wrote: [...]
I really want to underscore the difficulty in implementing (for exmaple) medial axis that is robust to floating point numerical issues. Fernando's contribution to the CGAL project was exactly that and I think he can attest to the fact that it is not a summer project. If we think back to Triangle and Shewchuk's use of Priest's expansions to implement Delaunay triangulation it was more than a summer project and there are very few students like Shewchuck out there.
I have pleasure to get familiar to some extent with Jonathan Shewchuck's work together with Martin Isenburg for LiDAR data processing and such, and it is a solid piece of complex matter indeed. [...]
FWIW, I have working implementations of Schewchuk's expansion arithmetic algorithms (in free functions and classes utilizing these free functions), both for fixed-sized expansions (with error estimates) and arbitrary-sized expansions, if you (or anyone) is interested. It's not self-contained (depends on some other components of our code base), but could be a good starting point if you're looking in that direction. We currently use it in an adaptive context to "robustify" our geometric predicates. Of course, it isn't 100% robust, as overflow and underflow could happen, but so far it has not failed. It's also not going to be as efficient as the "tricks" Shewchuk uses in his triangulation (I'm guessing), but it still gets you somewhere.
Jeffrey, I'd be interested in taking look at it myself. Perhaps you could push it to the Sandbox? Best regards, -- Mateusz Loskot, http://mateusz.loskot.net Charter Member of OSGeo, http://osgeo.org
Mateusz Loskot wrote:
Jeffrey Hellrung wrote: [...]
FWIW, I have working implementations of Schewchuk's expansion arithmetic algorithms (in free functions and classes utilizing these free functions), both for fixed-sized expansions (with error estimates) and arbitrary-sized expansions, if you (or anyone) is interested. It's not self-contained (depends on some other components of our code base), but could be a good starting point if you're looking in that direction. We currently use it in an adaptive context to "robustify" our geometric predicates. Of course, it isn't 100% robust, as overflow and underflow could happen, but so far it has not failed. It's also not going to be as efficient as the "tricks" Shewchuk uses in his triangulation (I'm guessing), but it still gets you somewhere.
Jeffrey, I'd be interested in taking look at it myself. Perhaps you could push it to the Sandbox?
I don't have a boost svn-sandbox account, but seeing as how the code is not (currently) self-contained and depends on a larger code base, I don't think it belongs in the sandbox. I have zipped up just the expansion arithmetic code and uploaded it to www.math.ucla.edu/~jhellrun/sake-svn/sake/expansion_arithmetic.7z If you are interested in actually using this code, we should discuss. I imagine it could be excised out of its containing code base without too much difficulty. - Jeff
Jeffrey, I'd be interested in taking look at it myself.
Perhaps you could push it to the Sandbox?
I don't have a boost svn-sandbox account, but seeing as how the code is not (currently) self-contained and depends on a larger code base, I don't think it belongs in the sandbox. I have zipped up just the expansion arithmetic code and uploaded it to
www.math.ucla.edu/~jhellrun/sake-svn/sake/expansion_arithmetic.7z<http://www.math.ucla.edu/%7Ejhellrun/sake-svn/sake/expansion_arithmetic.7z>
If you are interested in actually using this code, we should discuss. I imagine it could be excised out of its containing code base without too much difficulty.
The Boost Vault would also be a good place to put this. Andrew Sutton andrew.n.sutton@gmail.com
Andrew Sutton wrote:
Jeffrey, I'd be interested in taking look at it myself.
Perhaps you could push it to the Sandbox?
I don't have a boost svn-sandbox account, but seeing as how the code is not (currently) self-contained and depends on a larger code base, I don't think it belongs in the sandbox. I have zipped up just the expansion arithmetic code and uploaded it to
www.math.ucla.edu/~jhellrun/sake-svn/sake/expansion_arithmetic.7z<http://www.math.ucla.edu/%7Ejhellrun/sake-svn/sake/expansion_arithmetic.7z>
If you are interested in actually using this code, we should discuss. I imagine it could be excised out of its containing code base without too much difficulty.
The Boost Vault would also be a good place to put this.
Good idea. Done. File is vault/sake_expansion_arithmetic.7z. - Jeff
Jeffrey Hellrung wrote:
Andrew Sutton wrote:
Jeffrey, I'd be interested in taking look at it myself.
Perhaps you could push it to the Sandbox?
I don't have a boost svn-sandbox account, but seeing as how the code is not (currently) self-contained and depends on a larger code base, I don't think it belongs in the sandbox. I have zipped up just the expansion arithmetic code and uploaded it to
www.math.ucla.edu/~jhellrun/sake-svn/sake/expansion_arithmetic.7z
If you are interested in actually using this code, we should discuss. I imagine it could be excised out of its containing code base without too much difficulty.
The Boost Vault would also be a good place to put this.
Good idea. Done. File is vault/sake_expansion_arithmetic.7z.
Thanks! I'll take a look at it and give feedback here. Best regards, -- Mateusz Loskot, http://mateusz.loskot.net Charter Member of OSGeo, http://osgeo.org
participants (10)
-
Andrew Sutton -
Barend Gehrels -
Jeffrey Hellrung -
Mateusz Loskot -
Michele Caini -
Rene Rivera -
Robert Ramey -
Simonson, Lucanus J -
Stefan Seefeld -
Vladimir Prus