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

Martin Davis mbdavis at refractions.net
Tue Aug 25 16:12:54 EDT 2009

Good point about the possible connection between LSI and the 45/90 
degree stuff.  Given that both authors work for Intel that seems even 
more likely...  There's probably some significant optimizations possible 
if you have 45/90 degrees as a constraint on the input.


Stephen Woodbridge wrote:
> Martin,
> 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,
>   -Steve
> 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
> _______________________________________________
> 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