Subject: [boost] [polygon] late review
From: Gordon Woodhull (gordon_at_[hidden])
Date: 2009-09-14 03:48:41
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
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
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
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.
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
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk