Re: [boost] preview of a template geometry library

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.