The library is really generic now, concepts are everywhere, as requested by the list before. It can take any std::vector or range, as requested by this list.
That's certainly very good, isn't it? So you can do retroactive modeling and everything. True. External (legacy) classes (points, lines, polygons, boxes) can be registered by traits classes and handled as if they were points etc. Ranges are working very good indeed.
It is coordinate system agnostic and dimension agnostic, as requested by the list.
I wonder how it works. I hope the algorithms can still be written generically, and don't have to be written independently for every coordinate system. The algorithms are generic and forward to strategies (which are normally different per coordinate system) where possible. For example the distance algorithm uses different strategies for spherical / cartesian distance. The simplify algorithm (using distance internally) is generic, is not per system.
I also hope you didn't force yourself to too much agnosticism just because it was requested on the list. People request lots ;). Actually this abstraction was also very useful for ourselves, we're often working with both x/y and latitude/longitude and the way the
In many cases it is possible to write code dimension agnostic, for example for the Pythagorean theorem. In other cases it is better to specialize it for its number of dimensions. For example the separating axis algorithm to check the intersection of 2 oriented bounding boxes in 3D. The theorem makes it possible to solve the problem with "only" 15 cross products. Even if it's still available in 2D, it can probably be written in a much more direct way. So it's reasonable to have sometimes 2D, a 3D and a nD versions for a complete and efficient dimension-agnostic implementation. To be complete: not all algorithms are implemented for 3D Behind the screens the agnosticy works with "coordinate system tags" traits classes, binding strategies to them. For some strategies (e.g. transform) strategies are specialized by the number of dimensions as well. You'll see a lot of strategy specializations in the code, those are always specialized per tag, and sometimes per dimension. library handles them now is also convenient for us.
There seems to be a few inconsistencies in the documentation, Ring says it checks the linestring concept, for example.
Thanks, this one is fixed
Also, what a geometry is should be in the documentation of its concept, not of its model (the model is the implementation of a concept). Of course, the documentation isn't really concept-centric at the moment.
There is a page about concepts on "Related pages" but you are right, the documentation will therefore be enhanced.
The documentation of geometries isn't very clear, by the way. For example, what's an nsphere? Is it the set of points which are at an equal distance of another point, the center? (what a(n n-)sphere really is) Is it the set of points which are at an equal or inferior distance of the center? (typically known as a ball) I would recommend clearly defining every geometry to prevent ambiguities, in terms of set of points maybe, rather than referring to a name which may have various meanings. In the same sort of thing, a polygon is not just the set of points which are on its border, it's all the points that are within, too. The name "ring" lets me think it's just the border. Documentation will be enhanced. In general we've used OGC/Egenhofer definitions, e.g. described in http://www.spatial.maine.edu/~max/RJ3.html <http://www.spatial.maine.edu/%7Emax/RJ3.html> where indeed geometries are handled as point sets.
I also just noticed the performance section. It doesn't really tell what the other libraries are. And since GGL is so much more efficient (by an impressive margin, actually), I recommend adding other libraries to the benchmark: why not CGAL? That one should be a much tougher competitor. There are some more measurements to be done and more details will be added. Therefore I'll keep them currently anonymous. In the end we'll
About the n-sphere, ball, there was a discussion before on the list on this. It is actually handled in the same document of Egenhofer, by the definitions you give. So "within" within a sphere makes no sense, within a disk it does, the point is taken. n-sphere, n-disk... True, polygon is the set of points within, plus border, whilst its borders are linear rings, not having an interior themselves. Internally that is not always handled consequently like this formal definition, a polygon consists of rings so the areas of rings are calculated and added/subtracted, which is conceptually wrong (the result is right...). So you are right, it is a good point (one of your set of good points :-) ) publish the comparison sources and details, it first has to mature a bit and be described better. So you guessed CGAL is not one of them... It will be included, as it provides much or all of the algorithms tested, it is interesting indeed.
How is the new selected algorithm much different from distance? It seems it's either distance or within that is used, depending on the geometry. Is there a use for this algorithm? It just feels kind of weird to me.
It can be very useful, but it is indeed weird in the sense that it is more pragmatical oriented than most others. Two reasons for it: 1) abstraction 2) performance Abstraction: because in a collection of same-type-geometries you might select by a point, especially visually, on the screen you click on a point, line or polygon. However you might click one pixel away from it. By having the generic "selected" it either takes the point or linestring near by, or the point in which it is clicked. The enclosing entity (e.g. a 'layer') does not have to care about which geometry type it selects. Performance: it is not really distance calculation here, as soon as in one dimension it is too far away a point (or linestring) is discarded, no more mathematics necessary then.
Is concept refinement implemented? Is a Ring also a ConstRing and a ConstPolygon? A Ring is a ConstRing, yes. A (Const)Ring is formally not a ConstPolygon, by the definition you gave above...
We try to limit the geometries such that they are as orthogonal as possible. Basic geometires are point, linestring and polygon which are really mutually different (ignoring the linestring with zero length or polygon with zero area). In that sense the box for example is not strictly necessary: it is a polygon without holes and with 5 points, the last closing one the same as the first one. A segment is also not strictly necessary, it is a linestring with only two points. However, segment and box can hardly be missed in implementations. Besides that they are also very useful for the user. So although theoretically and formally they are too much, pragmatically they make a lot of sense. So conceptually Box might be seen a refinement of a Polygon. In practice all algorithms for a box (keep in mind that Box here means an axis aligned box) are different. We've also defined different, pragmatic, access algorithms for it such as getting the min/max corners. And we didn't implement the polygon operations on it such as the outer ring, inner rings, etc because it makes no sense. So no, the Box in our code is not a refinement for a Polygon. The box was just an example but in the end: refinements seem not applicable (besides Const/non Const) Regards, Barend