Re: [boost] [Review] GGL review starts today, November 5th

Subject: Re: [boost] [Review] GGL review starts today, November 5th
From: Barend Gehrels (barend_at_[hidden])
Date: 2009-11-22 11:11:19

Hi Pierre,

> I realize I was not very clear. I was referring to 'homogeneous coordinates'. As consequence I suppose it to be more a : ggl::cs::homogeneous. Homogeneous coordinates exists in 1D,3D, ... 100D etc... It's like a cartesian system + an inverse scaling factor for the previous coordinates. So homogeneous point at (1, 1, 1, 4) is in cartesian system at (0.25, 0.25, 0.25). There are very helpfull in projective geometry (application : shadow maps in rt3D, 3D reconstruction, motion capture, tracking, imaging...). I thought this was quite used in GIS too ?
> Anyway, from ggl documentation I read : "Many algorithms such as distance or transform use coordinate systems to select the strategy to use. " This is also described in the strategy rationnale. So there it should be highly possible to 'discards' incompatibles algorithms through strategy + a cs::homogeneous. You can consider it as an alternative proposition to the one you made of an'infinity function' (which could work too). In that case, ggl seems perfectly adequate to support homogeneous coordinates. What do you think of the approach a coordinate system?
>   
This approach will work, and might be easier and/or more fitting into 
the design than the one we described. Thanks for the suggestion!
Yes, I think that a homogenous coordinate system will be very useful 
here and can indeed block distance functions, or enable implementing 
functions in the correct way for homogenous coordinates. Strategies can 
also be mixed (so working on two points of two different coordinate 
systems), and that might be useful for this as well.

> //=== about intersection documentation  
>     
> Yes I had read this pages, but this title is still not really convincing. If I tell you "I got a geometry containing a sphere and two cubes" what is the image that comes to your mind : the set intersection of all three or the sum (union) of them? For me it's the union. Maybe you could write " new geometry containing what is common to A and B "? Or you might use the 'AND'('inversed U') symbol from the set theory. That could make it much more clearer that you are reffering to set theory. What do you think?
>   

I see your point. Yes, the inversed U and U symbols will be indeed more 
clear, and for the users who don't know them, we can make the 
description more clear. I agree completely.

> //=== about intersection design (not set theory, but traditionnal intersection)
>
> Pierre wrote:
>   
>>> For example, if I want to calculate a line-line intersection, I have to provide a template parameter for the output type that seems to me completely unknown when I am requesting the calculation :
>>> line-line can be : nothing / a point / a line. So will we need to create a new function intersection (geometric_intersection<>), or does the template specialization of intersection_inserter allow to already write it correctly?
>>>       
>
> Barend wrote:   
>   
>>> Yes, specifying the output parameter means specifying the behaviour. If you've an output iterator of points, it will deliver zero or more points. If you want lines, you get lines. Please note that line-line is not yet supported.
>>>       
>
> I am not completely convinced by this approach. I will explain first why, and then make a little proposition.
>
> Let's take an example. 
> Example A : "I have a line and a plane. I wonder : does the line touch the plane, and if it does what is the nature of the intersection, and what is the value of the intersection?". If I can only 'expect' a return type, I might have to make 2 query (one with a line as output, and another time with a point as output). From my point of view, such approach looks wrong, because it is not performant, and present the problem from a narrower point of view than what is required by the mathematical problem.
>
> There is a solution to that situation, that is to use for example a boost::variant as return type. This would allow the user to get both calculation results, and also result type. One of the difficulties in that case is to determine exactly what are the appropriate variations of the return type, from a mathematical point of view. 
>
> On the other end, it is true that in every applications, people will most of the time care only for one type of intersection (let's say 'point result' for a plane-line intersection). But in that case, I would consider it as a "special case", not really the default behavior. I think a variant (or some custom struct) as an "exact result" would be appropriated in most cases.
>
> It seems to me this is possible to do (I don't say it's easy). Can you confirm this is possible? Do you think of some drawbacks of such variant return ?
>   
I think it the scenario possible, yes. But I don't know if the 
boost::variant will do, depending on how you implement it.

I give another example. In case an intersection of two polygons, you can 
get:
- the intersection points (if the output geometry type is point)
- the intersection polygon(s) (the 'normal' behaviour)
- the intersection linestrings (the lines where the two polygons happen 
to intersect in a linear form, e.g. shared borders)

Using a variant, you get one of them (because a variant is a multi-type, 
single-value). In this case, the implementation does not know which one 
is the most appropriate. Using a template parameter you can specify what 
you want. Here you get one type of them back, without the possibility to 
specify which type. Seeing your description, this is probably not your 
intention.

Another option, still using a variant, is having the output iterator 
adding variants. In this way all output of the intersection, points, 
lines and polygons, are just append to e.g. a vector of variants. This 
will probably do. I don't know how common this scenario is. It is 
possible, there is one consequence though, it would require three output 
template parameters (to specify how output points, output linestrings, 
output polygons will look like...)

You mention performance and indeed, this would save calculating the 
intersection points two or three times (because internally they are 
always used). Another option to avoid multiple calculations is to split 
the algorithm (actually it is split internally). Users can then specify 
precalculated intersection points in the algorithm (or in an overloaded 
version).

We will take your points into account, it is very interesting. There is 
always room for adding another function (e.g. intersection_variant)  
which returns a vector of variants.

>
> Yes, this is already in the introduction :
> "The GGL might be used in all domains where geometry plays a role: mapping and GIS, gaming, computer graphics and widgets, robotics, astronomy... The core is designed to be as generic as possible and support those domains. However, for now the development has been mostly GIS-oriented."
> But in that case, you need to provide some roadmap / todo list (done / not done) / priorities for the developments : current features and future features. Some kind of 'future versionning' for example would be appreciated.
>   
Yes. Good point, this would be very useful and we will add this.

Thanks, regards, Barend