Re: [boost] [geometry] [polygon] What's the relationship?

Subject: Re: [boost] [geometry] [polygon] What's the relationship?
From: Luke Simonson (simoluk_at_[hidden])
Date: 2012-09-16 17:02:28

> Could someone please explain the relationship, if any, betweeen these
> two libraries?  They seem to cover similar domains.  Do they
> interoperate?  Is one better than the other for certain kinds of
> problems?

This was discussed quite a lot during both reviews.  The discussion
became quite heated at times and I don't want to fan those flames
again.  I've been participating in the Geometry mailing list and the
two libraries have been peacefully coexisting.

I would say that the main difference between the two is a different
philosophy towards numerical robustness.  Polygon achieves 100%
numerical robustess by requiring integer coordinates of the input
geometry and applying higher precision arithmetic if necessary and
snap rounding.  Boost.Geometry generally assumes floating point input
coordinates, though there has been quite a few bug fixes delivered
recently by Geometry to support integer coordinates.  Geometry ignores
the rounding of both integer and floating point coordinates, which
means that it is possible for it to produce an output that it cannot
consume as an input because it does not ensure as a postcondition
something that it requires as a precondition.  Rounding with integer
coordinates is a much bigger issue than with floating point because
the error introduced tends to be relatively larger.

Initially the Geometry requirements for models of its concepts were
not compatible with the data types defined in Polygon, but I
understand that to have been changed.  The two libraries should
interoperate syntactically if the appropriate adaptors are provides,
however, the difference between requirements on the coordinate data
type is more fundamental.  What I've observed about the usage of each
library is the users generally want one geometry library or the other
but don't want both.  Users tend to pick the library that best suites
their application requirements.  For example, GIS users clearly prefer
Geometry while EDA users tend to prefer Polygon.  So far no one has
seemed particularly confused and I haven't heard any complaints.

After Geometry was accepted it was suggested that work on Polygon
should cease and the two libraries merged eventually.  That isn't
really feasible.  The existing users of the Polygon API would not want
to port their code to the Geometry API and the Geometry algorithms
would not satisfy their requirements.

We are about to release the Voronoi diagram extension to Polygon as
well as a new line segment_concept.  Voronoi was designed to allow the
core algorithm to be independent of the rest of the library, both to
satisfy Google users, who restrict template metaprograming and to make
it easily compatible with Boost.Geometry, though the integer input
requirement is still there if we are to ensure bounded numerical
error.  I'm currently working on straight skeleton, which will be
coupled both to Voronoi diagram internals for bounded error arithmetic
and to the concepts based Polygon interface for line segments.  It
will also require integer input coordinates.

The bottom line is that because Polygon algorithms require integer
input coordinates they are not suitable for inclusion in Geometry
because it would be very confusing that some algorithms can only be
called with integer geometry types while others should only be called
with floating point types in the same library.  Polygon could benefit
from the spatial query tree data structure being developed as a part
of Geometry, but I don't think most current users would welcome cross
dependencies being formed between the two libraries.

My straight skeleton implementation is coming along well.  Both vornoi
diagram and straight skeleton are very difficult to make numerically
robust and I don't expect Geometry to support them with floating point
coordinates any time soon.  While the two libraries do have
substantial overlap, they differ in philosophy and are growing in
different directions.

> Was Boost.Polygon once called the Geometry Template Library, as
> suggested by the BoostCon 2009 slides?  Boy, that's confusing.

Yes, people felt the name was too general so I changed it to Polygon.
Later the name of Barend's library was changed to Geometry.

> Lastly, could we get these libraries' documentation to mention one
> another and explain the information I'm asking for?

I'm reluctant to make statement's about Geometry in my documentation
that the Geometry authors might take issue with or that might fall out
of date as changes to Geometry are made.  While the status is peaceful
coexistence and (I believe) mutual respect, we still disagree on
technical matters and I don't want to raise tensions.

We will be updating the documentation for the release of Voronoi.  I'd
be happy to include a statement that summarizes the answers to your
questions that we can all agree on.

Regards,
Luke