From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2008-02-03 11:50:02
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.