Re: [boost] Preview 4 of the Generic Geometry Library (ggl)

Subject: Re: [boost] Preview 4 of the Generic Geometry Library (ggl)
From: Barend Gehrels (barend_at_[hidden])
Date: 2009-02-17 13:51:32

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?
>   
Today didn't add it, but will do that (probably thursday), no problem. 
And yes, it is all doxygen generated.
> 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 
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.
>   
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.
> 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 
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