[boost] [polygon] late review

Subject: [boost] [polygon] late review
From: Gordon Woodhull (gordon_at_[hidden])
Date: 2009-09-14 03:48:41

Hi all,

Sorry this is late - I intended to participate in the discussion, but  
the review schedule happened to intersect with an offline vacation.   
(Plus day job, school starting, etc.)

Thank you, Luke, for submitting what I think is a very good start  
toward a Boost geometry library.  I do not think the library is ready  
for inclusion in Boost at this time, but I believe it will be with  
further improvements.  I would almost vote for acceptance with  
conditions, but the list is long and I think the concepts merit more  
discussion.

Unfortunately I have not had time to take an in-depth look at the  
library; I have read some of the documentation and examples and it  
looks useable.  So this is mostly a non-technical review of the issues  
raised by others.  Also I offer a bit of "meta-review" of the review  
process for libraries that will continue to evolve and merge with  
other libraries.

My application domain is mainly graph drawing (network visualization)  
but I might also use this in 2D screen graphics and games.  For these  
purposes, the restriction to two dimensions is acceptable, and even  
the restriction to integer coordinates is mostly acceptable.  However,  
I think the library name should reflect these restrictions.  It will  
be some time (if ever) before a library can claim to be The geometry  
or polygon library.

Boost has no merge process (if that's even possible), and neither  
Polygon nor GGL subsumes the other, so I think they should eventually  
be accepted in parallel, and merge concepts and algorithms over time.

As I see it, this library provides two major contributions:
1. A set of concepts for VLSI and other 45/90 degree applications  
which can in the future be extended or bridged to other geometric  
problem domains, e.g. GIS, 3D, n-dimensional.
2. An extremely robust and (I believe) efficient polygon intersection  
algorithm.

The interface still needs some work, but the concepts are a valuable  
first pass at defining this domain.  I want to see some system of  
libraries that supports rectangles through arcs all the way up to  
splinegons.  This isn't that, but I am patient.  I will be interested  
to compare the advantages of concepts for polygons with holes versus  
the runtime version in GGL.

I don't agree that accepting a library where the concepts/interface  
are incomplete or even wrong will pollute a future generalized  
geometry library.  This library will just have to improved over time,  
and influenced by libraries from other domains.

To mention just one specific interface problem: I don't like rect -  
int meaning shrink the rectangle.  I think that everyone is going to  
have strong opinions about what operators they like and dislike and I  
hope that some future geometry library will allow choosing different  
sets for different domains.

The intersection algorithm is very, very cool and I hope the ideas can  
be extended someday by someone to provide robust intersection of arcs  
and splines.  I don't yet understand whether this is possible.  I  
agree with those who would like to see lazier evaluation to run the  
intersection algorithm on as much as possible.

Luke and Barend, I'm sorry but I don't believe either of your  
benchmarks.  I think you are choosing problems that suit each of your  
libraries.  This is understandable, but we will need to build a  
comprehensive suite of examples from many different domains to learn  
which algorithms are actually faster in which situations.

Meta-review

I admire the Boost process for protecting authorial control over  
libraries.  However, one consequence is that two very important  
requirements, maintenance and cooperation, are only ensured indirectly  
by vigorous debate.

1. Maintenance.  This is not really addressed by the Boost rules or  
review process, except to remind authors that they will be responsible  
for maintenance or for finding a new maintainer.  There is no way to  
compel authors to respond to their users except for the threat of  
library removal which IIUC has almost never happened.

So one of my essential criteria in reviewing a library - I've only  
reviewed one other library but followed many other reviews closely -  
is the attitude of the author toward changes requested.  Users are  
inevitably going to have new requirements.

Luke definitely seems willing to make the changes that are needed to  
get this into Boost, and I trust that he'll continue to help it  
adapt.  I am slightly concerned that Intel will not allow the library  
to depend on Boost because I think that will slow down improvement.   
In particular I think operator customization and lazy evaluation would  
be helped by using Proto.  I hope Intel will allow this.  Or maybe  
that's the scope of a different library.

2. Cooperation.  Boost has no rules or process for making libraries  
work together, never mind merging them.  Maybe there is some work to  
be done here.  But people will naturally want to make their libraries  
compatible if they're under the same umbrella.

Competition is also a healthy human drive, but it's especially  
productive when there is some basis of cooperation, as I think there  
is between Luke and Barend, despite how nerves may have frayed during  
this review.

I hope that both libraries are accepted, when ready, and that the  
authors and others interested in a "universal" Boost geometry library  
work to find the commonalities and connections.

Fervently waiting,
Gordon