Re: [boost] preview of a template geometry library

From: Barend Gehrels (barend_at_[hidden])
Date: 2008-02-03 05:44:47

Phil,

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.

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. You then could still model it like that, making 
a temporary copy and call the output iterator.
The std::sort algorithm, for example, works in place and doesn't make a 
copy, maybe because it is recursive.
These are just considerations based on a few examples. However, I prefer 
to have the algorithms as consequent (with respect to input/output) as 
possible.
> 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.
>
> [snip]
> 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>.
>
> [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. 
Therefore, it makes less sense. This is not changed when indexing them, 
but the processing is less of course.
After all intersections are done, indeed they might be outputted one by one.

(A polygon intersection has certainly advantage using indexes during the 
intersection process.)

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

I appreciate all comments and these discussions are indeed very 
interesting. So you can go on. You, Hervé, Fernando and others have made 
me think about many things and alternatives and we will consider all 
those and try to enhance the design and implementation.

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 already 
started with the "point" issue raised by Hervé, points are changed and 
enhanced and I'm happy with it. However, it is unfinished yet.

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.

Best regards, Barend

-- 
-------------------------------------
Barend Gehrels, Geodan Holding b.v., Amsterdam, The Netherlands, www.geodan.nl