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

Subject: Re: [boost] [Review] GGL review starts today, November 5th
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-11-15 19:02:00

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

The library should be accepted contingent on several concerns discussed below being addressed.  Feedbacks labeled "Concern" are things I feel the library should be accepted contingent upon changes.  Feedbacks labeled "Minor Concern" are issues I have identified, but should not prevent the library from being released as part of boost.

I would like to integrate the polygon intersection (and perhaps convex hull and centroid) algorithms into my own library, and my concerns are things that I think need to be addressed before I would undertake integrating the two libraries.

> Additionally, please consider giving feedback on the following general
> topics:
> 
> - What is your evaluation of the design?

The design of the generic interfaces is good.  The library is extensible and flexible.  I like how easily stl data structures can be adapted to satisfy geometry concepts.  I don't like that stl interfaces are required to satisfy some concepts, and in particular I'd like the polygon concept made more generic.

Concern: polygon concept interfaces need to be made more generic by making them consistent with the linestring and ring concept interfaces.  

Concern: linestring requires random access iterator semantics.  This should be relaxed to forward iterator semantics. 

> - What is your evaluation of the implementation?

I focused my evaluation of the implementation on the polygon intersection algorithm, where I am most knowledgeable.  I found the implementation very clean, but also apparently incomplete.  I have several concerns about the implementation of polygon intersection.

Concern: only interfaces intersection and union between two polygons are currently implemented.  Intersection, union, xor and AND NOT operations should all be supported on multi-polygons.  Also the union of a single multi-polygon should be supported.  AND NOT and xor are both composable from intersection and winding direction inversion.  I find it strange that the author brought the library to review without implementing these.

Concern: as submitted the polygon intersection algorithm is very weak in the line intersection algorithm.  This flaw can either be addressed by the author by applying his query-tree based optimization, or by myself by applying divide and conquer in one axis and sorted scan in the orthogonal axis.

Minor Concern: the polygon intersection algorithm is weak to large numbers of holes.  This is fundamental to the choice of the graph-traversal polygon formation algorithm, which provides no information about what polygons contain what holes.  This is a common problem in polygon clipping implementations and is exhibited by some of the best and most expensive closed source implementations.  I would suggest that the author provide a multi-ring interface to the polygon intersection algorithm such that polygons and holes are written out distinguished by winding direction and not associated with each other.  This would allow the user to avoid the costly step of associating holes to outer shells in the circumstances where that information is not required.

Concern: I found a bug in the implementation of polygon intersection during the review.  This bug should be fixed before the library can be accepted.

Concern: I am skeptical that adequate testing of the polygon intersection algorithm has been done.  I'd like to see a more comprehensive testing strategy pursued including high volume, randomly generated test inputs.  This stress testing is essential to ensure that bugs like the one I found don't make it into a boost release.  These tests should not be considered unit tests, and need not run when boost unit tests are run.

Concern: The algorithm is not robust.  The line segment intersection predicate is not robust with floating point calculations, meaning that the results produced can be incorrect from a topological point of view; intersections can be missed or erroneously inserted.  Also, because the intersection point is calculated with floating point there are a significant number of bits of precision lost, meaning that the intersection point can end up moving much farther than a single floating point grid position.  Lateral movement of line segments due to intersection point insertion due to loss of precision and or snapping to the coordinate grid and result in self intersecting outputs being produced.  The line segment intersection predicate needs to be enhanced to make it robust and the output needs to be checked for self intersection and recycled through the algorithm until the check passes.

> - What is your evaluation of the documentation?

I really did not like the doxygen generated content.  I found it difficult to find the real documentation among all the doxygen generated fluff.  The documentation that was authored by a human was very good, though somewhat incomplete.  I'm concerned that people may misinterpret the documentation and conclude that features that are not yet implemented are already supported because the interfaces such as distance() appear to accept all geometry pairs, but in fact do not.

Minor Concern: it should be more clear what concepts do and don't work with a given interface.  If a feature is planned and not yet implemented it should be stated in the documentation for its interface and the documentation can be updated when the feature is implemented.

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

My strongly held belief is that a polygon clipping implementation that is not robust has no value.  The library is potentially very useful if the polygon intersection algorithm is enhanced to make it robust.  I consider the polygon intersection algorithm to be the highest (potential) value piece of the library.

I think the stated scope of the library (generic computational geometry) differs from the scope of what has been implemented (generic 2d floating point GIS focused geometry).  I feel that the scope of the library should be brought in line with what is implemented and planned, and that scope should be reflected in its name.

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

I compiled it with gcc 4.2.2.

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

I spent about two days working with the documentation and the code.  I gave some portions of the library a glance, others a quick reading and the polygon intersection received an in-depth study.

> - Are you knowledgeable about the problem domain?

For polygon clipping I've read all the relevant papers and implemented my own.  For GIS, I'm an outsider.  For generic interfaces I guess I'm at least somewhat knowledgeable.

Thanks,
Luke