[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.
Martin
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