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-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 
specializations.

Regards, Barend