Re: [boost] preview of a template geometry library

From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2008-02-01 19:49:55

Barend Gehrels wrote:
> Phil Endecott wrote:
>> Do things like your clipping and simplification algorithms work 
>> in-place or out-of-place, or both?  I can imagine that both of these 
>> examples will often return a result identical to the input, in typical 
>> usage; avoiding a copy in that case would be worthwhile.
>>   
> They work out-of-place, they deliver a copy. And indeed this might 
> result in an identical one, I will consider to avoid that. Do you want 
> to have a boolean returned or something like that?
> However, to me it would seem awkward to check each time if my result is 
> in the source or in a copy. Besides that, in many algorithms you know 
> (or even then don't know) that the algorithm resulted in the same output 
> as the input after the process is completed. The copy is then ready, so 
> in those cases it is not more efficient.

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.

When I look at the OutputIterator variant, I like to imagine that it's 
possible to chain together a pipeline of operations using output 
iterators and input iterators.  People have mentioned "dataflow" 
sometimes on this list.  I have never thought through what's necessary 
to achieve this.

If I had a linestring with lots of elements, and I wanted to clip it to 
a viewbox and then render it, I would prefer to do it 
segment-by-segment to avoid copying it; e.g. (naively)

for each segment in linestring
   clip this segment to bounding box
     plot resulting segment, if any

It's a bit more complicated because there isn't a 1:1 relationship 
between input line segments and output line segments.  How about a clip functor:

class Clipper {
public:
   Clipper(box clip_to);
   linestring operator()(line l);  // retuns a linestring with 0, 1 or 
more segments,
                                   // depending on how l lies w.r.t. the 
clip_to box
};

or alternatively:

class Clipper {
public:
   Clipper(box clip_to, OutputIterator iter);
   void operator()(line l);  // outputs clipped line segments, if any, 
to iter.
};

(Functors for variable-width character set conversions are a bit like 
this.  Are there any examples in the standard library, or elsewhere in Boost?)

It's also interesting to consider how this could work in the context of 
more intelligent containers, e.g. polygons with bounding-boxes or with 
spatial indexing.  Say I have a polygon that is the coastline of a 
continent, with millions of points, and I'm zoomed in on a bit of 
coast.  How long does it take to get the clipped polygon to render?  
Say the container can iterate efficiently over a 2d range:

indexed_polygon continent_coastline = ...;
box viewbox = ...;
Clipper cl(viewbox);
indexed_polygon::range2d r(continent_coastline,viewbox);
for(range2d::const_iterator i = r.begin();
     i != r.end(); ++i) {
   // We get each line from continent_coastline that is within, or 
crosses, the viewbox
   cl(*i);  // Clip to the viewbox, do something with the resulting line-segments.
   ...
}

That's quite straightforward, as long as the clipper does the right 
thing for all the peculiar cases.  But if you have a 
whole-polygon-at-a-time clip algorithm, it's not clear how you do it:

indexed_polygon continent_coastline = ...;
box viewbox = ...;
polygon visible_outline = clip(viewbox,continent_coastline);
   // Could be efficient if the clip algorithm knew that 
continent_coastline had range2d, maybe?
   // Similarly, could be efficient for a polygon-with-bounding-box, if 
the clip algorithm
   // knew that it had it.  This sounds like a case for specialisations 
with enable_if.
   // But most likely, clip() will not exploit the indexing in 
inexed_polygon and treat it
   // like a std::vector<point>.

So I could pass a range to the algorithm:

indexed_polygon continent_coastline = ...;
box viewbox = ...;
indexed_polygon::range2d r(continent_coastline,viewbox);
polygon visible_outline = clip(viewbox, r.begin(), r.end());

This is all very interesting.  But you should stop me from waffling 
about details, and instead focus on "what is the way forward?".

Phil.