[Boost-users] [Review] GGL review starts today, November 5th
Hartmut Kaiser
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
_______________________________________________
Boost-users mailing list
Boost...@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Michael Fawcett
>
> 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
Barend Gehrels
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.
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.
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.
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:
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.
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.
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.
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
Jose
<michael...@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
Michael Fawcett
> On Fri, Nov 20, 2009 at 7:07 PM, Michael Fawcett
> <michael...@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
Jose
<michael...@gmail.com> wrote:
> On Sat, Nov 21, 2009 at 12:53 PM, Jose <jma...@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.
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.
>
programming". Though we aim to a broad scope, we don't aim to "generic
geometry"
Barend
Jose
<michael...@gmail.com> wrote:
> The Boost.Polygon comments were meant tongue-in-cheeck, note the
> smiley and "IMVHO".
Actually yes, I din't get the irony the first time! Sorry, I'm very
sensitive to this topic
Stefan Strasser
> > 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.
Michael Fawcett
>
> 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!