Re: [boost] Preview 3 of the Geometry Library

Subject: Re: [boost] Preview 3 of the Geometry Library
From: Barend Gehrels (barend_at_[hidden])
Date: 2008-10-15 10:00:11

Just a few additions from my side.

> Here are the few answers I can give right now, I let Barend complete
> or correct me, and answer the questions for which he has a better view
> of the library than me.
>
>   
>> - Still about "box", it is really an axis-aligned (whatever that means in
>> non-cartesian geometries) hyperrectangle.
>> Since "box" can not contain an arbitrary box, maybe it should be called
>> minmaxbox or aabox or whatever.
>>     
>
> aabox could be good.
>   
>> - envelope calculates the minimum bounding axis-aligned hyperrectangle for
>> an object.
>> It might also be desirable to have a way to calculate the minimum bounding
>> hyperrectangle (non necessary axis-aligned) or the minimum bounding sphere.
>> What names would those algorithms have if envelope is reserved for AABHR?
>>     

The names of geometric objects are, as much as possible, taken over from 
OGC (see also http://geometrylibrary.geodan.nl/ogc.html). Those names 
(point, linestring, linear ring, polygon) are also used in Google's KML 
and in most databases with geometry support.
Indeed the "circle" and the "box" were not there, we've added them, and 
they are open for discussion.

Also the names of the algorithms are borrowed from OGC, and are used in 
many GIS applications and spatially enabled databases. It seems 
therefore useful to have an algorithm "envelope" there. See for example 
http://dev.mysql.com/doc/refman/5.1/en/geometry-property-functions.html#function_envelope
(which, as OGC describes, returns a polygon - we thought a box was more 
appropriate for C++ applications, but it is open for discussion).

>> - Modeling sequences of polygons as iterator pairs seems an annoyance to me,
>> ranges are much prettier to handle since one variable is thus sufficient to
>> represent one object (while two are required for iterators).
>>     
>
> Maybe we can double each algorithm to have the choice between passing
> a pair and a range. AFAIK, this will be the approach of the algorithms
> in C++0x, am I right?
>   
None of the algorithms use iterator pairs for polygons. Polygons might 
have holes, in our library, so having just a sequence of points is not 
sufficient to define a polygon.

On the other hand, algorithms take linestrings by iterator pairs, which 
was in fact a positive result of the discussions of this list. Return of 
linestrings / polygons is done using output iterators.

>> - Algorithms should be overloaded to handle all geometric objects. I assume
>> the reason it wasn't done is simply because of time to do so.
>>     
>
> Yes I suppose that we'll be able to add those overloads once the
> general design will be validated.
>   
Agree, where it makes sense. The "within" algorithm is not symmetric, a 
point can be within a polygon but a polygon cannot be within a point.

> why isn't envelope returning in result rather than taking a reference?
The reason is, like with centroid, that the output box / point might 
have a different type than the input geometry. If it was a result, the 
library user has, when calling the function, to specify the type as 
template parameter. But it might be changed, it is open.

> - Why are intersection_segment arguments template parameters instead 
> of segment, why is it not simply an intersection overload and why does 
> it return something different than intersection? Maybe the design of 
> the generic intersection should be extended so that it can work with 
> segments rather than segments be made a special case.
Right. The case of the segment, in fact, is actually an internal 
implementation function. It should have been in namespace "impl", will 
be changed. Agree, all intersection algorithms should return the same 
thing and should have the same name. Internally it is useful that it 
exactly returns how it intersects.
> - An overlap algorithm, that would be equivalent to testing 
> not_empty(intersection) || within, would probably be interesting, 
> especially since it is very useful for collision detection or spatial 
> indexing. It can obviously be much faster than performing intersection 
> and within calls.
Agree.
> - centroid says it throws an exception if the polygon does not contain 
> any point. But how can a polygon not contain any points!?
> The constructor of a polygon should force it to have at least one point.
A polygon with only one point has also not much meaning. See also 
discussion about construction. As soon as the polygons follow the 
concept Polygon, the construction is open to the implementator / library 
user. Then the centroid algorithm can still get an empty polygon.

Barend