Boost logo

Boost :

Subject: Re: [boost] Formal Review: Boost.Polygon starts today August 24, 2009
From: Barend Gehrels (barend_at_[hidden])
Date: 2009-09-02 12:49:47

> Barend,
> Inside the Boost review process, you are quite welcome to vote. It is
> a good idea for you to make sure such mitigating factors as you list
> are clear in your review, and it is the review manager's job to
> decide how that should affect the weight given to your vote.
> John Phillips Review Wizard

OK, so here is my vote: NO

I've already sent several issues to this list, and have many concerns
about this library. The main reasons to vote "no" are:
1) it is way too slow
2) its concepts are not sound
3) it is not generic

ad 1) the library is specialized on polygon boolean operations
(intersection, union, symmetric difference). But they are implemented
very slow. Of course everything can be enhanced lateron, but we're
measuring now, we don't know what we will measure lateron. A simple
overlay operation costs 92.2 seconds using Boost.Polygon, versus 1.1
second in GGL. So how can I vote yes for this? Besides that the result
is less precise... Anyone is welcome to test this assertion, to
reproduce my figures.

ad 2) already explained in another posting. The file polygon_set_concept
contains the "area" operation, copying a set of poylgons to another
std::vector of polygons just to calculate the area... This is not sound
in design and in implementation. Copying of polygons is as far as I
glanced through done in many operations for polygon_sets.

ad 3) Quote of John Phillips' mail:
> Many Boost developers (myself included) think a good geometry library
> would be a solid addition to Boost. It is an area that allows generic
> solutions, that has some very persnickety details that are very easy
> to get wrong, and that is applied in a large number of different
> problem and application domains.
I agree with this. But I don't think that Boost.Polygon is a good
geometry library (yet).
a) it is polygon only
b) it is 2D only
c) it is cartesian only
d) it is (for boolean operations) integer only

Look below for an elaboration.

For integers: of course we can map to integer but as I've said earlier,
the results are different. In my benchmark the resulting summed area is
155 vs. 161, which is the correct answer. If I take other factors the
result is even less precise or overflows. Luke, if I'm doing things
wrong here, please tell me. But this deviation is way too large.
Boost.Polygon seems to just unable to handle this case.

Elaboration: let me memorize the previews for GGL here shortly, because
they are relevant, and now that my reactions are classified as
"mine-is-betters-than-yours" anyway.

I came with a geometry library preview in January 2008, which was
criticized on this list because it was 2D only and Cartesian only (it
still had more than polygons) and its concepts were not clear. Those
critics were very welcome because they have greatly enhanced the
library. In the meantime Bruno Lalande (who already contributed to
Boost) joined me. We did another three previews. It has now a sound core
for 2D/3D/nD, it is cartesian as well as spherical, it has clear
concepts modeled as a set of small metafunctions. It is now really
generic. On the last preview there were not so many comments. This
spring Mateusz Loskot joined us, having much experience with open source
and geometry. The library would have been for preview 5 in August, that
was postponed until about October. Intersections are new here by the way.
In between Federico did the Google of Summer spatial index effort, now
included in the library.

The library is now used in e.g. an OpenStreetMap mapping program and the
OpenGraphRouter. GGL is partly hosted by osgeo, partly by Geodan, partly
by Boost Sandbox, this is a somewhat uncomfortable situation so we'll
look forward to have one place for it.

There is, as far as I know, noone who really compared the two libraries,
Boost.Polygon and the GGL. It seems that I'm the only one until now, but
I can be considered as being subjective. It would be very good if an
objective person would compare the two libraries, in design, in
implementation, in functionality, in performance. I also suggested
(off-list) that the libraries could go for (another) review together, at
the same time. But other people were less enthousiastic about that,
being more complicated for the reviewers.

Boost.Polygon is now for review as the first one.

Acceptance of Boost.Polygon might change our efforts. I don't know if
I, or my team, or my employer, will make it possible for us to go for
review as a second boost geometry library. And our generic library
cannot be based on a non-generic kernel. We can and will not go back to
2D / Cartesian. GGL has nearly everything what this Boost.Polygon
library has. It does not have 45/90 angled polygons, nor plans for it.
But Luke is welcome to add them to our library, it is perfectly
feasable, it makes sense. I sent this to Luke last July, to which I
referred to earlier:
> Let me also repeat that you're still welcome to join us. We're
> prepared to add 45 and 90 manhattan geometries. You could implement
> your algorithms as specializations for those cases.

Both parties worked for nearly two years on this boost process and
(future) submission. We've had several useful discussions and I met Luke
at BoostCon. So in a way it is hard to say no. But I think Boost.Polygon
is not the long waited-for geometry library. We should cooperate,
resulting in a generic Boost geometry library, including the VLSI

Regards, Barend


Boost list run by bdawes at, gregod at, cpdaniel at, john at