
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

Gordon Woodhull wrote:
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.
Note that the GGL benchmark is Open Source, can be repeated by anyone and can also be extended by anyone. So please add your problem, either directly to the suite or you can suggest it to us such that we can check it. Regards, Barend

On Sep 18, 2009, at 5:00 PM, Barend Gehrels wrote:
Gordon Woodhull wrote:
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.
Note that the GGL benchmark is Open Source, can be repeated by anyone and can also be extended by anyone. So please add your problem, either directly to the suite or you can suggest it to us such that we can check it.
I surely will, when I have time. To tell the truth, geometry performance has not been much of an issue on most of what I've worked on, where speed is dominated by what's generating the smallish geometries. Based on the presentations of the algorithms given at Boostcon I would expect GGL to be faster on smaller cases and Polygon2D4590 to excel on really huge sets with tons of intersections. Neither algorithm seems to be completely mature. My larger point is that there might be room for many various intersection algorithms for different 2D geometry domains. Looking forward, Gordon
participants (2)
-
Barend Gehrels
-
Gordon Woodhull