Boost logo

Geometry :

Subject: [ggl] Clipping/Intersecting efficiency
From: Chris Browet (cbro)
Date: 2009-05-30 20:40:05

Thanks for this, it would already be half the problem gone. If you could
commit this to the sandbox, it would be great.

In this case, what should be defined as a point_2d? point*, right?

- Chris -

2009/5/30 Barend Gehrels <Barend.Gehrels_at_[hidden]>

> 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
> _______________________________________________
> ggl mailing list
> ggl_at_[hidden]
-------------- next part --------------
An HTML attachment was scrubbed...

Geometry list run by mateusz at