Boost logo

Boost :

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.

> 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.

> 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.

Boost list run by bdawes at, gregod at, cpdaniel at, john at