[geos-devel] [Fwd: Formal Review: Boost.Polygon starts today August 24, 2009]

Stephen Woodbridge woodbri at swoodbridge.com
Tue Aug 25 14:23:00 EDT 2009


Thank you for looking at this. I am not involved, just thought it looked 
interesting. I did read through some of their docs and examples and just 
was not sure what to think about it. Having worked on some large scale 
integrated circuit software in the distant past, this may be more 
oriented to this arena which would explain the 45/90 degree stuff I noticed.

Anyway maybe something to keep an eye on as it evolves or something that 
you might want to comment on in their review process.

Best regards,

Martin Davis wrote:
> 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

More information about the geos-devel mailing list