[Review] GGL review starts today, November 5th
Hi all, The formal review of the Generic Geometry Library (GGL) starts today, November 5, 2009 and will finish November 15, 2009. GGL is being developed by Barend Gehrels, Bruno Lalande and Mateusz Loskot, with substantial input from this Boost mailing list. ------------------------------------------------ About the library: GGL defines concepts for geometries and implements some algorithms on such geometries. GGL is header-only, and can be applied in all software where geometry plays a small or a larger role. Users of the library can use just only one function, such as distance: int a[2] = {1,1}; int b[2] = {2,3}; double d = ggl::distance(a, b); Library users can also use the library in combination with std::vector, boost::tuple's and boost::ranges, such as: std::vector<boost::tuple<double, double, double> > line; line.push_back(boost::make_tuple(1, 2, 3)); line.push_back(boost::make_tuple(4, 5, 6)); line.push_back(boost::make_tuple(7, 8, 9)); double length = ggl::length(line); GGL can also be used in combination with custom or legacy geometries, adapting them to the library specializing traits classes or using registration macro's. Formally, GGL contains a dimension-agnostic, coordinate-system-agnostic and scalable kernel, based on concepts, meta-functions and tag-dispatching. On top of that kernel, algorithms are built: area, length, perimeter, centroid, convex hull, intersection (clipping), within (point in polygon), distance, envelope (bounding box), simplify, transform, convert, and more. The library is also designed to support high precision arithmetic numbers, such as GMP. The GGL might be used in all domains where geometry plays a role: mapping and GIS, gaming, computer graphics and widgets, robotics, astronomy... The core is designed to be as generic as possible and support those domains. However, for now the development has been mostly GIS-oriented. The GGL team proposes an extension model, very similar to what is used by GIL. The proposal as it is in the Boost Sandbox included three extensions: - SVG because it is used in the samples and to generate the documentation - WKT because it is used in the tests - The geographic coordinate system because it is used in some of the examples, also showing how other coordinate systems can be implemented There are more extensions, not included now, a.o.: - Spatial index - Map projections The proposed GGL has seen four previews, many discussions and many changes in design and implementation, based on those discussions. Previews were published on this list January '08, March'08, October'08 and February'09. GGL can be found in the sandbox https://svn.boost.org/svn/boost/sandbox/ggl/formal_review, including source code, examples, unit tests and documentation. Documentation can also be found online: http://geometrylibrary.geodan.nl/formal_review ------------------------------------------------------- Everybody on this list is invited to participate in this formal review. I hope to see your review of this library, including your vote, and I welcome your participation in the discussions on the Boost mailing list. Please always state in your review, whether you think the library should be accepted as a Boost library. Additionally, please consider giving feedback on the following general topics: - What is your evaluation of the design? - What is your evaluation of the implementation? - What is your evaluation of the documentation? - What is your evaluation of the potential usefulness of the library? - Did you try to use the library? With what compiler? Did you have any problems? - How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? - Are you knowledgeable about the problem domain? Regards Hartmut Review Manager ------------------- Meet me at BoostCon http://boostcon.com
On Thu, Nov 5, 2009 at 9:19 AM, Hartmut Kaiser <hartmut.kaiser@gmail.com> wrote:
Please always state in your review, whether you think the library should be accepted as a Boost library.
I must admit, I have been on the fence about this for a few days, however, I am giving a Yes vote. Some general thoughts: Integration with Boost.Units should be encouraged. I don't think is_angle, etc should be in GGL. If I have a vector of quantities, things should Just Work. I'm unsure of the focus of GGL. Given the current offering, I don't think GGL is an appropriate name. I don't think Boost.Polygon is appropriate either. IMVHO Boost.Polygon should be Boost.VLSI and Luke can drop floating point support if he believes it offers no benefits to that domain (I'm sure he would love less work :) ). If the GGL authors decide their focus area is the core geometry concepts, then the name GGL is fine. As it is, Barend favors GIS, Bruno favors gaming, and the resulting library is a mashup of GIS terms and other arbitrary terminology and it excels in no one particular area. There even appears to be plans to support 3D CSG operations in the future. Just these three domains are HUGE, warranting libraries all on their own. I suppose the vision would be that each of those domain specific libraries be built on GGL. Ambitious, and I support the vision, but I think the focus needs to be narrowed for the time being.
- What is your evaluation of the design?
IMO, this is a weak spot. The concepts need work. They are poorly documented, and I don't think they represent the minimal set of operations required.
- What is your evaluation of the implementation?
I didn't look at the actual code, but the benchmarks and the ongoing discussions seem to indicate they are of fairly high quality. It sounds like there's plenty of room for improvement, both in robustness and speed.
- What is your evaluation of the documentation?
I agree with all of Thomas' points on the documentation, so I won't make my post longer by restating them all here. I think it would benefit from step-by-step tutorials, much like the Boost.Iterator docs for iterator_facade and adaptor. The concepts should be documented like Boost.Graph.
- What is your evaluation of the potential usefulness of the library?
I think it will be very useful eventually.
- Did you try to use the library? With what compiler? Did you have any problems?
Yes. I spent a few hours trying to get it to with ESRI, a leader in the GIS domain. Their API is completely COM based however, and it proved extremely difficult to get working with GGL. I wasn't able to successfully do this with Boost.Polygon either. I then tried using my own custom math types and had more success, although not without problems. The Examples link at the bottom of the main page of documentation is broken (last line), and custom_point_example.cpp doesn't compile - cs::cartesian needs to be ggl::cs::cartesian. It was not clear what includes I had to include to register my custom point type. GEOMETRY_REGISTER_POINT_2D is defined in ggl/geometries/register/point.hpp, but the following won't compile: #include <ggl/geometries/register/point.hpp> struct test { double x, y; }; GEOMETRY_REGISTER_POINT_2D(test, double, ggl::cs::cartesian, x, y) That gives 33 errors with MSVC 8.0. Instead of tracking it down, I just included everything from the example program. That worked, but I still don't know what is *actually* required to register a custom point. It also doesn't appear that the custom point type can be in its own namespace when using these registration macros. For instance, the following doesn't compile: namespace foo { struct test { double x, y; }; } GEOMETRY_REGISTER_POINT_2D(foo::test, double, ggl::cs::cartesian, x, y) That gives 26 errors, same compiler as before. Since my own custom point was in a math namespace, I had to have "using namespace math" just to register my point correctly. Once I finally got my math types registered, I went on to using some of the functions. distance() worked out of the box and returned the correct answer, but I then wanted to customize the strategy for distance(). Using the haversine strategy caused compilation errors because there was no overload of get_as_radian<>() for my point type. 1. It's not documented that the haversine strategy requires get_as_radian, or at least I didn't see it. 2. My custom point type already has get<> defined, so why not relax the requirements and have haversine do something like: template <int N, typename T> double get_as_radian(const T &p) { return get<N>(p) * constants::pi_over_180(); }; by default? I finally got haversine working with my point type by defining get_as_radius as above, and the result was correct. I then went on to define my own distance strategy based on the Vincenty distance formula. This almost went smoothly, except that I had to specialize strategy_tag, but didn't see any mention of this requirement in the docs. Once I did that, my distance strategy worked and returned the same value as haversine for values along the equator.
- How much effort did you put into your evaluation? A glance? A quick reading? In-depth study?
5-6 hours reading the documentation and making toy programs using and extending the library.
- Are you knowledgeable about the problem domain?
Yes, I am knowledgeable about geometry as it relates to video games, as well as GIS. --Michael Fawcett
Hi Michael, Thanks for your review! I don't understand some of the problems you have had, so I'll explain or ask some things.
Some general thoughts:
Integration with Boost.Units should be encouraged. I don't think is_angle, etc should be in GGL. If I have a vector of quantities, things should Just Work.
I think you mean is_radian, which is used internally to know if spherical coordinates are in degree's or in radian's. We didn't thought it a good idea, just for this one piece, to integrate with another boost library. Though for some coordinate systems it certainly would make sense (see also answer to Brandon's review)
As it is, Barend favors GIS, Bruno favors gaming, and the resulting library is a mashup of GIS terms and other arbitrary terminology and it excels in no one particular area.
Thanks for your namespace suggestion in another thread. This will help to improve this.
Yes. I spent a few hours trying to get it to with ESRI, a leader in the GIS domain. Their API is completely COM based however, and it proved extremely difficult to get working with GGL. I wasn't able to successfully do this with Boost.Polygon either.
Yes, it would be very cool if this would work nicely, and it is meant to work. It is not clear to me if you get anything working, or nothing. However, I'll come back to you because it would be very useful if there is an example, showing integration between GGL and ESRI.
The Examples link at the bottom of the main page of documentation is broken (last line),
This was not a hyperlink (could be though, sorry)
and custom_point_example.cpp doesn't compile - cs::cartesian needs to be ggl::cs::cartesian.
This surprises me. It is declared within a macro, so ggl namespace is not necessary there. I've not heard of this problem before, and it seems to compile fine normally for everyone (so I must now say: for most people). Are you sure?
It was not clear what includes I had to include to register my custom point type. GEOMETRY_REGISTER_POINT_2D is defined in ggl/geometries/register/point.hpp, but the following won't compile:
Normally, including <ggl/ggl.hpp> is enough, but indeed this should also compile, will be add the dependency.
It also doesn't appear that the custom point type can be in its own namespace when using these registration macros. For instance, the following doesn't compile:
namespace foo { struct test { double x, y; }; } GEOMETRY_REGISTER_POINT_2D(foo::test, double, ggl::cs::cartesian, x, y) [...] I had to have "using namespace math" just to register my point correctly.
Yes, that was a known issue and should have been documented. We didn't search for the solution yet, it must be simple.
Using the haversine strategy caused compilation errors because there was no overload of get_as_radian<>() for my point type.
1. It's not documented that the haversine strategy requires get_as_radian, or at least I didn't see it.
Spherical coordinate systems use get_as_radian internaly (using is_radian), but it should never be necessary to overload it yourself. The normal procedure is registering your point as cs::spherical<degree> coordinate system. That would have been fine, and that was expected for the haversine function. You probably used cs::cartesian, and it didn't know if it was degree or radian. Anyway, I see your problem though, we will correct this and/or document this better.
I finally got haversine working with my point type by defining get_as_radius as above, and the result was correct.
I must say, it is a great workaround, nice that you got it working also like that.
This almost went smoothly, except that I had to specialize strategy_tag, but didn't see any mention of this requirement in the docs. Once I did that, my distance strategy worked and returned the same value as haversine for values along the equator.
To be complete, the vincenty is also part of the gis extension, it was first not included, but later we wanted to show that 07 graph example, showing nicely the integration between BGL and GGL (there were not too many comments on this though). I understand that you implemented your own strategy, very cool. And indeed, you should specialize your strategy_tag, if (and only if) you want to use that one by default. Another way would have been that you specified the strategy as additional parameter. Great you got it all working like this! Of course, everything should work, but you did use some quite advanced features of GGL, and I like to see that you did succeed there. We will work on the documentation so these scenario's will cause less problems. Thanks again, Barend
On Sat, Nov 21, 2009 at 6:57 AM, Barend Gehrels <barend@geodan.nl> wrote:
I think you mean is_radian, which is used internally to know if spherical coordinates are in degree's or in radian's. We didn't thought it a good idea, just for this one piece, to integrate with another boost library. Though for some coordinate systems it certainly would make sense (see also answer to Brandon's review)
Sorry for reporting the wrong name, you guessed right. It would have added more work for sure, delaying the review, but seeing two libraries operate seamlessly together is always nice. I hope this is planned.
However, I'll come back to you because it would be very useful if there is an example, showing integration between GGL and ESRI.
If you need any help with this, let me know. The licenses can be very costly, so it's probably not easy to test.
The Examples link at the bottom of the main page of documentation is broken (last line),
This was not a hyperlink (could be though, sorry)
Ah, it looked like a broken hyperlink since it was bolded, and usually Doxygen auto-links. My mistake, but it would be nice to just jump to the Examples from there rather than scrolling all the way back up.
and custom_point_example.cpp doesn't compile - cs::cartesian needs to be ggl::cs::cartesian.
This surprises me. It is declared within a macro, so ggl namespace is not necessary there. I've not heard of this problem before, and it seems to compile fine normally for everyone (so I must now say: for most people). Are you sure?
No, you are right. I went back to my test programs and must have jumped to that conclusion when I was having all the other compilation issues.
It was not clear what includes I had to include to register my custom point type. GEOMETRY_REGISTER_POINT_2D is defined in ggl/geometries/register/point.hpp, but the following won't compile:
Normally, including <ggl/ggl.hpp> is enough, but indeed this should also compile, will be add the dependency.
Is it only in certain cases when other dependencies are necessary? I went back and tried this again, and indeed it doesn't compile for me. This is with MSVC 8.0, SP1.
Spherical coordinate systems use get_as_radian internaly (using is_radian), but it should never be necessary to overload it yourself. The normal procedure is registering your point as cs::spherical<degree> coordinate system. That would have been fine, and that was expected for the haversine function. You probably used cs::cartesian, and it didn't know if it was degree or radian. Anyway, I see your problem though, we will correct this and/or document this better.
I did use cartesian, so I was definitely misusing the library, but every now and then I think people will want to misuse the library. It should be possible (even if it's harder) and documented I think. Either that, or have an "unpecified" coordinate system type. Basically, think of a use-case where I have hundreds of thousands of points, where I want to display them in "Cartesian" coordinates on screen in an Orthographic projection and need both pixel-space and geodesic distance between points. Do I have to make a copy of every point before one of the operations, or can I coax the distance strategy into doing different things even though my point type can only be registered in one coordinate system (currently)?
Great you got it all working like this! Of course, everything should work, but you did use some quite advanced features of GGL, and I like to see that you did succeed there. We will work on the documentation so these scenario's will cause less problems.
Thanks, the documentation was obviously "enough" since I did get it all working in the end, but it wasn't as smooth as using other boost libraries has been for me. Keep up the good work! --Michael Fawcett
On Fri, Nov 20, 2009 at 7:07 PM, Michael Fawcett <michael.fawcett@gmail.com> wrote:
I'm unsure of the focus of GGL. Given the current offering, I don't think GGL is an appropriate name. I don't think Boost.Polygon is appropriate either. IMVHO Boost.Polygon should be Boost.VLSI and Luke can drop floating point support if he believes it offers no benefits to that domain (I'm sure he would love less work :) ).
The paragraph above is way too random! Each of us can not come up with one idea of what a library should be, and Boost already clarifies what the high level requirements should be. From the home page: "Boost libraries are intended to be widely useful, and usable across a broad spectrum of applications." regards
On Sat, Nov 21, 2009 at 12:53 PM, Jose <jmalv04@gmail.com> wrote:
On Fri, Nov 20, 2009 at 7:07 PM, Michael Fawcett <michael.fawcett@gmail.com> wrote:
I'm unsure of the focus of GGL. Given the current offering, I don't think GGL is an appropriate name. I don't think Boost.Polygon is appropriate either. IMVHO Boost.Polygon should be Boost.VLSI and Luke can drop floating point support if he believes it offers no benefits to that domain (I'm sure he would love less work :) ).
The paragraph above is way too random!
Each of us can not come up with one idea of what a library should be, and Boost already clarifies what the high level requirements should be. From the home page:
"Boost libraries are intended to be widely useful, and usable across a broad spectrum of applications."
I can't understand how that applies to what I said, sorry. I didn't come up with the idea of what the library should be, the library authors did. I believe it's up to the reviewers to determine if the implementation matches the author's intended scope (among many other things). If I had a library that only implemented quad-trees and then proposed it as Boost.Generic Spatial Index, I would think the reviewers would have something to say about that. The Boost.Polygon comments were meant tongue-in-cheeck, note the smiley and "IMVHO". --Michael Fawcett
On Sat, Nov 21, 2009 at 7:18 PM, Michael Fawcett <michael.fawcett@gmail.com> wrote:
On Sat, Nov 21, 2009 at 12:53 PM, Jose <jmalv04@gmail.com> wrote: I can't understand how that applies to what I said, sorry. I didn't come up with the idea of what the library should be, the library authors did. I believe it's up to the reviewers to determine if the implementation matches the author's intended scope (among many other things).
The author's intended scope has to match Boost goals to merit a review. In practice, this is not always the case. These issues have been discussed in the Boost list. The thread is Updating the Boost Review Process - Was Polygon(GTL) vs GGL - rationale. Boost doesn't aim for libraries in a very specific application domain, as stated in the home page.
If I had a library that only implemented quad-trees and then proposed it as Boost.Generic Spatial Index, I would think the reviewers would have something to say about that.
Please note that GGL is a "geometry library" implemented using "generic programming". Though we aim to a broad scope, we don't aim to "generic geometry" Barend
Am Saturday 21 November 2009 19:30:20 schrieb Barend Gehrels:
If I had a library that only implemented quad-trees and then proposed it as Boost.Generic Spatial Index, I would think the reviewers would have something to say about that.
Please note that GGL is a "geometry library" implemented using "generic programming". Though we aim to a broad scope, we don't aim to "generic geometry"
has there been a discussion about the name of the library? with other libraries that has come up and the conclusion was that there are already enough "* Template Library" aka ?TL. Generic Geometry Library comes down to "Generic * Library" aka G?L because like you said "generic" doesn't say anything about the domain of the library, but about the programming style. not much different than "Template". so what's left is: G Geometry.
participants (5)
-
Barend Gehrels -
Hartmut Kaiser -
Jose -
Michael Fawcett -
Stefan Strasser