Re: [boost] Formal Review: Boost.Polygon starts today August 24, 2009

Subject: Re: [boost] Formal Review: Boost.Polygon starts today August 24, 2009
From: Barend Gehrels (barend_at_[hidden])
Date: 2009-08-31 18:33:50

>
> The formal review of the Boost.Polygon library by Lucanus Simonson 
> starts today, August 24, 2009 and will finish September 2, 2009.
>
First, congratulations Luke, and also Gyuszi, with having finished this 
library and having it for review.

As one of the authors of another Geometry Library, also aimed for Boost, 
I'll try to be as objective as possible. I'll not compare it too much to 
our library, though I'll give some performance measures compared with 
many other libraries, also ours (ggl).

When I started testing Boost.Polygon, in February or March, there was 
not yet any documentation, it was difficult to write the benchmarks, it 
didn't compile using MSVC 2005. That is all solved now, it is 
documented, it compiles using MSVC 2005 now, there are some positive 
reviews on design, implementation and the paper. So this is a good step 
forward.

In my domain (GIS) we, normally, only use floating point coordinates on 
arbitrary angle polygons. I'll not review the 45/90 polygons because I 
don't know them and I'm not interested in them.

Expectations: I think a templated Boost.Polygon library should at least:
1) support most of the basic polygon geometry algorithms
2) have a performance comparable to other libraries
3) support both integer and floating point coordinate types

1) the library supports many operations, but some basic polygon 
algorithms are missing:
- convex hull
- centroid
- is_convex
Those operations are found in many libraries and I think they should be 
supported by Boost.Polygon. It would also make the performance 
comparison (even) more interesting.

2) though some reviewers were satisfied about the performance, and the 
paper indicates it is well performing, our benchmark shows that it is in 
general slower or much slower than other libraries:
- the performance of the "contains" operation is perfect, fastest available
- the "area" operation is about a factor 1.5 slower than most other 
libraries. This is surprising because "area" is quite a simple 
operation, it should be possible to implement it with the same 
performance as e.g. CGAL or wykobi.
- the "intersection" operation is too slow compared with other 
libraries. The paper (referred to in the documentation) compares the 
intersection performance with GPC and CGAL, but does not give exact 
figures. It gives some plots about scalability using a very high number 
of points per polygon.

In normal usage, in nearly all cases, GPC outperforms Boost.Polygon with 
a high factor:
--> GPC: 9.0 seconds, GTL/Boost.Polygon: 92.2 seconds for the same 
operation (for 100 points per overlayed ellipse)
--> GPC: 13.7 seconds, GTL/Boost.Polygon: 115.3 seconds for the same 
operation (1000 points per overlayed ellipse, which is already large).
--> Also with 10000 points GPC is still much faster (factor 5).
--> Only in high-intersection-densities with a very high number of 
points GTL is faster than GPC.
If I was a user and license would allow me, I would definitely take GPC 
and not BP, because of performance and because of floating point...

--> compared with CGAL: in normal usage, GTL is indeed faster. But in 
intersection-dense environments CGAL scales better (this in contrary to 
the paper)
--> compared with GGL: in normal usage Boost.Polygon is a factor 81.1 
slower than GGL. While it was suggested that we should use BP for our 
boolean operations, and we evaluated this (resulting in this 
comparison), we're glad that we first compared it to other libraries 
because a user can wait for 1 second, but cannot wait for 92 seconds... 
for a less precise result... In all tests GGL is way faster.
--> for the complete overview, see 
http://trac.osgeo.org/ggl/wiki/Performance and 
http://trac.osgeo.org/ggl/wiki/IntersectionMore

Most of our benchmark results are contrary to the results of your paper. 
I think that if you write things like this, you should publish the 
benchmark sources because it is very sensitive information. People 
should be able to reproduce them. Also exact figures in the paper would 
help to interpret the results.
The Boost.Polygon library is specialized for boolean operations and the 
paper is all about performance. But in the end it is really not 
performing well...

3) Boost.Polygon supports integer but does not support double for 
boolean operations.
For the operations "area" and "contains", coordinates in "double" 
floating precision are supported. Also the boolean operations accept 
double coordinates, but crashes immediately. I think it should not 
crash, slightly better is to prevent floating point coordinates by 
giving a compilation error. Much better: floating point coordinates 
should be implemented. For me as GIS-user, a library without floating 
point support is unusable.

For the comparison I converted to integer coordinates (multiplying using 
a factor of 10000.0). But in the resulting summed area you can see that 
this is not working perfectly. The area differs, and where it should 
increase (star-ellipse with more and more points) it is decreasing... I 
tried other integer-double-conversion factors as well but that made 
things worse.

>
>
> - What is your evaluation of the design?
It is difficult to answer this question because I (with Bruno, and some 
folks of this list) designed another library in another way, it is hard 
to be objective here. I would prefer a geometry library, instead of a 
polygon library. Polygons come seldom alone. It would be useful to have 
other geometry types as well.

The 45/90 polygons could be implemented as specializations (special 
cases) of the normal polygons, overriding implementations. This library 
is designed the other way round, it started with 90/45 polygons and 
arbitrary polygons were added to be submitted as a boost library.

The diagram shows the polygon_90 as a refinement to a rectangle, the 
polygon_45 as a refinement to a polygon_90, the polygon as a refinement 
to a polygon_90, and a polygon_45_with_holes as a refinement to both a 
polgon_90_with_holes and a polygon_45. All this makes really no sense to 
me, I think it could and should be much more simple.

> - What is your evaluation of the implementation?
It is curious that Boost.Polygon went from Tag Dispatching to SFINAE 
last year, while we (GGL) went from SFINAE to Tag Dispatching. We're 
very glad with our change, while most compiler problems and warnings in 
Boost.Polygon origin from the SFINAE implementation. I'm still convinced 
that Tag Dispatching, suggested to us on this list by Dave Abrahams, is 
a very good choice in a geometry library implementation. We're happy 
with it and all compiler and compatability problems are vanished.

Things are copied from other boost libraries. File isotropy.hpp contains 
a nearly literal copy of enable_if. There is also an extraction of MPL. 
While this is an explicit choice, I don't think it is a good choice. The 
Boost Concept Check Library is not used to check concepts.

I didn't try everything, but I'm getting the feeling that the concepts 
are not implemented as they should be. The file polygon_set_concept.hpp, 
which should give an outline of the polygon set concept, is dependant on 
polygon_set_data.hpp (which implements that concept). That should be the 
other way round. Inside that concept file, points are often copied into 
a polygon_set_data temporary. That is not how concepts should be 
implemented, and is very bad for performance.

The file transform.hpp contains a large number of enumarions for 
transforming polygons up/down/west/east etc. I think this is not 
necessary, and besides that "west" / "east" gives the impression of 
spherical coordinate systems while this library is cartesian only. 
Left/right should already be better, but why not two offset numbers in 
two dimensions?

> - What is your evaluation of the documentation?
I didn't read all. It is looking good but contains several errors in the 
details. E.g. documentation of the polygon_90_with_holes_concept, 
function begin_holes has the description  "Returns the begin iterator 
over the range of coordinates that correspond to horizontal and vertical 
edges.". This is probably copy/paste error. Another example is the "void 
clean() const"  function, which cannot be const of course, indicating 
that this documentation is written / copied / pasted and not generated 
with e.g. Doxygen.
> - What is your evaluation of the potential usefulness of the library?
I think most people using geometry / polygons are using floating point 
coordinates. As these are not supported in the algorithms where this 
library is specialized on (booleans), I think it is useful for a limited 
public (VSLI?)
> - Did you try to use the library?  With what compiler?  Did you have any
> problems?
MSVC 2005, MSVC 2008, GCC 4.4 using MinGW. Everything compiled but the * 
notation for intersections didn't compile anymore (it did before)
> - How much effort did you put into your evaluation? A glance? A quick 
> reading? In-depth study?

An in-depth study to several aspects of the library

> - Are you knowledgeable about the problem domain?

I'm designing and implementing GIS / geometry libraries since 1992.

I hope that my review was as objective as can be expected from an 
alternative library writer.

I conclude with the remark that I've asked several times on this list 
and off-list for cooperation, I suggested that Luke could join us 
writing a combined Geometry Library for Boost. All these requests were 
never answered. I would still be in favour of one library.
If this library is accepted it will create a different situation for 
subsequent geometry libraries. In reviews it will be expected that these 
libraries work together or that one is built on top of the other. If 
that is the case, the base should be very very good. It is to the other 
reviewers to decide that this is the case.

Regards, Barend