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 16:15:51

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