Re: [boost] [Review] GGL review starts today, November 5th

Subject: Re: [boost] [Review] GGL review starts today, November 5th
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2009-11-19 22:19:13

> Please always state in your review,
> whether you think the library should be accepted as a Boost library.

This is a difficult question in this case, because it is not completely clear what it means. I found out during my review that the library as submitted for review is "work in progress", at least in parts. So I vote for acceptance, but try to explain how to interpret that vote.

The library as a whole is not ready for release, but it is ready enough for a formal review, especially if we consider that it is normally expected that a library author will modify his library after a formal review to address the most important issues that came up during the review.

The following parts of the library look completely finished and polished to me:
- The design of the tag dispatching system, including all implementation details, the documentation of the rationale for it and the explanation of how it works and how it can be extended.
- The configuration of the algorithms by the strategies, including all implementation detail, the documentation of the rationale and the explanation of how to use it.
- The overall file and directory structure, including the setup of the regression-test system and the regression-tests themselves.

The following parts of the library failed to give me the impression that they are finished:
- The user level documentation
- The geometry concepts

One of the underlaying problems of the unfinished parts seems to be caused by an unclear position with respect to the relationship to certain OGC specifications. (And I'm not referring to the names of the concepts and certain algorithms here.) As an example, box and segment seem to be considered as second class citizens sometimes, because they are not part of the OGC specifications. Another example is that a clear documentation of the ring concept is considered not so important, because it is part of the OGC specifications (Barend wrote: "Agree that it could be enhanced, but please add that we refer to OGC which documents the meaning of geometric semantics and concepts in detail."). On the other hand, one OGC specification has a triangle as a specialization of a polygon, but GGL has neither a triangle concept, nor do the polygon concept allows to easily create a triangle class that fulfills the polygon concept. There are examples that try to show how to create a triangle class that fulfills the ring concept instead of the polygon concept, and as it turns out even this doesn't really work well.

In theory, it should be clear that the relationship to OGC must stay on a purely naming-consistency level, if GGL really wants to be a generic geometry library and not a GIS geometry library. In practice, it seems to be difficult to ignore all the experience that you have collected in the GIS domain, especially because OGC provides so many nice reference documents.

So how can I vote for acceptance when I consider two vitally important parts like the user level documentation and the geometry concepts as unfinished? Well, first of all, the finished and polished parts are really excellently done (in my opinion). So I hope that the authors will acknowledge that some parts are not yet finished, and that the yet unfinished parts will be of the same high quality as the already finished parts after they have been finished and polished. (I guess the authors would have waited longer before they requested a formal review if there would not have been the Boost.Polygon review. So I think there are good excuses why they submitted "work in progress" for formal review.) Another reason why I vote for acceptance is that GGL has three devoted developers that try to collaborate well with other developers (like incorporating the work of Federico J. Fernández on spatial indexes or trying to work with Brandon Kohn or Lucanus Simonson).

> - What is your evaluation of the design?

Are we taking about the design of the "dimension-agnostic, coordinate-system-agnostic and scalable kernel" here? Honestly, I don't know exactly what is meant by this. So let's evaluate the "tag dispatching system" and the "configuration of the algorithms by the strategies" instead.

The tag dispatching system seems to work well and it's details are well thought out and explained. Inheritances between the concepts is currently not present (which is sad, a ring as a specialization of a polygon would have been interesting), so it is difficult to directly compare it to the corresponding SFINAE dispatching system of Boost.Polygon. But the code is indeed easy to read, I got the impression that I was able to understand how it works from the explanations and would be able to write my own extensions, if necessary. And it didn't had any troubles with different compilers. The much more finished Boost.Polygon on the other hand really was constantly fighting with different compilers. So tag dispatching really seems to have advantages over SFINAE.

The "configuration of the algorithms by the strategies" seems to works well and it's details are well thought out and explained.

The design of the geometry concepts is not yet perfect. Some details of problems with the current geometry concepts were given above. How about the "dimension-agnostic"? The existing geometry concepts are quite focused to 2D, both 1D and 3D fall short. Cartesian products of spaces or geometries and quotient space constructions are completely ignored. (An axis aligned box is a Cartesian product of 1D intervals, for example. Representing it by two points is convenient and makes sense as a representation, but ignoring the Cartesian product part is still not good.) It's good that there are segments, because a polygon is mostly defined by its segments, in the same vain as a triangulated surface is mostly defined by its triangles.

This also explains for me why requiring a polygon/ring to have the first and last point equal could make sense. After all, these points just define the corresponding segments. But nevertheless, I'm not sure whether this requirement is really a good idea. The requirement that a ring/polygon be closed has many consequences. First of all, it seems to make adapting legacy polygon classes much more difficult. On the other hand, a Polygon is not so much a collection of points as a collection of segments, so it is understandable that we want to make it easy and efficient to iterate over the segments of a polygon.

Does the library enables me to write the geometric algorithms that I want in a generic way? For 2D algorithms, the answer is probably yes.

A thing I noticed is that the different functions don't follow any obvious conventions about the order of their arguments. Sometimes the 'intended' return parameters (out parameters) are the first parameters (as most of us would expect), sometimes they are in the middle, sometimes they are at the end.

> - What is your evaluation of the implementation?

The implementation looks quite nice to me. I especially like that the algorithms and the concepts are not in the same source file (as is often the case for Boost.Polygon).

However, one question arises with respect to the extensions, because they already exist, but are not reviewed. Will the extensions be added to the library in boost without further review? Will they be distributed separately?

> - What is your evaluation of the documentation?

The documentation is not sufficient. However, this is not a statement about the quantity, but about the organization, and about what is documented. Many individual algorithms and functions actually have a quite nice documentation. However, the overall picture is missing, and the reference to OGC specifications or examples is no substitute for a proper documentation.

The position of GGL with respect to open/closed set interpretation of geometric objects (= how to treat the boundary of geometric objects) is not clearly documented.

I actually collected many typos during my review, and corrected some in the corresponding source files, but I will have to send this in a separate mail. (And I probably should also elaborate more on the points were the documentation could/should be improved.)

> - What is your evaluation of the potential usefulness of the library?

I guess we all agree that a foundation for a geometry libraries and algorithms in general would be quite useful.

And the proposed library is more than just this foundations. There are utilities for input (WKT) and output (WKT, GeoJSON, SVG), distance computations with respect to different coordinate systems nad much more additional functionality like arithmetics, simplify, boolean operations, compare, ???

> - Did you try to use the library?  With what compiler?  Did you have any
> problems?

I used it with VC9express and gcc-4.3.4. The crashing/hanging intellisense of VC9express is really annoying, but is this really the fault of GGL?

> - How much effort did you put into your evaluation? A glance? A quick
> reading? In-depth study?

I read the documentation, tried the examples, had a look at some of the tests, stepped through some of the existing code with a debugger, tried modifying some of the existing examples slightly (with disappointing effects...). I also tried to look up the referenced OGC specifications, which was probably not a good idea. I tried to build the soci examples, but gave up when I had to build soci.

> - Are you knowledgeable about the problem domain?

What is the problem domain?
GIS? no, I'm not knowledgeable about GIS.
VLSI? yes, I'm quite familiar with it, but that was the problem domain of Boost.Polygon.
Computational Geometry? a bit.
Generic Geometry? Sorry, never heard of that problem domain. Is this related to the Erlang Program of Felix Klein?
Generic Computational Geometry? not really. I heard that CGAL should cover quite some ground there, but I never worked with CGAL, only browsed over some of its documentation.
Geometry? I know enough geometry to have some feeling about all the uncountable many things in geometry that I don't know.

Final comments:

The library is "work in progress". I looked in the policies, and didn't found anything that disallows accepting such libraries. But it should be clear that the first public release must meet higher quality standards.

I heard that GGL has its own mailing lists. When GGL gets accepted as boost library, this mailing list should at least be referenced in the "http://www.boost.org/community/groups.html" section of the boost web page. It might also be nice if in this case, that list would be open to discussions regarding the development of geometry related boost libraries and questions about them in general.

Regards,
Thomas