[Fwd: [Boost-users] [boost] Formal Review: Boost.Polygon starts today August 24, 2009]
|
|
| 1 2 |
Stephen Woodbridge
|
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 <[hidden email]> Resent-To: [hidden email], [hidden email] Date: Mon, 24 Aug 2009 17:36:56 -0300 From: Fernando Cacciola <[hidden email]> Reply-To: [hidden email] To: [hidden email] 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 [hidden email] http://lists.boost.org/mailman/listinfo.cgi/boost-users _______________________________________________ geos-devel mailing list [hidden email] http://lists.osgeo.org/mailman/listinfo/geos-devel |
||||||||||||||||
Martin Davis
|
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 <[hidden email]> > Resent-To: [hidden email], [hidden email] > Date: Mon, 24 Aug 2009 17:36:56 -0300 > From: Fernando Cacciola <[hidden email]> > Reply-To: [hidden email] > To: [hidden email] > > 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 > [hidden email] > http://lists.boost.org/mailman/listinfo.cgi/boost-users > _______________________________________________ > geos-devel mailing list > [hidden email] > http://lists.osgeo.org/mailman/listinfo/geos-devel > -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 _______________________________________________ geos-devel mailing list [hidden email] http://lists.osgeo.org/mailman/listinfo/geos-devel |
||||||||||||||||
|
Stephen Woodbridge
|
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 <[hidden email]> >> Resent-To: [hidden email], [hidden email] >> Date: Mon, 24 Aug 2009 17:36:56 -0300 >> From: Fernando Cacciola <[hidden email]> >> Reply-To: [hidden email] >> To: [hidden email] >> >> 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 >> [hidden email] >> http://lists.boost.org/mailman/listinfo.cgi/boost-users >> _______________________________________________ >> geos-devel mailing list >> [hidden email] >> http://lists.osgeo.org/mailman/listinfo/geos-devel >> > _______________________________________________ geos-devel mailing list [hidden email] http://lists.osgeo.org/mailman/listinfo/geos-devel |
||||||||||||||||
|
Martin Davis
|
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 <[hidden email]> >>> Resent-To: [hidden email], [hidden email] >>> Date: Mon, 24 Aug 2009 17:36:56 -0300 >>> From: Fernando Cacciola <[hidden email]> >>> Reply-To: [hidden email] >>> To: [hidden email] >>> >>> 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 >>> [hidden email] >>> http://lists.boost.org/mailman/listinfo.cgi/boost-users >>> _______________________________________________ >>> geos-devel mailing list >>> [hidden email] >>> http://lists.osgeo.org/mailman/listinfo/geos-devel >>> >> > > _______________________________________________ > geos-devel mailing list > [hidden email] > http://lists.osgeo.org/mailman/listinfo/geos-devel > -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 _______________________________________________ geos-devel mailing list [hidden email] http://lists.osgeo.org/mailman/listinfo/geos-devel |
||||||||||||||||
Hartmut Kaiser
|
In reply to this post
by Martin Davis
> 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 <[hidden email]> > > Resent-To: [hidden email], boost- > [hidden email] > > Date: Mon, 24 Aug 2009 17:36:56 -0300 > > From: Fernando Cacciola <[hidden email]> > > Reply-To: [hidden email] > > To: [hidden email] > > > > 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 > > [hidden email] > > http://lists.boost.org/mailman/listinfo.cgi/boost-users > > _______________________________________________ > > geos-devel mailing list > > [hidden email] > > http://lists.osgeo.org/mailman/listinfo/geos-devel > > > > -- > Martin Davis > Senior Technical Architect > Refractions Research, Inc. > (250) 383-3022 > > _______________________________________________ > geos-devel mailing list > [hidden email] > http://lists.osgeo.org/mailman/listinfo/geos-devel _______________________________________________ geos-devel mailing list [hidden email] http://lists.osgeo.org/mailman/listinfo/geos-devel |
||||||||||||||||
Barend Gehrels
|
Hartmut Kaiser wrote: > 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 list before, but were intended to. Since yesterday they are in the GGL Wiki on the performance page: http://trac.osgeo.org/ggl/wiki/Performance Regards, Barend Gehrels _______________________________________________ geos-devel mailing list [hidden email] http://lists.osgeo.org/mailman/listinfo/geos-devel |
||||||||||||||||
|
Martin Davis
|
In reply to this post
by Hartmut Kaiser
Hmmm... GEOS comes off rather badly compared to GGL. Is that because of
memory access issues? Or perhaps the fact that less code is inlined? Hartmut Kaiser wrote: > 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 > > -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 _______________________________________________ geos-devel mailing list [hidden email] http://lists.osgeo.org/mailman/listinfo/geos-devel |
||||||||||||||||
Mateusz Loskot
|
Martin Davis wrote:
> Hmmm... GEOS comes off rather badly compared to GGL. Is that because > of memory access issues? Or perhaps the fact that less code is > inlined? It's hard to judge, but I'm quite sure inlining is only a small and minor optimisation available. GEOS and GGL follow completely different programming paradigms. GGL is strongly based on static polymorphism resolved and calculated in compile-time. This increases changes that compilers will apply finest possible optimisations. Best regards, -- Mateusz Loskot, http://mateusz.loskot.net Charter Member of OSGeo, http://osgeo.org _______________________________________________ geos-devel mailing list [hidden email] http://lists.osgeo.org/mailman/listinfo/geos-devel |
||||||||||||||||
|
Martin Davis
|
Ok, I can see that. So in other words, GEOS uses a dynamic coordinate
access paradigm, which gives flexibility to access different data structures, but can't be optimized by the compiler? Is this the reason for the performance difference for *all* the other libraries which beat it in peformance? Or maybe some of them *don't* provide the dynamic data structure wrapper, and hence also can be optimized by the compiler (but thus they are less adaptable for use with external data structures). It would be nice to have this confirmed with some detailed code inspection and/or profiling. I presume it would be a big job to convert GEOS to a template-based paradigm? It's somewhat annoying that the problem of efficient memory access and compiler optimization is quite orthogonal to the actual geometric algorithms, and yet it seems difficult to express the algorithms in a sufficiently abstract way to allow optimizations to take place. Perhaps what we need is a meta-language, in which the raw algorithms could be expressed and then compiled into whatever codebase was most efficient to execute. Or - C++ seems incredibly powerful with it's templating and operator overloading - would it be possible to define a DSL using C++ constructs which would allow GEOS to be compiled more efficiently? Martin Mateusz Loskot wrote: > Martin Davis wrote: > >> Hmmm... GEOS comes off rather badly compared to GGL. Is that because >> of memory access issues? Or perhaps the fact that less code is >> inlined? >> > > It's hard to judge, but I'm quite sure inlining is only a small and > minor optimisation available. > GEOS and GGL follow completely different programming paradigms. > GGL is strongly based on static polymorphism resolved and calculated in > compile-time. This increases changes that compilers will apply finest > possible optimisations. > > Best regards, > -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 _______________________________________________ geos-devel mailing list [hidden email] http://lists.osgeo.org/mailman/listinfo/geos-devel |
||||||||||||||||
|
Hartmut Kaiser
|
In reply to this post
by Mateusz Loskot
> Martin Davis wrote:
> > Hmmm... GEOS comes off rather badly compared to GGL. Is that because > > of memory access issues? Or perhaps the fact that less code is > > inlined? > > It's hard to judge, but I'm quite sure inlining is only a small and > minor optimisation available. > GEOS and GGL follow completely different programming paradigms. > GGL is strongly based on static polymorphism resolved and calculated in > compile-time. This increases changes that compilers will apply finest > possible optimisations. >From what I've seen in GEOS and GGL, GEOS is mostly relying on dynamic memory allocation, where GGL tries to avoid that. GEOS relies on runtime polymorphism, where GGL relies on compile time (static polymorphism). GEOS is built using Java-ish constructs, where GGL is build the C++ way... All of this influences the runtime behavior, but there might be more reasons. Please note, I didn't do any thorough analysis, all of this is just guessing. Regards Hartmut _______________________________________________ geos-devel mailing list [hidden email] http://lists.osgeo.org/mailman/listinfo/geos-devel |
||||||||||||||||
|
Barend Gehrels
|
Some javascript/style in this post has been disabled (why?)
Hartmut Kaiser wrote: I do not know GEOS very well but I think that Hartmut is right here. GGL uses the std-library for storage of coordinates. If I'm right, GEOS calls a memory allocation for every point (of a polygon). And indeed GGL uses static polymorphism. The consequence of this is also that there is no polygon.area() function, but an area(polygon) function, taking any polygon which fulfills the polygon concept. Regards, Barend _______________________________________________ geos-devel mailing list [hidden email] http://lists.osgeo.org/mailman/listinfo/geos-devel |
||||||||||||||||
|
Barend Gehrels
|
In reply to this post
by Martin Davis
Martin Davis wrote: > Ok, I can see that. So in other words, GEOS uses a dynamic coordinate > access paradigm, which gives flexibility to access different data > structures, but can't be optimized by the compiler? It is not only the compiler. Dynamic memory allocations are relatively slow. Allocating 1000 times a point is slower than allocating once 1000 points. > > Is this the reason for the performance difference for *all* the other > libraries which beat it in peformance? Or maybe some of them *don't* > provide the dynamic data structure wrapper, and hence also can be > optimized by the compiler (but thus they are less adaptable for use > with external data structures). I don't know this for sure but I think most allocate for the whole polygon or linestring at once. GPC is e.g. C, not C++. > > I presume it would be a big job to convert GEOS to a template-based > paradigm? Probably. What would be possible and feasable is adapting GEOS's datastructures (polygon) to GGL's concepts and then call e.g. GGL's intersection. It would at least be a nice experiment. You still have the dynamic memory then, but you can see which part is the algorithm and which part is the memory access > It's somewhat annoying that the problem of efficient memory access and > compiler optimization is quite orthogonal to the actual geometric > algorithms, and yet it seems difficult to express the algorithms in a > sufficiently abstract way to allow optimizations to take place. I don't see this. Using the std-library, both access to a vector and (temporary) storage using a vector or deque are usually quite fast. Regards, Barend _______________________________________________ geos-devel mailing list [hidden email] http://lists.osgeo.org/mailman/listinfo/geos-devel |
||||||||||||||||
|
Martin Davis
|
One thing to make clear - GEOS does not alway require allocations to be
done pointwise. The CoordinateSequence interface and various subclasses provide the option of allocating all storage for a list of points in a single allocation. I would certainly be curious to see how the algorithmic component of GEOS compares to GGL (or any other library). The JTS/GEOS predicate and overlay algorithms were developed with the primary goal being first generality and then performance. So no doubt there's better ways of doing things. In the GEOS algorithms at least I don't see any way of avoiding dynamic allocation, since there's no way to predict a priori how many line segment intersections will be found, or how what the structure of the output geometry is. Does GGL avoid this problem in some way? Barend Gehrels wrote: > > > Martin Davis wrote: >> Ok, I can see that. So in other words, GEOS uses a dynamic >> coordinate access paradigm, which gives flexibility to access >> different data structures, but can't be optimized by the compiler? > It is not only the compiler. Dynamic memory allocations are relatively > slow. Allocating 1000 times a point is slower than allocating once > 1000 points. >> >> Is this the reason for the performance difference for *all* the other >> libraries which beat it in peformance? Or maybe some of them *don't* >> provide the dynamic data structure wrapper, and hence also can be >> optimized by the compiler (but thus they are less adaptable for use >> with external data structures). > I don't know this for sure but I think most allocate for the whole > polygon or linestring at once. GPC is e.g. C, not C++. >> >> I presume it would be a big job to convert GEOS to a template-based >> paradigm? > Probably. What would be possible and feasable is adapting GEOS's > datastructures (polygon) to GGL's concepts and then call e.g. GGL's > intersection. It would at least be a nice experiment. You still have > the dynamic memory then, but you can see which part is the algorithm > and which part is the memory access > >> It's somewhat annoying that the problem of efficient memory access >> and compiler optimization is quite orthogonal to the actual geometric >> algorithms, and yet it seems difficult to express the algorithms in a >> sufficiently abstract way to allow optimizations to take place. > I don't see this. Using the std-library, both access to a vector and > (temporary) storage using a vector or deque are usually quite fast. > > Regards, Barend > > > > _______________________________________________ > geos-devel mailing list > [hidden email] > http://lists.osgeo.org/mailman/listinfo/geos-devel > -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 _______________________________________________ geos-devel mailing list [hidden email] http://lists.osgeo.org/mailman/listinfo/geos-devel |
||||||||||||||||
|
Barend Gehrels
|
Martin Davis wrote: > One thing to make clear - GEOS does not alway require allocations to > be done pointwise. The CoordinateSequence interface and various > subclasses provide the option of allocating all storage for a list of > points in a single allocation. OK, sorry for my misunderstanding. I just debugged the Geos area routine, what could then be the reason that it is relatively slow? It might be that it is accessed as a vector, indeed, but not as an iterator, so getting points using "return (*vect)[pos]" is not efficient as it could be using iterators. Besides that it is probably no problem to make the getAt function inline. > > I would certainly be curious to see how the algorithmic component of > GEOS compares to GGL (or any other library). The GGL overlay algorithm will be described in a paper. It is a modern variant of the classic Weiler-Atherton algorithm. > The JTS/GEOS predicate and overlay algorithms were developed with the > primary goal being first generality and then performance. So no doubt > there's better ways of doing things. Actually the GGL algorithm is generic as well, in the sense that it is able to overlay polygons and polygon/rectangle (clipping) with the same algorithm. The only difference is getting the intersections, which is more efficient for the rectangle case. Also intersection/union are implemented in one algorithm. > In the GEOS algorithms at least I don't see any way of avoiding > dynamic allocation, since there's no way to predict a priori how many > line segment intersections will be found, or how what the structure of > the output geometry is. Does GGL avoid this problem in some way? Yes. It will be described, but in short: we don't insert the found intersection points into the polygons (as done in many algorithms, but I don't know about GEOS) but register them separately. That saves a copy, plus many inserts (shifts). However, it requires somewhat more bookkeeping. So intersected polygons are assembled in the end, in between there are no large pieces of memory allocation. By the way, everyone is of course invited to check the geos comparison source files, it might be that I've done something not in the most efficient way. It is the intention to have it as efficient as possible, of course. Sources are at boost SVN now: http://svn.boost.org/svn/boost/sandbox/ggl/other/comparisons/ Regards, Barend _______________________________________________ geos-devel mailing list [hidden email] http://lists.osgeo.org/mailman/listinfo/geos-devel |
||||||||||||||||
strk
|
On Wed, Sep 02, 2009 at 11:39:32AM +0200, Barend Gehrels wrote:
> I just debugged the Geos area routine, what could then be the reason > that it is relatively slow? It might be that it is accessed as a vector, > indeed, but not as an iterator, so getting points using "return > (*vect)[pos]" is not efficient as it could be using iterators. Besides > that it is probably no problem to make the getAt function inline. getAt is a virtual function, can't be inlined. Templates would make it a lot better, but far away from 1:1 mapping with Java. Beside, how do you handle memory management in GGL ? --strk; Free GIS & Flash consultant/developer () ASCII Ribbon Campaign http://foo.keybit.net/~strk/services.html /\ Keep it simple! _______________________________________________ geos-devel mailing list [hidden email] http://lists.osgeo.org/mailman/listinfo/geos-devel |
||||||||||||||||
|
Barend Gehrels
|
Some javascript/style in this post has been disabled (why?)
Right, I debugged in CoordinateArraySequence, where it is not denoted virtual (the overloaded version is...), but I now saw that its parent indeed is virtual. A (probably) working way to have less virtual calls (for area) then would be changing this: double bx=ring->getAt(i).x; double by=ring->getAt(i).y; double cx=ring->getAt(i+1).x; double cy=ring->getAt(i+1).y; to this: Coordinate const& c = ring->getAt(i + 1 ); double cx = c.x, cy = c.y; and have a previous_coordinate (b) for the getAt(i). Would save 3 virtual calls + 3 times non-iterator-based vector access... I didn't try it. This just in search of what would be the bottle neck, because the area algorithm itself is extremely simple. Sure, though Java also have templates nowTemplates would make it a lot better, but far away from 1:1 mapping with Java. 1) Using the std:: library. Where it is an optional template parameter, so you can have polygon<point> but also polygon<point, std::deque> for if you decide that you want a deque instead of a vectorBeside, how do you handle memory management in GGL ? 2) Using concepts, actually a polygon or linestring can be anything as long as it fullfiles the concept. So having an iterator (for linestring that is enough), having traits te denote exterior/interior ring handling. In this way our library does not even now what is below the surface, it just uses it. Regards, Barend _______________________________________________ geos-devel mailing list [hidden email] http://lists.osgeo.org/mailman/listinfo/geos-devel |
||||||||||||||||
|
Mateusz Loskot
|
Barend Gehrels wrote:
> >>> I just debugged the Geos area routine, what could then be the reason >>> that it is relatively slow? It might be that it is accessed as a >>> vector, indeed, but not as an iterator, so getting points using >>> "return (*vect)[pos]" is not efficient as it could be using >>> iterators. Besides that it is probably no problem to make the getAt >>> function inline. >>> >> >> getAt is a virtual function, can't be inlined. >> > Right, I debugged in CoordinateArraySequence, where it is not denoted > virtual (the overloaded version is...), but I now saw that its parent > indeed is virtual. > > A (probably) working way to have less virtual calls (for area) then > would be changing this: > double bx=ring->getAt(i).x; > double by=ring->getAt(i).y; > double cx=ring->getAt(i+1).x; > double cy=ring->getAt(i+1).y; It would be not a bad idea to help compiler to optimise as much as possible: double const cx = ... Most people think it's too trivial to influence generated code, but it may really help. > to this: > Coordinate const& c = ring->getAt(i + 1 ); > double cx = c.x, cy = c.y; Best option possible. > and have a previous_coordinate (b) for the getAt(i). Would save 3 > virtual calls + 3 times non-iterator-based vector access... I didn't try > it. Anyway, all the small things that "seem" trivial, make a big difference in fact. >> Templates would make it a lot better, but far away from 1:1 mapping >> with Java. >> > Sure, though Java also have templates now > >> Beside, how do you handle memory management in GGL ? >> > 1) Using the std:: library. Where it is an optional template parameter, > so you can have polygon<point> but also polygon<point, std::deque> for > if you decide that you want a deque instead of a vector Plus, you can use your own containers or you can use your own allocators with standard containers. It's not uncommon situation when specialised allocators are really a good idea. > 2) Using concepts, actually a polygon or linestring can be anything as > long as it fullfiles the concept. So having an iterator (for linestring > that is enough), having traits te denote exterior/interior ring > handling. In this way our library does not even now what is below the > surface, it just uses it. This is an important detail. One of the major feature of GGL is that it's extensible and applicable to user-defined types that conform to concepts and contracts defined by GGL. It is realised with use of abstractions like iterator, range, collection which are orthogonal to specific types. This makes it possible to design set of geometry or geometry-like types or managed with sophisticated allocators, memory pools, etc. and use them with GGL. For example, it would be possible to specialise ggl::polygon with stxxl::vector [1] and apply GGL algorithms on such container capable to store very large number of elements. [1] http://stxxl.sourceforge.net/ There are much more powerful options available like use of concept of views [2], iterator adaptors [3], etc. [2] http://www.zib.de/weiser/vtl/ [3] http://www.boost.org/doc/libs/1_39_0/libs/iterator/doc/index.html Imagine calculation of length or transformation of coordinate of N linestrings, both of M points, in single-pass using zip_iterator :-) Best regards, -- Mateusz Loskot, http://mateusz.loskot.net Charter Member of OSGeo, http://osgeo.org _______________________________________________ geos-devel mailing list [hidden email] http://lists.osgeo.org/mailman/listinfo/geos-devel |
||||||||||||||||
|
Martin Davis
|
In reply to this post
by Barend Gehrels
> The GGL overlay algorithm will be described in a paper. It is a modern > variant of the classic Weiler-Atherton algorithm. Have you done anything to make the algorithm robust? My impression of this algorithm is that it might be more complex to make robust (although perhaps you can handle that in the intersection determination). > >> The JTS/GEOS predicate and overlay algorithms were developed with the >> primary goal being first generality and then performance. So no >> doubt there's better ways of doing things. > Actually the GGL algorithm is generic as well, in the sense that it is > able to overlay polygons and polygon/rectangle (clipping) with the > same algorithm. The only difference is getting the intersections, > which is more efficient for the rectangle case. Also > intersection/union are implemented in one algorithm. The JTS/GEOS generality extends to handling all combinations of polygons, lines and points. As you say, rectangles are special cases of polygons which allow faster intersection detection, and which don't have any self-intersections, so don't need an initial topology building step. JTS/GEOS has some optimized code for rectangle handling, but there's still opportunity for further optimization. > >> In the GEOS algorithms at least I don't see any way of avoiding >> dynamic allocation, since there's no way to predict a priori how many >> line segment intersections will be found, or how what the structure >> of the output geometry is. Does GGL avoid this problem in some way? > Yes. It will be described, but in short: we don't insert the found > intersection points into the polygons (as done in many algorithms, but > I don't know about GEOS) but register them separately. That saves a > copy, plus many inserts (shifts). However, it requires somewhat more > bookkeeping. So intersected polygons are assembled in the end, in > between there are no large pieces of memory allocation. JTS/GEOS uses the same approach. As you say, it's more efficient to collect the intersection points first and then create the split edges. -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 _______________________________________________ geos-devel mailing list [hidden email] http://lists.osgeo.org/mailman/listinfo/geos-devel |
||||||||||||||||
|
Martin Davis
|
In reply to this post
by Barend Gehrels
Barend Gehrels wrote: > >> Templates would make it a lot better, but far away >> from 1:1 mapping with Java. >> > Sure, though Java also have templates now I'm no expert in this, but my understanding is that Java templates are purely for type management, and don't really provide much in the way of compile-time optimization (since they don't change the underlying memory allocation model of Java). So it's not clear to me that rewriting JTS to use templates would provide optimal code via a direct port to C++. It might get closer, I guess, but maybe there'd still be some semantic rewriting required for maximum optimization. But I'd be happy for someone to prove this conjecture wrong 8^) -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 _______________________________________________ geos-devel mailing list [hidden email] http://lists.osgeo.org/mailman/listinfo/geos-devel |
||||||||||||||||
|
Mateusz Loskot
|
Martin Davis wrote:
> > > Barend Gehrels wrote: >> >>> Templates would make it a lot better, but far away from 1:1 mapping >>> with Java. >>> >> Sure, though Java also have templates now > > I'm no expert in this, but my understanding is that Java templates are > purely for type management, and don't really provide much in the way of > compile-time optimization (since they don't change the underlying memory > allocation model of Java). Yes, Java generics work for type-safety only/mostly. > So it's not clear to me that rewriting JTS > to use templates would provide optimal code via a direct port to C++. > It might get closer, I guess, but maybe there'd still be some semantic > rewriting required for maximum optimization. But I'd be happy for > someone to prove this conjecture wrong 8^) The results might be funny. I'm not sure how up-to-date this is, but still interesting: http://www.oreillynet.com/onjava/blog/2005/10/generics_performance_demystifi_1.html Best regards, -- Mateusz Loskot, http://mateusz.loskot.net Charter Member of OSGeo, http://osgeo.org _______________________________________________ geos-devel mailing list [hidden email] http://lists.osgeo.org/mailman/listinfo/geos-devel |
||||||||||||||||
| Free Embeddable Forum Powered by Nabble | Help |
