Barend Gehrels wrote:
Phil Endecott wrote:
[snip] Have a look at the string algorithms, for example to_upper. There are three variants:
template<typename WritableRangeT> void to_upper(WritableRangeT & Input, const std::locale & Loc = std::locale());
template<typename OutputIteratorT, typename RangeT> OutputIteratorT to_upper_copy(OutputIteratorT Output, const RangeT & Input, const std::locale & Loc = std::locale());
template<typename SequenceT> SequenceT to_upper_copy(const SequenceT & Input, const std::locale & Loc = std::locale());
So I can do it in-place (first), returning a copy (third), or to an output iterator (second). You could also imagine a copy-on-write version, but we would probably want to implement general-purpose copy-on-write containers or smart-pointers before trying that.
The algorithms are currently modelled conform the OGC specifications. This means they have an input and an output.
We might add the other alternatives as well. However, many algorithms have already many variants. Consider "distance", there are at least 36 variants of "distance": 6 OGC geometries can be compared to each other. This "matrix" is symmetrical, many are just the other way round, but you might expect that the library contains both "distance(point, linestring) {...}" and "distance(linestring, point) {...}" for template reasons.
To offer, for each algorithm, also these three variants, plus the variants taking an iterator, and the variants taking a whole geometry, and sometimes specializations for xy-points or latlong-points or indexed geometries, might seem to much, or an explosion.
In the case of distance() this is a non-issue because the output is only a scalar. (Though there are many variants in terms of min-distance vs. max-distance vs. centroid-distance that might be wanted sometimes.) In other cases, often one variant would be used to trivially implement the others, e.g. some_algo(container) is implemented in terms of some_algo(begin_iter,end_iter). The important thing is to provide a library that can be used to produce code that's as efficient as a "skilled user" would get doing it by hand. Unnecessary copying of large structures is definitely worth avoiding.
For some algorithms it certainly makes sense, for example for the line clipping algorithm as you mentioned. As soon as a line is finished it can be outputted. The algorithm "simplify" is recursive and there it will work less obvious.
As it happens, I use an O(N) sequential simplification algorithm rather than the O(N log M) typical, O(NM) worse-case Douglas-Peucker algorithm, to avoid this. It gives inferior results, but it seems to be a good trade-off in my case. [snip]
The polygon clipping, unlike the line clipping, is finished after the last segment has been processed. Intersections in the last segment of the last inner ring might change the output polygon started first.
Yes, polygons with holes are more complicated; I've never had to deal with them. I think it's worth defining separate concepts for solid and holey polygons so that algorithms can specify which they work with. [snip]
The way forward is, I currently think, that we will change many things based on these and other comments and will make a new preview.
I encourage you to define concepts and to document what concepts your algorithms require.
I also would appreciate it as someone experienced in geometry/gis and the boost process could give me a hand. I mean: in the sense that I could ask questions, discuss some things, show him/her code before preview.
Please show things and ask questions on the list so that everyone can comment. Regards, Phil.