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 14:35:47

Barend Gehrels wrote:
> Many questions. I started with inheriting tags but it bring any
> profit.

Of course the fact that there is subtyping going on must be used to be profitable.  I actually took out inheriting of tags in my library because I determine refinement relationships with meta-programming instead.  Often times I need more than simply sub-typing to express what types satisfy an algorithm.

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

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.

> 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!

Don't thank me yet, you haven't seen the infinite template instantiation recursion errors you'll have to deal with if you use it.

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

Yes, you are right, distance(point, point) and distance(point, T) should be overloads.  I was focused more on making the system easily extensible rather than collapsing the existing implementation.  I used point and segment merely as examples of what is possible.

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

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?

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

>> Then instead of implementing O(n^2) distance functions you can
>> simply implement o(n) views of conceptual types as linestring.
> 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.

The double code is the dispatch functions.  As you add more concepts into the mix you will appreciate the intractability of enumerating tag pairs in separate dispatch functions.

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

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.

>>   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!

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.  If you have cartesian and spherical coordinate sytem polygons with and without holes you have four polygon flavors.

Regards,
Luke