Luke,

Barend, I've been looking forward to this pre-release. I noticed that the doc directory in svn is empty. Can documentation be built from what is in svn?

Also, on the front page of geometrylibrary.geodan.nl it says preview 3. How much of the documentation is updated since preview 3? Cannot find that. Are you sure you refreshed that page? Or else which

Today didn't add it, but will do that (probably thursday), no problem. And yes, it is all doxygen generated. page is that? All documentation is updated.

Is it mostly just the status.html page, or are all new concepts/APIs documented? I was very happy to see that I can get at the code through the documentation. I find it very frustrating when boost documentation doesn't include links to the code, which is what I want to see half the time.

Doxygen does a nice job there!

I wanted to find out how the distance function mentioned in status.html works because there is a certain problem with scalability of tag dispatching implementations. It is as I suspected and you have enumerated tag pairs in the dispatch namespace. These include point/point, point/linestring, linestring/point, point/segment and segment/point. What happens if you want to add new conceptual types to your library? Do you have to implement O(n^2) distance dispatch functions to support O(n) tag types in your system? There would be the need for a distance function for each and every possible pair.

Good point! Indeed we need n^2 dispatch specializations. We've been thinking if that could be reduced to the halve of it (half diagonal matrix) using meta-programming but we didn't work that out until now.

Do you use concept refinement? It doesn't appear so from glancing at tags.hpp. Is segment a refinement of linestring, for instance? What happens if you call distance(segment, line_string)? I notice that polygon_tag does not inherit from linestring_tag. Does distance(point, polygon) not work currently?

Many questions. I started with inheriting tags but it bring any profit. So they are indeed not there. Distance (point,polygon) does not work yet. I don't think it is a refinement of linestring, at least the implementation is different. For a ring/polygon you have to check if it is inside. If yes, the distance is 0.0. If no, calculate distance from linestring. It is easy to add it like this, but you can combine those two to get better performance. And therefore it is not yet there.

Why not implement the default distance dispatch as the following:

template <typename Tag1, typename Tag2, typename G1, typename G2> struct distance { static inline typename enable_if<typename not_same_type<G1, G2>::type, typename distance_result<G2, G1>::type>::type calculate(const G1& g1, const G2& g2) { return distance<Tag2, Tag1, G2, G1>::calculate(g2, g1); } };

which at least cuts the number of implementations down by a factor of two? Something like this might be the solution indeed. However, the number of "implementations" stays the same, it is the number of "dispatches" that will decrease, but also that is useful. Thanks!

To be sure this could cause you some syntax errors, especially as you start trying to use concept refinement to resolve the dispatch function.

However, why solve just half the problem? Given the proper abstractions I would say you need only one implementation of distance(T1, T2). Implement it as distance between two linestrings and then allow all other geometry objects be behave as refinements (read-only-view-of) linestring. A point is a linestring with only one point Eehm, that last thing is true but I really think that points should be handled separately. A linestring with one point should be handled but it is not the normal case. Are you handling point-in-polygon like this? I would handle it the other way round. Handle a linestring-with-one-point as a point. Which is what is done. But it needs two implementations, they are really different. In the point-segment distance you need the point-point distance.

, a segment is a linestring with two points We have a segment indeed but just for convenience. Many algorithms handle segments such as area calculation. It is not of primary importance for the user. They can use a linestring everywhere. But they might use segments as well, might be better performant. , a triangle is a linestring with four points (it has to be closed), a rectangle with five, a polygon with n+1 because it has to be closed. We call that last one a "ring". Triangle is not there, besides an example. Rectangle can really be better handled separately. All algorithms are different! You can calculate the area of a rectangle much simpler than you would do it if it is a polygon. OK, now I see what you mean, non-axis-parallel rectangles are indeed just polygons. By the way, we have "linear ring" and "polygon", for the case without and with holes (which can really differ in implementation terms) Then instead of implementing O(n^2) distance functions you can simply implement o(n) views of conceptual types as linestring.

For performance optimization you can always override the one distance function to accept a specific concept. For instance it might be inefficent to view an axis parallel rectangle as a linestring for the purpose of distance computation to a point/rectangle. These overloads could be added and called when appropriate. Better still, these overloads could be added by the motivated user because you have been nice enough to make the dispatch scheme non-member non-friend. I think this is just like we did... Having dispatch functions for different cases... Most of the time they forward to implementations in namespace impl, so there is no double code. By the way, I'm not sure what the distance struct is doing for you, are you using it to allow partial specialization of the dispatch function? Since your default is empty and all others fully specify both tags you don't seem to be using it that way. You can do that with SFINAE as well.

SFINAE overloading of generic functions allows for a great many code transformations and maximum flexibility (at the cost of maximum verboseness) that allows even more freedom that concept refinement. We had SFINAE and it worked. On one of your topics on this list Dave said we were better of with tag dispatching and that proved to be very

The distance struct is very useful for comparing distances in Cartesian systems. It avoids sqrt for every comparison. However, for spherical systems it does not add any value. So then it is just a double. However, the distance struct is completely separated from tag dispatching and from sfinae. We had it in the first preview, but differently, it more natural now. Phil suggested this. true. It is much clearer like this, and it also allows more specializations. The custom triangle example in our documentation shows this.

You can use this freedom to reduce the number of functions you need to write to the minimum. I would rather write O(n) code with SFINAE overhead on each function and some of the structs than O(n^2) code without. Initially I was very wary of writing SFINAE based concept code because it looked like a huge ammount of work. Well, it is a huge ammount of work, but now I understand what I can get for that work, and it ammounts to saving an even bigger ammount of work to accomplish what I want to get done. The compilers can be a real obstacle to writing SFINAE code at times, but with Steven W. around and a positive attitude to keep you going on long weekends this can be overcome. ;)

I'm not yet sure about this, have to have a closer look. Will do that anyway. Thanks for your comments! Regards, Barend

Actually for point in polygon I would think you would want distance from boundary and distance from solid to both be available, perhaps through a strategy.

Agree, you might need it from the inside as well.

I actually don't have a segment concept (yet), and tend to use std::pair<Point> in my own code. In any case, a geometry library ought to be symetric. If you can compute distance between point and segment, why not between segment and linestring?

Our segment started from a pair as well...However, the segment is especially useful, we handle it often as two const references, we don't have to copy the points themselves. And true, a distance betweeen segment and linestring would be useful.

...

...

, a triangle is a linestring with four points (it has to be closed), a rectangle with five, a polygon with n+1 because it has to be closed.

We call that last one a "ring". Triangle is not there, besides an example. Rectangle can really be better handled separately. All algorithms are different! You can calculate the area of a rectangle much simpler than you would do it if it is a polygon. OK, now I see what you mean, non-axis-parallel rectangles are indeed just polygons. By the way, we have "linear ring" and "polygon", for the case without and with holes (which can really differ in implementation terms)

The issue isn't whether something is there, it is how easy it is to add. If each concept added to the library requires O(n) effort where n is the number of extant concepts in the library it will stifle to ability of the author to extend the library and kill off the growth of the API at whatever level of workload the author can handle.

One reason to keep the the number of geometries low. OGC defines three basic ones: point, linestring, polygon. We've added a few more: box because it is very useful in many cases, segment because it is used in many algorithms, ring because a polygon consists of them. The circle just because it was always there, actually it would have to be worked out to all kinds of curved geometries, another workload. Requiring 7x7 distance algorithms, intersections, overlaps, within determinations...

I meant the dispatch::distance<>::compute version of distance. For sqrt optimizations I have a separate distance_squared function. The "namespace dispatch { template <> struct *distance* {}; }" critter doesn't seem to be used because the template could be on the function instead. I was wondering why it was there.

OK, I misunderstood you indeed. The struct is necessary because of partial specializations. See therefore the custom triangle example c04b. Without partial specializations such a thing is not possible (example c04a is then the maximum).

You can look at my code in the svn sandbox under gtl/gtl. There you will find distance(T1, T2) type functions in the files named *_concept.hpp that implement the various distance computations between point/rectangle, point/point etc. polygon_concept.hpp doesn't exist yet, and is just appended on polygon_traits.hpp because I found it convenient to have it all in one file while I was conceptualizing the code. There you will find not distance(polygon, polygon) (which I haven't implemented yet), but you will find distance(point, polygon) I think, as well as the assignments between my six flavors of polygons with/without holes with the assign() function. From that file especially you can take a closer look at overloading with SFINAE. In November I tranformed all my library code from tag dispatching to SFINAE overloading, which produced the code currently residing in the sandbox. It took me about a week to do the simple transformations, three weeks to do the complex ones and another two to port the result to MSVC, however I greatly enhanced the completeness of the API and now it is very easy to extend the library. You have a similar problem to mine.

This is really interesting. We went from SFINAE to tag dispatching in january and were very very happy with it. Its explanation is a bit long to go over all again. However, the main advantage with the new approach is that it offers us much more flexibility, such as partial specializations for certain cases, or deriving from implementation structs. Using SFINAE we had to overload all combinations in separate, hardly distinguishable functions. I know we used it in a (slightly?) different way than you do, having the BCCL concept checks there as well. But it was complicated, gave often compilation problems, and when we converted it all this was much clearer, more logical and could be extended much easier. If it is adding extra one-line dispatch stuct's I'll take that for the advantages it gives. And maybe we can solve that in another way, we didn't work that out yet. It is however interesting that you feel it exactly the other way round, while we're working on the same kind of library :-) I'll soon look to you code again indeed.

If you have cartesian and spherical coordinate sytem polygons with and without holes you have four polygon flavors. It does not feel to me that that is the problem. For example area. A holey polygon just subtracts its inner rings area from the area of its outer ring. There is only one area implementation strategy for cartesian. Then there is indeed one other strategy for spherical rings. However, for the (holey) polygon there is only one implementation, no double code, even no two dispatch struct's, not a single line. The coordinate systems are handled at another level, distinguished by strategies. (OK, that is done by tag dispatching as well, at another level, but does not relate to the holes anymore). So also for the simplify, or length, you'll found no code targeted to a coordinate system.

Regards, Barend

Luke,

If I add triangle it goes to 11. Because my template code can generate the 10x10 instantiations of functions with ~O(10) template function definitions I'm not that intimidated by the idea of adding a triangle concept at some future point. I simply make it a refinement of polygon and it suddenly works with literally hundreds of different functions I've already defined. I think our approach is the same in this way. The triangle example c04 shows that it can be implemented... as a specialization of a polygon... 7x7 versions really does not mean that there are 49 implementations. Your cartesian and sperical can each be converted to the other, putting them together in an equivalency class, whereas conversion from 45 to 90 is not generally allowable, making them equivalent in same contexts but not in others.

We don't convert them, we handle it as different coordinate systems with different strategies. This discussion concentrated on implementation details, but there is more in this new preview. 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. It is coordinate system agnostic and dimension agnostic, as requested by the list. How is everything now? Let's put it in another way, is there any interest in such a geometry library? Regards, Barend

...

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

Hi, This still waited an answer.

When you say refinements seem not applicable, do you mean refinements in general, or just in the case of rectangle/polygon? I have been curious about how you might implement refinement in your tag dispatching based API as I understand it, and I couldn't come up with an answer. If refinement used/supported by your API, or do you think it is not needed except for Const/non Const? I'm curious to hear you elaborate on that.

One (the main?) of the related topics here (on concept refinements) was to limit the number of implementations and combinations. As I've mentioned earlier, we try to limit the geometries such that they are as orthogonal as possible. However, some geometries of course have some common properties. A linestring is, like a linear_ring, a sequence of points. Simple calculations, such as the number of points of them, can share their implementations. With help of a few meta-functions they can also share tag dispatching. Then take for example the "selected" algorithm. It uses the "topological_dimension" (TD) meta-function, which is 0 for points, 1 for lines (or segment), 2 for polygons (and in general everything with an area). The "selected" algorithm specializes on this TD meta-function and everywhere where it is 2 it uses "within". Then for example: calculate distance between two geometries. TD does not make sense here. We will have in the end the ortogonal geometries point, linestring, polygon, multi-point, multi-linestring, multi-polygon, that is 6. Plus the supporting ones segment,box,linear_ring. 6 geometries make already 36 combinations. We now also implemented the reverse tag dispatchings, so point-linestring and linestring-point are implemented as one tag dispatching struct. Bruno implemented this, it uses a Reversable boolean template parameter. So this saves 15 combations, 21 left. (This reversability is applicable to all tag dispatching constructs taking two geometries.) As soon as we have multi-geometries (multi-point for e.g. a fleet, multi-linestring for e.g. a highway, multi-polygon for e.g. France and Corsica), and we want to calculate the distance between them, the process is always the same. They are all vectors (containers), walk through the vectors, check the distance between the entries, if it is shorter than any other memorize that one, etc, straightforward. So the implementation can be the same for all of them (of course using spatial index/sections or similar to do it fast). So we add a meta-function "is_multi", returning false for normal geometries, true for multi-geometries, and we can (partly) specialize on them. There will then only two (one for single-multi, one for multi-multi) dispatch structs handling them all. This saves another 12 combinations. So 9 left, which can be overseen easily (and probably there are more combinations which can be harmonized). (Note that all multi-ones are not yet implemented, they are skipped until all concepts are clear.) So these are all really different cases, distinguishing on linearity, multi-ness, topological dimension. This is not concept refinement, or it would be a complex system of tags multiple inherited by other ones. We limit our dispatch cases in a finetuned way, so no "concept refinement" but "meta-function finetuning"... Regards, Barend https://svn.boost.org/svn/boost/sandbox/ggl <https://svn.boost.org/svn/boost/sandbox/ggl/>