[boost] GGL Review

Subject: [boost] GGL Review
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2009-11-15 17:10:44

Dear All,

Here is my review of GGL:

I have attempted to try the same examples that I did for my 
Boost.Polygon review.  Unfortunately limited time has made it 
impossible for me to be as thorough as I would have liked.  Here is 
what I have done, and the issues that I encountered along the way.  
(You may want to look at my Boost.Polygon review for background.  It 
can be seen here:  
http://thread.gmane.org/gmane.comp.lib.boost.devel/193204/focus=193758 )

My first exercise was a GUI application in which I wanted to merge a 
large number of small rectangles into a single more complex polygon.  
Unfortunately I failed at the first step with this: I wanted to teach 
the library about my existing types (point, box, etc), but how to do 
this is not properly documented.  It seems that there are some macros 
(with not-Boost-style names) but their only mention in the 
documentation is in an example.  Yes, I could probably have worked out 
what to do from the example, but I have limited time and furthermore I 
don't think it's acceptable to expect a library end-user to learn 
something relatively fundamental like this from an example.  (From my 
brief look at the example, it does look as if this mechanism is 
significantly less verbose that what I had to do to teach Boost.Polygon 
about my types, which is a good thing.)

So I moved on to my second example, which reads a file containing the 
borders of the states and provinces of the US and Canada and determines 
which ones contains points that the user enters.  I implemented this 
using the geometry types provided by the library, so the question of 
adapting to types did not arise.  This all worked quite smoothly, 
though I did encounter the following issues, mainly with the 
documentation, which I imagine could be corrected quite easily:

- The docs do not say what the C template parameter in point_xy<T,C> is.
- The "complete list of members" for ggl::linear_ring is empty.  
(Presumably the issue here is that the members are all inherited from 
the std::container; it could at least say that.)
- The documentation for ggl::linear_ring says that V is a "container 
type e.g. std::vector, list, deque"; it should describe this in terms 
of std concepts (presumably bidirectional container) so that I know if 
my own custom type will work.  Looking at the code I don't see any 
concept-checking for this; that would be nice.
- The args to the within() function are reversed wrt the equivalent 
function in Boost.Polygon.  This is a good example of the issue that I 
raised in a previous email, where the generic nature of the 
concisely-named functions can lead to mistakes.
- Doxygen doesn't give the full path to the headers, i.e. 
"point_xy.hpp" rather than "geometries/point_xy.hpp".
- There seems to be a dependency on Boost.Math that isn't mentioned on 
the list of dependent libraries.
- The library doesn't seem to be in namespace boost.  I guess the 
intention is to add this later.  This is unusual.
- I was surprised that the box class doesn't have width and height members.
- I got a page full of warnings from my test program; the cause seemed 
to be unused parameters in within.hpp, lines 118 and 178.  Since I have 
touched only a small fraction of the library, I imagine there are other 
places with the same issue.

As I said, these are minor issues that I imagine could be corrected 
quickly.  However they did give me the impression that the library is 
still very much a work-in-progress - especially the documentation - 
rather than a fully-formed finished work.  I don't necessarily believe 
that a library has to be perfect before it can be accepted into Boost, 
but I think it needs to be a little less rough around the edges than this.

That unfortunately was all of the actual testing that I have been able 
to do.  I'll now discuss other issues:

Firstly there's the situation concerning Boost.Polygon.  My feeling is 
that the situation that has developed here is very unfortunate.  I 
think it's extraordinary that Boost can even consider having two 
incompatible, overlapping Geometry libraries reviewed within a few 
weeks of each other, with authors who are so publicly antagonistic 
towards each other.  How on earth did we get into this situation?  
(Answer: IMO, the progress towards review flowed to the current 
situation by following the path of least resistance, and "someone" - a 
"leader" ? - should have jumped in earlier to steer things in a more 
constructive direction.)  Anyway, Boost.Polygon has now been accepted 
(within an hour of this review starting! I mean, was that calculated to 
be antagonistic?) and we have to consider what that implies.

One option is to imagine the two libraries in parallel universes.  That 
may be the most stress-free way.  But it's not what would deliver the 
best results for Boost's end users.  What I would prefer to see is some 
work to investigate how more common ground can be introduced.  For example:

- Common terminology.  ("within" vs. "contains", "extents" vs. 
"envelope", and dozens more.  GGL's not-unreasonable adoption of OGC 
terminology is an issue here.)

- Inter-operable types.  I would like to hope that the basic geometry 
traits classes could be shared.  Failing that, perhaps a method of 
forwarding from one set of traits to the other could be used.

I am unsure how deeply the choice of tag dispatch vs. SFINAE makes 
inter-operation more difficult.  Maybe someone could comment on that.

Let me say a little about performance.  There has been a great deal of 
discussion about this on the list.  My feeling is that all libraries 
should document the worst-case complexity of all of their functions.  
In the current case we have polygon boolean operations where I believe 
I learnt as an undergraduate 20 years ago that they should be O(n log 
n).  Here IIUC the implementation is worst-case O(n^2) but typically 
better.  I feel uncomfortable with that, however many benchmarks and 
years of real-world use have gone in to it.  Is it not possible to 
contrive an introsort-like "fallback" solution that gives both good 
typical case performance and an optimally-bounded worst case guarantee?

The other controversial implementation issue is floating-point 
robustness.  I'm still not clear what the position of this library is 
on that.  Are we just given assurances that it seems to be robust in 
real-world use, or is it believed that it actually is certainly 
robust?  I expected to see this discussed in the library documentation, 
but I don't see anything - maybe I've missed it.  If it is "believed to 
be robust in real-world use", it would be helpful to describe the 
possible failure modes (e.g. segfault, runs forever, or just outputs 
the wrong answer.)

In summary:

Congratulations to the authors on getting their library to this point.  
I'm sure that it contains much useful code.

At this time, the library is let down by incomplete documentation, and 
I feel it should be rejected for that.

I believe it is also essential that some effort is done to find common 
ground (I'm avoiding saying "merge") with Boost.Polygon.

If the authors are unable to work together, then I would prefer that 
Boost keep things simple for its end users, and avoid years of 
antagonism on the mailing list, but suggesting that one (or other!) 
library should exist outside of Boost.

To answer the usual questions:

- What is your evaluation of the potential usefulness of the library?
Very useful.

- Did you try to use the library?  With what compiler?
Yes; gcc-4.x on Linux.

- How much effort did you put into your evaluation?
I've spent about 5 hours in all.

- Are you knowledgeable about the problem domain?
I'm not a geometry expert, but I have done projects that could make use 
of this sort of library.

Regards,  Phil.