Geometry Boost List: [ggl] Clipping/Intersecting efficiency

Subject: [ggl] Clipping/Intersecting efficiency
From: Barend Gehrels (Barend.Gehrels)
Date: 2009-05-30 14:57:32

Hi Chris,

>
>> While registering the point* the indicated way pass compilation, I 
>> now have the problem that, at run-time, the output points are created 
>> on the stack, which obviously fails on a pointer.
I've recreated it and done some experiments. I think there is a 
solution. But not with output to point* or a wrapper.

In the case of the point*, the memory has to be allocated somewhere, as 
you noticed, and it has also to be de-allocated. In the case of the 
line-intersections, a segment (to be copied from the input points) is 
clipped, then 0, 1, or 2 points are added to the output. With point* 
they have to be deep copied (because are changed), so allocation / 
deallocation is necessary. We need a local wrapper there, specialized 
for points, or so, to handle points which go out of scope and points 
which are appended. This will be more complex and also be more 
memory-intensive because many allocated points are never used.

Every algorithm where geometries are edited would have to be revisited 
for this. We have to decide if this will be supported at all.

So we have to state that at this moment vector<point*> is not supported. 
Or we can state that it is only supported for some read-only operations 
(length, distance, area, etc). (Note: distance point-linestring will 
create a temporary point and will probably give the same problems. So: 
not supported...)

A better option is that line-intersection will read (in your case) its 
input from a vector<point*> but outputs to another point-type (one 
without pointer). However, this is also not supported in the current 
distribution, the line-intersection takes its point-type from the input 
geometry. It is (as far as I know) not possible to get the value_type 
from any output iterator. I mean it is possible but it is then often 
void. But output point-type (or output linestring-type in this case) can 
be specified explicitly. Just tried and it works. This will probably 
solve your problem, it will then not be necessary to copy points before 
doing the intersection -> faster.

I just commited (to the trunk) the change I made in the experiment to 
prove/enable this. The main change is that it defines the output 
linestring-type in another place, this has no big implications and 
probably can be committed to the sandbox as well. So if you find this 
useful I can do that this weekend. You then have to call it like this:

    typedef std::vector<my_point*> ln;
    ln myline;
    (...)
    std::vector<ggl::linestring_2d> clipped;
    ggl::strategy::intersection::liang_barsky<ggl::box_2d, 
ggl::point_2d> strategy;
    
ggl::impl::intersection::clip_linestring_with_box<ggl::linestring_2d>(cb, 
myline, std::back_inserter(clipped), strategy);

(Replacing ggl:: by geometry:: if working in the sandbox). The last 
lines mean: call the implementation explicitly to specify the output 
linestring (in the normal algorithm the linetype will still be used as 
the input-linetype)

Regards, Barend

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/ggl/attachments/20090530/ed20abe3/attachment.html