[geos-devel] [Fwd: [Boost-users] [boost] Formal
Review: Boost.Polygon starts today August 24, 2009]
Hartmut Kaiser
hartmut.kaiser at gmail.com
Tue Aug 25 18:00:41 EDT 2009
> Interesting and ambitious project.
>
> With the caveat that I've really only skimmed the documentation and
> have
> not done any actual experimentation with the library, here's my
> perspective on it's applicability to PostGIS & GEOS:
>
> - The API seems likely to be quite complex, since it dives headfirst
> into the C++ template/traits pool. This seems to be de rigeur for any
> serious C++ library these days, but to my mind this is orthogonal to
> the
> requirements of PostGIS and indeed a lot of geometry processing.
> - The library is apparently concerned only with polygon operations,
> whereas GEOS and PostGIS provide the full SFS geometry model
> - As I read it the library as it ships uses 32-bit integers for
> computation. In my experience this is not enough precision for general
> geospatial processing. They do say that it can be configured/enhanced
> to allow 64-bit processing (but not floating-point, it looks like). It
> would be work to develop this and test it, however
> - It doesn't look like predicates are provided
> - They don't do any performance comparisons against GEOS. That's too
> bad - it would be nice to see how it stacks up.
> - They seem to be quite concerned with providing code for handling
> rectilinear and "45-degree" polygons. It looks like some operations
> might be restricted to these kinds of geometries (eg buffering?). Not
> sure what their use case is, but this doesn't occur that often in
> geospatial data.
>
> The coverage handling aspect could be interesting, but I don't see much
> reference to it in the documentation. In any case, the really hard
> part
> about coverage processing in a database is scaling to process datasets
> which exceed main memory. Some recent experimentation has convinced me
> that sweep-line is a good paradigm for tackling this problem, but this
> still requires an algorithms which is explicitly designed to process
> out
> of external memory.
>
> IMO the things that matter most to the PostGIS/GEOS community are
> peformance, robustness, and ease of use. It would be really nice to
> see
> some performance comparisons between Boost.Polygon, GEOS and JTS on
> large geometries and datasets. If BP proved to be much faster and/or
> more robust, then it might indicate that they have chosen a better
> approach to the core problem of evaluating polygon overlays. Even
> then,
> however, there is the question of the complexity of using two large
> APIs together. There would be some serious work involved in
> providing a higher-level facade API to enable using selected components
> of both APIs in a transparent fashion.
FWIW, there will be a second Boost library review soon: GGL (Generic
Geometry Library, here: http://trac.osgeo.org/ggl/), which is yet another
project currently hosted by OSGEO. GGL is much larger than BP, more similar
to GEOS (full SFS geometry, etc.). The comparing measurement I saw tend to
show GGL being even than everything else, for instance:
100 points per ellipse, with area check:
-> geos: resulting area: 69.68616316800, time: 13.641 seconds
-> ggl: resulting area: 69.68616316800, time: 1.156 seconds
-> gpc: resulting area: 69.68616316800, time: 9.297 seconds
-> polygon: resulting area: 69.68616202400, time: 108.563 seconds
-> terralib: resulting area: 69.68616316800, time: 4.672 seconds
These results are colored by the check of the area. Checking without gives:
100 points per ellipse:
-> geos time: 13.437 seconds
-> ggl time: 1.140 seconds
-> gpc time: 9.047 seconds
-> polygon time: 38.688 seconds
-> terralib time: 4.609 seconds
Here is the description of the measurements as posted by Barend on the GGL
list:
<quote>Testing is done with the (freely available) US Counties shapefile.
Each polygon (without holes because not every library can handle them) is
intersected with ellipses, with the axes 110% of each polygons bounding box.
We can vary the number of points in the ellipse to test scalability. All
tests are done using GCC -O3, and using double coordinates (GTL mapped to
integer, the mapping is done outside the measurements).</quote>
And another set of results:
10 points per ellipse:
-> geos time: 14.063 seconds
-> ggl time: 1.062 seconds
-> gpc time: 8.484 seconds
-> polygon time: 37.469 seconds
-> terralib time: 5.281 seconds
1000 points per ellipse:
-> geos time: 14.703 seconds
-> ggl time: 0.953 seconds
-> gpc time: 14.000 seconds
-> polygon time: 59.171 seconds
-> terralib time: 7.781 seconds
10000 points per ellipse:
-> geos time: 30.016 seconds
-> ggl time: 3.671 seconds
-> gpc time: 74.641 seconds
-> polygon time:259.016 seconds
-> terralib time:44.750 seconds
Regards Hartmut
> HTH - Martin
>
> Stephen Woodbridge wrote:
> > Hi Devs,
> >
> > I saw this this morning and thought it might be of interest to the
> > postGIS and GEOS teams. What caught my eye was the connection to
> > Graphs which implies to me topology in this case. This might give us
> > the tools needed to handle polygon coverages and do things like
> > simplify a coverage while maintaining topology of the edges and and
> > common edges between topologically connected polygons. I'm only
> > guessing al this from the write up below but it sounds promising.
> >
> > Maybe someone with more technical guts knowledge can review this for
> > its potential value to GEOS and/or PostGIS.
> >
> > ATB,
> > -Steve
> >
> > -------- Original Message --------
> > Subject: [Boost-users] [boost] Formal Review: Boost.Polygon starts
> > today August 24, 2009
> > Resent-Date: Tue, 25 Aug 2009 07:43:06 -0400
> > Resent-From: Ronald Garcia <garcia at osl.iu.edu>
> > Resent-To: boost-users at lists.boost.org, boost-
> announce at lists.boost.org
> > Date: Mon, 24 Aug 2009 17:36:56 -0300
> > From: Fernando Cacciola <fernando.cacciola at gmail.com>
> > Reply-To: boost-users at lists.boost.org
> > To: boost at lists.boost.org
> >
> > Dear Developers,
> >
> > The formal review of the Boost.Polygon library by Lucanus Simonson
> > starts today, August 24, 2009 and will finish September 2, 2009.
> >
> > I really hope to see your vote and your participation in the
> > discussions on
> > the Boost mailing lists!
> >
> > ---------------------------------------------------
> >
> > About the library:
> >
> > The boost polygon library provides algorithms focused on manipulating
> > planar
> > polygon geometry data. Specific algorithms provided are the polygon
> set
> > operations (intersection, union, difference, disjoint-union) and
> related
> > algorithms such as polygon connectivity graph extraction, offsetting
> and
> > map-overlay. These so-called Boolean algorithms are of significant
> > interest in
> > GIS (Geospatial Information Systems), VLSI CAD as well al other
> fields
> > of CAD,
> > and many more application areas, and providing them is the primary
> > focus of this
> > library. The polygon library is not intended to cover all of
> > computational
> > geometry in its scope, and provides a set of capabilities for working
> > with
> > coordinates, points, intervals and rectangles that are needed to
> support
> > implementing and interacting with polygon data structures and
> > algorithms.
> > Specifically, 3d and non-Cartesian/non-planar geometry is outside of
> > the scope
> > of the polygon library
> >
> > The design philosophy behind the polygon library was to create an API
> > for
> > invoking the library algorithms it provides on user geometry data
> > types that is
> > maximally intuitive, minimally error-prone and easy to integrate into
> > pre-existing applications. C++-concepts based template meta-
> programming
> > combined with generic operator overloading meets these design goals
> > without
> > sacrificing the runtime or memory efficiency of the underlying
> > algorithms. This
> > API makes the following code snippet that operates on non-library
> > geometry types
> > possible:
> >
> > void foo(list<CPolygon>& result, const list<CPolygon>& a,
> > const list<CPolygon>& b, int deflateValue) {
> > CBoundingBox domainExtent;
> > using namespace boost::polygon::operators;
> > boost::polygon::extents(domainExtent, a);
> > result += (b & domainExtent) ^ (a - deflateValue);
> > }
> >
> > The source is available at
> >
> > http://svn.boost.org/svn/boost/sandbox/gtl/boost/polygon/
> >
> > And the documentation is at
> >
> > http://svn.boost.org/svn/boost/sandbox/gtl/doc/index.htm
> >
> > ---------------------------------------------------
> >
> > Please always state in your review, whether you think the library
> > should be
> > accepted as a Boost library!
> >
> > Additionally please consider giving feedback on the following general
> > topics:
> >
> > - What is your evaluation of the design?
> > - What is your evaluation of the implementation?
> > - What is your evaluation of the documentation?
> > - What is your evaluation of the potential usefulness of the library?
> > - Did you try to use the library? With what compiler? Did you have
> any
> > problems?
> > - How much effort did you put into your evaluation? A glance? A quick
> > reading? In-depth study?
> > - Are you knowledgeable about the problem domain?
> >
> >
> > Best Regards
> >
> > Fernando Cacciola
> > Review Manager
> >
> >
> >
> > _______________________________________________
> > Unsubscribe & other changes:
> > http://lists.boost.org/mailman/listinfo.cgi/boost
> > _______________________________________________
> > Boost-users mailing list
> > Boost-users at lists.boost.org
> > http://lists.boost.org/mailman/listinfo.cgi/boost-users
> > _______________________________________________
> > geos-devel mailing list
> > geos-devel at lists.osgeo.org
> > http://lists.osgeo.org/mailman/listinfo/geos-devel
> >
>
> --
> Martin Davis
> Senior Technical Architect
> Refractions Research, Inc.
> (250) 383-3022
>
> _______________________________________________
> geos-devel mailing list
> geos-devel at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/geos-devel
More information about the geos-devel
mailing list