Boost logo

Geometry :

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::point_2d> strategy;
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...

Geometry list run by mateusz at