[geos-devel] [Fwd: [Boost-users] [boost] Formal Review:
Boost.Polygon starts today August 24, 2009]
Martin Davis
mbdavis at refractions.net
Tue Aug 25 13:04:08 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.
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
More information about the geos-devel
mailing list