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#func... (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.
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
- 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
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. library user has, when calling the function, to specify the type as template parameter. But it might be changed, it is open. 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