Boost logo

Boost :

Subject: Re: [boost] Formal Review: Boost.Polygon
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2009-09-06 13:11:31


I am pleased to be able to review this important library. Boost would definitely
benefit from the addition of a geometry library of the right sort.

I am certainly not a geometry expert, but I have written a number of
things in the
last few years that use geometry in GUIs and for geographic data. I
have written this
review as a potential user by evaluating how well it would work in a
couple of example
applications.

My experience over all has been a little disappointing. I think this
is mainly because
I had very high hopes for the library. The reality has not quite met
my expectations.
As I will explain in detail below, my complaints are mainly things like excessive
warnings and odd misfeatures in the interface. These are all things
that could be
fixed, and they perhaps only indicate that the library has arrived a little
prematurely. Based only on these issues my verdict would be that that
the library
could be accepted after some revisions. But we must also look at the
bigger picture,
i.e. the existence of other competing libraries "in the wings". I will
discuss this
after describing my practical evaluation.

Points starting ** in the following are issues that I think should be
fixed for the
library to be acceptable.

Application 1
-------------

I have an application that can display placename search result markers
on a world map
(see http://chezphil.org/tmp/six_thousand_lakes.jpeg). When no markers
are shown the
screen can be updated at about 20 frames per second; when many markers
are shown
the frame rate drops to the point where usability is impaired. In this
case the vast
majority of the markers overlap each other, and this could be exploited
to reduce the
amount of work that needs to be done by the graphics hardware and hence
boost the
frame rate.

The first step was to add the "magic" required by the library to
support my rectangle
type. The examples don't seem to include a custom rectangle, and the decomposition
of a rectangle into a pair of intervals rather than the more common
pair of points or
point and size, made this a bit tricky. More serious were the
following problems:

** The library does not seem to use any sort of explicit concept
checking; if types do
not satisfy their concepts random errors from deep inside the library
are emitted. The
verbosity and incomprehensibility of errors from complex C++ code is,
in my opinion,
the greatest single failing of the language today. In the face of
these ridiculous
messages, some users will simply abandon trying to use the library (or
the whole
language, and go back to C) or limit themselves to only what can be
done by copying
examples. Fixing this needs effort from the language designers,
compiler writers, and
libraries. I am not certain that concept checking can totally cure
this problem,
but it can only help.

** The library spews out enormous quantities of warnings (gcc 4.1.2), I
think mainly
related to unused parameters. This has to be fixed (and I don't
believe fixing it is
hard).

** The library failed to work with std::pair being used as the interval
type, despite
this being mentioned as a possibility in the documentation. The
problem seems to be
that the std namespace is brought into ADL and std::set is found rather
than the
library's own set function. I have not investigated how hard this
would be to fix;
instead I wrote my own pair template.

Having completed the "magic", I started to adapt my marker drawing
code. My first
attempt was a minimally-invasive version that would check if each
marker covered any
new area and not plot it otherwise:

   if (!contains(markers,b)) {
     markers |= b;
     plot(b);
   }

Unfortunately this failed since contains() does not seem to be defined
for a
polygon_90_set and a rectangle. This surprised me somewhat. A
valuable addition to
the documentation would be a matrix indicating which operations are
supported between
which types. Somebody will need every combination of operations and
types, and it
would be useful to see quickly which are provided, which are planned
for a future
version of the library, and which cannot be implemented due to some
restriction of the
library design.

I could have tried to implement contains(polygon_90_set,rectangle) in
terms of e.g.
intersection but I was concerned that that would have much worse
complexity than an
optimised contains() algorithm could have. Which raises another issue:

** Algorithms should indicate their complexity guarantees, and (where
different) their
expected complexity for common inputs.

So I moved on to a more invasive modification where I accumulate all of
the rectangles
and use get_rectangles() at the end to extract a minimal set of areas
to plot:

   for (...) {
     markers |= b;
   }
   get_rectangles(rects,markers);
   foreach(rect in rects) {
     plot(rect);
   }

This works, and reduces the number of rectangles that are plotted from
about 6,000 to
about 900. Unfortunately get_rectangles() takes about 100 ms to run,
which is
slightly longer than plotting the redundant markers would have taken,
so overall the
frame rate is not improved.

In that code, I was surprised to see that get_rectangles takes an
output container by
reference. In this case, I have no need to allocate memory and store
these rectangles
at all. I would have prefered some way to get the rectangles as they
were generated
and pass them directly to my plot function, e.g.

   for_each_rectangle(markers, &plot);

An output iterator would be a more conventional (but in this case more
verbose) way to
achieve this.

** Unless there is some good reason for using output reference
parameters, algorithms
should use output iterators.

I was also a little confused by the difference - if any - between
"markers |= b" and
"markers.insert(b)". I believe that I know what the former does, but I
worry that
unioning-in each rectangle in turn is inefficient and that it would be
better to
construct a set of rectangles and self-union in one go. Perhaps this
is what insert()
does - yet there is no self_union function, and in practice I seem to
get the same
results. Maybe get_rectangles() has done the self_union. Some
clarification of this
in the documentation would be useful.

Application 2
-------------

I have data for the borders of N. American states and provinces. My
original plan was
to try to reduce these state outline polygons to a set of polylines; my
viewer does
this as a pre-processing step to halve the work it does when plotting
these borders.
But the library really is limited to polygons (hence the name), with no
support for
even representing polylines let alone doing anything with them. It
would be useful for
the documentation to include a "roadmap" section indicating whether
this is being
considered for a future version. It might be worthwhile to define
polyline and other
concepts now, if they are relatively uncontroversial, to avoid multiple implementations
later.

So I decided instead to use this data to implement a "what state is
this point in?"
function. This boils down to reading in the state border polygons and
testing points
using contains(polygon,point).

One issue that I noted while reading in the polygons is that the
provided polygon_data
type is immutable: to read from a file, I need either an exotic
iterator that can be
passed to its constructor, or a temporary. I'm unsure why polygon_data
can't be more
like a mutable std::container so that I can simply read points from a
file and
push_back() in a loop. Trying to use a std::vector<point_data>
required more traits
specialisation that I expected; can't this be pre-defined?

** The polygon_data type should be mutable (i.e. support things like
push_back()), or a
mutable version should be provided, or std::vector/list<point_data>
should work with
minimal traits specialisation.

I also found that polygon_data is specialised by the coordinate type,
not the point
type, so anyone using their own point type will have to provide their
own polygon type.
Is there some reason why I can't have polygon_data<my_point>? Again,
making it easier
to use std::container<my_point> would help.

I also found little mention of winding direction in the documentation.
I haven't
checked whether the data I have winds consistently; what does
unknown_winding actually
do?

As I guessed, contains(polygon,point) is very slow if done naively: the library's
polygon concept (and the provided default implementation) have no way
to determine
whether a point lies within a polygon in better than O(N) time.
Testing first with the
bounding box makes it O(1) in the common case. So I tried to write a
polygon type that
would do this, something like this (but not exactly this!):

   struct my_polygon: polygon_data {
     rectangle bbox;
     template <typename ITER>
     my_polygon(ITER begin, ITER end):
       polygon_data(begin,end),
       bbox(extents(*this))
     {}
   };

   bool contains(const my_polygon& poly, point_t pt) {
     return contains(poly.bbox,pt) && contains(poly,pt);
   }

Hmm, well that looks OK until the very last "contains"... no doubt
someone will
immediately spot the "right" way to do this. I ended up making
contains() a member of
my_polygon, and this worked reasonably well. Note that the extents()
function does not
work as written above: it takes a reference to a rectangle as an out parameter.
center() does something similar. This seems wrong to me; returning a
point or
rectangle would be more conventional I think.

** extents() and center() should return their results, rather than
using an output
reference.

An important question is what this function should do when given a
coordinate that lies
on the boundary between two (or more) states. One can argue for
various different
behaviours. My preference would be to never return "no state" and to
be deterministic,
but otherwise I don't care. The contains() function has a parameter "consider_touch"
that makes it possible to implement different policies; this seems
sufficient in most
cases, though I'm unsure how you would consider the left and bottom
included and the
right and top excluded in a 90-degree shape (which might be needed for
a GUI).

I have a fixed point type that I use for GPS coordinates (32 bits is
good for lat/lng
GPS positions, but 24 bits isn't) and using it with this library worked
well. The
Coordinate Concept page doesn't say much about the type requirements
("expected to be
integral") and spelling out in more detail what is needed would be
useful. In practice
I must have already implemented everything that it needed.

I would have liked to pursue this example further and see just how fast
the "which
state?" function can be made. For example, simplified versions of the
state borders
could be stored for fast lookup for points not near the borders. But I
ran out of
time. If anyone would like to experiment with this, the data can be
found at
http://chezphil.org/tmp/states.tgz .

Other general notes
-------------------

Operator Overloading : I am not a huge fan of "gratuitous" operator
overloading. In
this case, I find |= for union acceptable, particularly since I think I
can disable
this by not using the boost::polygon::operators namespace. I would
prefer to avoid
the duplicate operators (i.e. + == |).

However, I can't see any way to perform these boolean operations other
than using the
operators, and I think this is an ommission. If I were writing code
that I expected
someone else unfamiliar with the library to understand I would like the important
calls to be conspicuous.

** The library should provide functions to perform the boolean
operations, as well as
operators, for the benefit of those who want to make their code more verbose.

I dislike the use of operators with integers for the grow/shrink
operations. My
concern is that this meaning is non-obvious, and since these operators
are also
defined for boolean operations, there is potential for error:

   polygon_set a, b, i;
   ...
   for (int i = 0; i<10; ++i) {
     ...
     a -= b+i; // oops, forgot i is now an int
   }

Isotropic Style
---------------

I recall Luke describing his isotropic style on the list a long time
ago, and the
documentation would benefit from an explanation along those lines. One
"FAQ" that it
would need to address is the question of the performance of a run-time
selection of X
vs. Y compared to a compile-time selection in more conventional code.

I'm unsure if the use of caps for e.g. HORIZONTAL and VERTICAL enum
members is Boost
style. They look like macros to me.

I'm not very happy with the use of compass directions as direction
labels, since I
have code in which these directions are definitely not what the axes
actually mean.
Other labels including LEFT and RIGHT would have the same problem in
other contexts.
GUI APIs are inconsistent about whether y increases up or down the
screen, so terms
like "top left" are also problematic. I think about the only safe
terms are
"increasing X axis" etc. I tend to use x0y0 ... x1y1 for corners.

Documentation
-------------

I find the documentation satisfactory, though it could benefit from
some style
improvements (e.g. the font for the example code).

I suggest that an introductory tutorial should be added. This should
fully explain
everything that a new user who has no legacy code needs to know (i.e.
it ignores the
traits and uses the provided _data types.) Then, a second tutorial
(more like the
current material) could explain how users with their own types can use
them with the
library.

Answers to basic questions like "is it header-only?" and "what other
Boost libraries
does it depend on?" should also be added somewhere prominent in the introduction.

That concludes my practical examination of the library.

We then have the question of rival geometry libraries to consider.

Barend has presented a few previews of his library and I have looked at
these, though
not in much detail. My feeling was that Barend had a long way to go
before he would
have something useful, and that even then he may never produce
something that I would
actually be able to use. For example, he has decided to adopt the
conventions of the
OGC; this is not entirely unreasonable, but it means that semantics of
things like
whether border points are inside or outside a polygon are
non-negotiable. Barend has
also recently reminded us of the spatial indexes GSOC project and says
that it is now
included in his library, despite it being the worse code I have ever
seen presented to
Boost.

Despite all that, Barend's recent comments suggest that he has made significant
progress and that he may have something useful to show us in a few weeks.

Barend has also raised questions about the worse-case performance of Luke's
line intersection algorithm, and it seems that Luke accepts that it is
not optimal.
Achieving the best possible algorithmic complexity is something that I
would consider
very important or essential for a Boost library. At the very least,
Luke needs to
document the complexity of his current algorithm and explain why he
cannot do any
better. The views of experts should be sought if this cannot be
resolved by the
review manager.

In view of all this, I suggest that this library should be rejected for
now. This
will tell Barend that he still has an opportunity to present his
library for review,
and that it will be considered on a level playing field. If Barend's
library is
reviewed and found to be more complete, more performant and at least as
usable as this
library, then it should be accepted. On the other hand, if Barend's
library is found
to be deficient in some way (or is not submitted for review), then Luke
will have an
opportunity to resubmit an updated version of this library, which I
anticipate should
be accepted.

Regards, Phil.


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk