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

Subject: Re: [boost] Preview 4 of the Generic Geometry Library (ggl)
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-02-17 13:06:23

Barend Gehrels wrote:
...
> This time we've added the library to the SVN repository at boost,
> https://svn.boost.org/svn/boost/sandbox/ggl
> 
...
> For more change descriptions, see the page on status and preview from
> the documentation (link below).
> 
> The Generic Geometry Library is accessible from Boost SVN, mentioned
> above, or can be downloaded as well from
> http://geometrylibrary.geodan.nl 
...
> We welcome any type of comment, opinion, cooperation, merge or join.

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?  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.

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.

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?

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?  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, a segment is a linestring with two points, 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.  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.  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.  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.  ;)

Regards,
Luke