YES, the library should be accepted (only show stopper is that it has to include the non-cartesian coordinates so that the library can be useful as is without resorting to additional extensions) - What is your evaluation of the design? The design is good and has taken input in multiple iterations from the community. Also, it's a very strong point that the library provides open benchmarks with multiple libraries so that the performance standing of the library can be evaluated. The week point is that the library does not satisfy the needs of some application domains (e.g. VLSI domain) where floating point types are not acceptable. It's unfortunate that this review has been muddled by the recent boost.polygon review. This is a topic beyond this review and specific to the boost review process. I think in this case it should be determined by at least two experts whether it is possible to have a generic library that can satisfy the multiple application domains, and if yes, then take GGL as the base, update the design and incorporate boost polygon algorithms as appropriate. - What is your evaluation of the implementation? The library should incorporate the key extensions that make it useful right away, i.e. non-cartesian coordinates. Not including these will hamper the usefulness and adoption of the library. An example where this happened was the GIL library, it had a wonderful generic design but a key numeric extension was not included in the Boost library. As a result, the adoption has been very limited and the key extension not updated or bug-fixed, with some algorithms being ported and some libraries being built on top, but not wide use. I think the problem with the PROJ dependency could be handled similary to the MPI library, that provides bindings to the C library. - What is your evaluation of the documentation? The docs have to show how it can be used in multiple domains, GIS, CAD, VLSI, .. Same with the examples. - What is your evaluation of the potential usefulness of the library? Very high. A broad library that could be a great match for Boost. - Did you try to use the library? With what compiler? Yes. g++ 4.4.1 on x86_64 Did you have any problems? YES, because the non-cartesian extension was not part of the library. - How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? 10+ hours. Studied both GTL/GGL papers/presentations presented in BoostCon09. - Are you knowledgeable about the problem domain? Yes, the GIS application domain but not core geometry and other important domains.
Hi Jose, Thanks for your interest and for your enthousiastic review.
The library should incorporate the key extensions that make it useful right away, i.e. non-cartesian coordinates.
As I've a GIS-background myself too I'm glad to read this. The reasons for moving it to extension were: - the kernel should be geometry and not GIS - there is one thing still to be incorporated in the design of the GIS-extension (this is: the earth model, it is referred to in distance and in projections, and it should be shared) - the library is large and projections should make much it larger, and we didn't write the maths ourselves One question, do you mean with key-extension: - the geographic coordinate system - or also the projections? The first is small, a few sources and distance calculations, and they were included in the distribution because they nicely show how to work with BGL (and GIS/SVG). The projections is more, ~90 complex math sources
I think the problem with the PROJ dependency could be handled similary to the MPI library, that provides bindings to the C library.
That is an option, but we converted PROJ to C++ style, that alone gives already some %'s performance gain. Besides that we want to be able to use GMP numbers (optionally), so we don't want to mingle them into existing (heavily macro's) C sources. Regards, Barend
On Mon, Nov 16, 2009 at 10:36 PM, Barend Gehrels <barend@geodan.nl> wrote:
As I've a GIS-background myself too I'm glad to read this. The reasons for moving it to extension were: - the kernel should be geometry and not GIS - there is one thing still to be incorporated in the design of the GIS-extension (this is: the earth model, it is referred to in distance and in projections, and it should be shared) - the library is large and projections should make much it larger, and we didn't write the maths ourselves
Moving it to extensions make sense. My point is that the extensions necessary to make the library useful for GIS should be part of the core library rather than a separate extension that the user has to find.
One question, do you mean with key-extension: - the geographic coordinate system - or also the projections?
The first is small, a few sources and distance calculations, and they were included in the distribution because they nicely show how to work with BGL (and GIS/SVG). The projections is more, ~90 complex math sources
I think the problem with the PROJ dependency could be handled similary to the MPI library, that provides bindings to the C library.
That is an option, but we converted PROJ to C++ style, that alone gives already some %'s performance gain. Besides that we want to be able to use GMP numbers (optionally), so we don't want to mingle them into existing (heavily macro's) C sources.
The first one is key, the second one you would need feedback from more reviewers. If there is no PROJ dependency then it's even easier to include it. regards jose
On Mon, Nov 16, 2009 at 10:36 PM, Barend Gehrels <barend@geodan.nl> wrote:
Hi Jose,
Thanks for your interest and for your enthousiastic review.
I forgot to add this in the review: Design --------- Spatial indexes are very important. What is the plan ? (I saw the brief mention in your paper). I also saw complaints about the bad quality of the SOC project code. I found an r-tree implementation that is part of a thesis and asked the author if he would be willing to donate the code (if it made sense!) Also, most mentions to indexes are memory indexes. Are there any solutions for persistent spatial indexes ? maybe by interfacing to an external library Do you see state-of-the-art c++ libraries like mapnik potentially using GGL, instead of their abstractions ? Docs ------- It would be nice to have at least one example that also uses GIL (a plus would be simple label placement with GIL + Freetype)
Jose wrote:
Also, most mentions to indexes are memory indexes. Are there any solutions for persistent spatial indexes ? maybe by interfacing to an external library
Jose, This is a very interesting subject indeed. I would be interested in solving spatial indexing in generic way myself. (I'm sorry for constantly referring to GIS domain, an occupational disease, clearly.) From GIS domain perspective, regarding persistent spatial index, I've observed popularity of two solutions based on Open Source implementations: - PostgreSQL GiST as foundation of spatial index for PostGIS [1] - simple single file-based (.qix) quadtree index [2] and [3]
Do you see state-of-the-art c++ libraries like mapnik potentially using GGL, instead of their abstractions ?
I am not a member of Mapnik team, however I have spoken to Artem Pavlenko long time ago about generic geometry library and he was confirming high interest in this subject. In those times, the only usable alternative for GIS was GEOS. Artem was not very enthusiastic about using GEOS. Given that, I would assume Mapnik project would be a potential user of GGL. [1] http://postgis.refractions.net/docs/ch04.html [2] http://trac.osgeo.org/mapserver/wiki/ShpTree [3] http://www.mapserver.org/utilities/shptreevis.html Best regards, -- Mateusz Loskot, http://mateusz.loskot.net Charter Member of OSGeo, http://osgeo.org
On Tue, Nov 17, 2009 at 1:43 PM, Mateusz Loskot <mateusz@loskot.net> wrote:
Jose,
This is a very interesting subject indeed. I would be interested in solving spatial indexing in generic way myself.
In the past I've implemented the Zones Algorithm using b-trees instead of sql, but I feel it is not a very good solution. http://research.microsoft.com/apps/pubs/default.aspx?id=64524 I recall long ago checking an r-tree algorithm (maybe from rtreeportal) that used persistent r-trees and it could potentially be very nice but it's risky to use code that is not actively developed because when you hit a problem you are stuck!
I am not a member of Mapnik team, however I have spoken to Artem Pavlenko long time ago about generic geometry library and he was confirming high interest in this subject. In those times, the only usable alternative for GIS was GEOS. Artem was not very enthusiastic about using GEOS. Given that, I would assume Mapnik project would be a potential user of GGL.
great!
Jose wrote:
On Tue, Nov 17, 2009 at 1:43 PM, Mateusz Loskot <mateusz@loskot.net> wrote:
Jose,
This is a very interesting subject indeed. I would be interested in solving spatial indexing in generic way myself.
In the past I've implemented the Zones Algorithm using b-trees instead of sql, but I feel it is not a very good solution. http://research.microsoft.com/apps/pubs/default.aspx?id=64524
Jose, Interesting resource. Thanks.
I recall long ago checking an r-tree algorithm (maybe from rtreeportal) that used persistent r-trees and it could potentially be very nice but it's risky to use code that is not actively developed because when you hit a problem you are stuck!
Yes. Best regards, -- Mateusz Loskot, http://mateusz.loskot.net Charter Member of OSGeo, http://osgeo.org
Hi Jose,
Design ---------
Spatial indexes are very important. What is the plan ? (I saw the brief mention in your paper). The plan is still there. We have an implementation, as you know, and want to revisit it a little more than we did until now. So it is currently not included, also because it is not yet used in the algorithms, so not yet essential.
As Mateusz said, we want to have an implementation based on templates; the SOC version did use virtual methods and we wish to avoid them.
I also saw complaints about the bad quality of the SOC project code.
People should not complain the way they did. We will take care for good quality.
I found an r-tree implementation that is part of a thesis and asked the author if he would be willing to donate the code (if it made sense!)
The implementation we have is r-tree. If the implementation you refer to is completely template based and has no virtual methods, we're certainly interested to compare or even include it. Our actual wish is a Priority R-Tree because it is worst-case optimal.
[quoted from more recent mail] I recall long ago checking an r-tree algorithm (maybe from rtreeportal) that used persistent r-trees We're currently not planning persistent trees inside the library (though it is interesting of course). We could do research to combine them (e.g. based on our concepts), so interfacing indeed, but that might more have the form of an external-sample than real integration.
Regards, Barend
As Mateusz said, we want to have an implementation based on templates; the SOC version did use virtual methods and we wish to avoid them.
Below is a c++ template-based implementation that has been used for route planning in the European street netwok (18 million vertices and 22 million edges). The code is part of a thesis and the author is willing to change the license to Boost, if it can be useful! http://idlebox.net/2006/Studienarbeit/libvgserver-0.1/RTree.h.html http://idlebox.net/blogtags/compsci_study_thesis In my opinion, a good r-tree implementation is necessary. I have no experience with the above library but I've seen other code from this author to be of high quality. regards
On Tue, Nov 17, 2009 at 10:15 AM, Jose <jmalv04@gmail.com> wrote:
In my opinion, a good r-tree implementation is necessary. I have no experience with the above library but I've seen other code from this author to be of high quality.
For the purposes of my own review, I'm trying to decide whether I think the library should be accepted without a spatial index. Would anyone like to sway my opinion one way or the other? :-) Jon
On Tue, Nov 17, 2009 at 6:21 PM, Jonathan Franklin <franklin.jonathan@gmail.com> wrote:
On Tue, Nov 17, 2009 at 10:15 AM, Jose <jmalv04@gmail.com> wrote:
In my opinion, a good r-tree implementation is necessary. I have no experience with the above library but I've seen other code from this author to be of high quality.
For the purposes of my own review, I'm trying to decide whether I think the library should be accepted without a spatial index. Would anyone like to sway my opinion one way or the other? :-)
I think an important point in a library is that it has a roadmap. GGL plans to address this! I think is key to have enough at the beginning so that the library is useful but the library has to evolve. Having too much at the beginning might also be bad because there is less focus on the generic stuff ! I thiink a spatial index should be in but its better the "release early, release often, but with high quality"
Jonathan Franklin wrote:
For the purposes of my own review, I'm trying to decide whether I think the library should be accepted without a spatial index. Would anyone like to sway my opinion one way or the other?
Hi Jon, I have a slightly unconventional spatial index that I would like one day to submit to Boost; I was hoping that we would have a Boost geometry framework that I could port it to, and as you may have noticed I'm unhappy that we instead have two incompatible ones... My index is actually an adaptor that uses Z-curves to make a 1D container (e.g. std::map, or for read-only access a memory-mapped file) efficiently accessible as a 2D (or potentially higher dimension) container. A restriction of the Z-curve method is that it does not work with floating-point coordinates... I suggest that the absence of a spatial index should not be a reason for rejecting GGL. It might be that adding some concepts to support this could be appropriate; for example, Barend, what requirements does the spatial index extension to your union/intersection algorithm have? Are they expressed as concepts? Phil.
Jonathan Franklin wrote:
On Tue, Nov 17, 2009 at 10:15 AM, Jose <jmalv04@gmail.com> wrote:
In my opinion, a good r-tree implementation is necessary. I have no experience with the above library but I've seen other code from this author to be of high quality.
For the purposes of my own review, I'm trying to decide whether I think the library should be accepted without a spatial index. Would anyone like to sway my opinion one way or the other? :-)
Personally I don't think that is a reasonable condition. If I were managing the review I would discount such an objection as unreasonable. Implementing a good 2D spatial index that is correct and competitively fast and memory efficient is 9 months of work. I won't go into all that is required. Implementing a spatial index that is merely correct and sufficiently generic is probably one month of work (design, implementation, test, documentation) for a very experience developer working without distractions. These estimates should be considered optimistic, as most such estimates are. Hastily adding a spatial index implemented by someone else might be ill advised. If the original author does not choose to maintain the code it is a big risk. I would prefer that a 2d spatial index in boost be competitively fast. Demonstrating that will be as challenging and subjective as demonstrating performance for the boolean operations. I think it would be reasonable to let a generic 2d spatial index data structure be reviewed as a stand alone library when someone has one they feel is ready for boost. Regards, Luke
DISCLAIMER: I have not looked at the GGL yet, so my comments are mostly of a meta character. On Nov 17, 2009, at 2:17 PM, Simonson, Lucanus J wrote:
Jonathan Franklin wrote:
On Tue, Nov 17, 2009 at 10:15 AM, Jose <jmalv04@gmail.com> wrote:
In my opinion, a good r-tree implementation is necessary. I have no experience with the above library but I've seen other code from this author to be of high quality.
For the purposes of my own review, I'm trying to decide whether I think the library should be accepted without a spatial index. Would anyone like to sway my opinion one way or the other? :-)
Personally I don't think that is a reasonable condition. If I were managing the review I would discount such an objection as unreasonable. Implementing a good 2D spatial index that is correct and competitively fast and memory efficient is 9 months of work.
Why would the effort needed matter for an evaluation of a library?
I won't go into all that is required. Implementing a spatial index that is merely correct and sufficiently generic is probably one month of work (design, implementation, test, documentation) for a very experience developer working without distractions.
So, *if* the spatial index is considered crucial for the intended uses of GGL, we just wait for 3 part-time months for a re-admission into the review queue. That does not sound unreasonable, given that hypothesis of the index being crucial.
These estimates should be considered optimistic, as most such estimates are. Hastily adding a spatial index implemented by someone else might be ill advised. If the original author does not choose to maintain the code it is a big risk. I would prefer that a 2d spatial index in boost be competitively fast. Demonstrating that will be as challenging and subjective as demonstrating performance for the boolean operations. I think it would be reasonable to let a generic 2 d spatial index data structure be reviewed as a stand alone library when someone has one they feel is ready for boost.
Fair enough, if it can easily be plugged into GGL. /David
On Tue, Nov 17, 2009 at 12:17 PM, Simonson, Lucanus J <lucanus.j.simonson@intel.com> wrote:
Jonathan Franklin wrote:
For the purposes of my own review, I'm trying to decide whether I think the library should be accepted without a spatial index. Would anyone like to sway my opinion one way or the other? :-)
Personally I don't think that is a reasonable condition. If I were managing the review I would discount such an objection as unreasonable.
So, if you're saying that my own personal needs in a library are much less important that the community's needs, then I totally agree. :-) Clearly, there has to be some minimum level of functionality for a library to be generally useful. I'm trying to convince myself that GGL will be useful to me without a spatial index, and wondering if others need spatial indexing as much as I do. Luke, you evidently don't need spatial indexing, so that's one good datum. I'm guessing that GGL has proven itself useful to it's existing user base without a spatial index, so that is probably enough data for me to answer my question. Jon
Jonathan Franklin wrote:
On Tue, Nov 17, 2009 at 12:17 PM, Simonson, Lucanus J <lucanus.j.simonson@intel.com> wrote:
Jonathan Franklin wrote:
For the purposes of my own review, I'm trying to decide whether I think the library should be accepted without a spatial index. Would anyone like to sway my opinion one way or the other? :-)
Personally I don't think that is a reasonable condition. If I were managing the review I would discount such an objection as unreasonable.
So, if you're saying that my own personal needs in a library are much less important that the community's needs, then I totally agree. :-)
Clearly, there has to be some minimum level of functionality for a library to be generally useful. I'm trying to convince myself that GGL will be useful to me without a spatial index, and wondering if others need spatial indexing as much as I do.
Luke, you evidently don't need spatial indexing, so that's one good datum.
Quite to the contrary, spatial indexing is crucially important in my application domain and along with polygon clipping, corner stitching tiles and centerline-stick interconnect data model is part of the four cornerstones of physical design VLSI cad software. It is also foundational to a large number of other fields. Well implemented Z-curve/Morton, Hilbert or Sierpinski 2D spatial indexes are what make the difference between an enterprise class data base index and something that merely works. It is the secret sauce in what Oracle sells. It is exactly because it is important that I don't want to rush it. To my way of thinking the polygon clipping is the killer app that GGL would provide. Most of the other algorithms are things that anyone can implement themselves fairly easily or are specific to GIS. Spatial indexing could be a killer app too, if done well. I had a spatial index in my library but I took it out to submit. It was well suited to CAD, but not ideal for general use as compared to better algorithms. I also took out the segment2d and segment3d data structures and concepts that form the basis for centerline stick interconnect models. Regards, Luke
On Tue, Nov 17, 2009 at 2:29 PM, Simonson, Lucanus J <lucanus.j.simonson@intel.com> wrote:
It is exactly because it is important that I don't want to rush it.
How long would you estimate it takes to get the interface right? It seems like that is really the piece that needs to be enterprise class at this point (or at least, when first introduced).
To my way of thinking the polygon clipping is the killer app that GGL would provide.
Yes, I can see this being a killer app for many use-cases, which makes GGL very useful to many, even without a spatial index.
Spatial indexing could be a killer app too, if done well.
It seems like a reference implementation, based on a well-known algorithm (i.e. some R-tree variant), would not be that difficult to get right. It may not be enterprise class, but would allow the authors to get the interface right, and the users to solve many problems in nlogn time, instead of quadratic. If I can then later plug in my own spatial index, that is tweaked for highly-dimensional data, then I will truly be a happy camper. Jon
Jonathan Franklin wrote:
On Tue, Nov 17, 2009 at 2:29 PM, Simonson, Lucanus J <lucanus.j.simonson@intel.com> wrote:
It is exactly because it is important that I don't want to rush it.
How long would you estimate it takes to get the interface right? It seems like that is really the piece that needs to be enterprise class at this point (or at least, when first introduced).
In the context of a Boost library we would surely expect the interface to a spatial index to be quite similar to the interfaces to std:: containers, so there are quite a few interface design decisions that are non-issues. In my experience, the only significant novelty in the interface is how to represent 2D ranges (i.e. to iterate over the points in a rectangle); a range2d type that takes a reference to the container and its bounds and provides a similar interface as the container itself has worked for me. (Luke, I'd be interested to know if your indexes differ significantly from this.) Phil.
On Tue, Nov 17, 2009 at 6:12 PM, Phil Endecott <spam_from_boost_dev@chezphil.org> wrote:
In my experience, the only significant novelty in the interface is how to represent 2D ranges (i.e. to iterate over the points in a rectangle); a range2d type that takes a reference to the container and its bounds and provides a similar interface as the container itself has worked for me.
Ultimately, we will iterate over a set of points (as returned by a range search). However, we need at *least* 2- and 3-d ranges for most use cases. And IMO, the interface should support higher dimension. Choosing the right interface to support both 2 and 3 dimensions *should* make it easily extendible to k dimensions. I'm actually *very* interested in k-d ranges... But expect to add support for them myself at some point, as I'm probably one of very few who actually wants this capability. Jon
Hi, There were many questions and discussions about Spatial Indexes last day and we want to clarify this from GGL point of view. Last summer Federico implemented spatial indexes for GGL during the GSoC. He spent several months on this contribution and did a very good job. The spatial index does its job correctly and is used together with in the OpenStreetmap Merkaartor tool. So we're very satisfied with it, and no bugs are reported. And I didn't encounter them myself. I explicitly state this again because there were complaints about its quality. We didn't include the spatial index in this submission though, because: - the performance should be improved - the interface can be enhanced > In the context of a Boost library we would surely expect the interface > to a spatial index to be quite similar to the interfaces to std:: > containers We want to have it similar to std:: containers, and or Boost Ranges, and or Boost Multi Index. We have to work this out and as Luke states, to implement it fast and memory efficient, and having exactly the right interface, we decided to postpone this and let the current implementation live further as an extension. > >> To my way of thinking the polygon clipping is the killer app that GGL would provide. >> > > Yes, I can see this being a killer app for many use-cases, which makes > GGL very useful to many, even without a spatial index. > Thanks for this. I like to add that GGL is more than polygon clipping alone! The most simple and obvious algorithms are all included in a generic way: distance, area, point-in-polygon. I think many users could profit from that as well, without reinventing the wheel each time. I agree that these algorithms are not that difficult, but they are implemented here for cartesian, spherical coordinate systems and for more geometry types or geometry type pairs, which is not trivial. > I suggest that the absence of a spatial index should not be a reason > for rejecting GGL. It might be that adding some concepts to support > this could be appropriate; for example, Barend, what requirements does > the spatial index extension to your union/intersection algorithm > have? Are they expressed as concepts? A spatial index can be used, in general: - to index geometries, so independant on any algorithm included in GGL - to index segments or sub-geometries during some algorithms which would profit from it (such as the union/intersection) The first is done in OpenStreetmap as mentioned above. It can be easily live as an extension and you can envision many implementations of these spatial indexes, all with different properties with respect to speed, memory, worst-case, etc. The second one could be used in e.g. union/intersection. It is internally not yet expressed as a Policy, a Concept or a Strategy. For such a thing, and the various indexes you can have, the interface should be carefully thought out. Regards, Barend
Barend Gehrels wrote:
Hi,
Yes, I can see this being a killer app for many use-cases, which makes GGL very useful to many, even without a spatial index.
Thanks for this. I like to add that GGL is more than polygon clipping alone! The most simple and obvious algorithms are all included in a generic way: distance, area, point-in-polygon. I think many users could profit from that as well, without reinventing the wheel each time. I agree that these algorithms are not that difficult, but they are implemented here for cartesian, spherical coordinate systems and for more geometry types or geometry type pairs, which is not trivial.
Exactly. I want to add another thing which makes GGL very useful: The actual instantiations of the concepts. Having them inside boost goes a long way in standardizing them. This makes it extremely important that the concepts are general and generic, which I am confident they are. Regards Fabio
Phil Endecott wrote:
Jonathan Franklin wrote:
On Tue, Nov 17, 2009 at 2:29 PM, Simonson, Lucanus J <lucanus.j.simonson@intel.com> wrote:
It is exactly because it is important that I don't want to rush it.
How long would you estimate it takes to get the interface right? It seems like that is really the piece that needs to be enterprise class at this point (or at least, when first introduced).
In the context of a Boost library we would surely expect the interface to a spatial index to be quite similar to the interfaces to std:: containers, so there are quite a few interface design decisions that are non-issues. In my experience, the only significant novelty in the interface is how to represent 2D ranges (i.e. to iterate over the points in a rectangle); a range2d type that takes a reference to the container and its bounds and provides a similar interface as the container itself has worked for me.
(Luke, I'd be interested to know if your indexes differ significantly from this.)
The data structure pre-dates my library and I did not enhance its interface except to make it support my rectangle concept. It provides output iterator for rectangles that match the query and may carry a payload of type T associated with the rectangle. I didn't like the interfaces and felt it would be too much work to enhance to interfaces to make them boost worthy only to have people complain that the performance is terrible and that the data structure is worthless for anything but CAD. Thanks, Luke
participants (8)
-
Barend Gehrels -
David Bergman -
Fabio Fracassi -
Jonathan Franklin -
Jose -
Mateusz Loskot -
Phil Endecott -
Simonson, Lucanus J