Sweep line support

[Winnie]

Hi list!

I'd like to find all intersecting segments for a set of segments using
Python and CGAL bindings. I found the compute_intersection_points
function of the Sweep_line_2 module [1], which unfortunately only
outputs the intersection points (and not the intersecting segments). My
idea was to write my own Sweep_line_2_visitor (which currently seems to
be undocumented - even for C++) similar to the Sweep_line_points_visitor
and store the segments instead of the points.

Additionally, it looks like there are no CGAL bindings for the
Sweep_line_2 module, yet. So I tried to come up with some SWIG stuff
that would do the job [2] - but I don't know how to export the
Sweep_line_2_visitor.

Unfortunately, my bindings don't work when I use them in Python. All
three functions of the Sweep_line_2 module output wrong results. I have
written a small test script [3], which makes it look like only one of
the segments gets passed to the C++ function - even though I declared
the parameter to be a Segment_range.

Can anybody help me on these issues? Is there a plan to make an official
binding for the Sweep_line_2 module in the near future?

Thanks for any help in advance - I need this stuff for my master's
thesis, so I'm a bit in a hurry. ;-)

Winnie

[1]
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Sweep_line_2_ref/Function_compute_intersection_points.html
[2] https://github.com/winniehell/cgal-bindings-sweep-line
[3] https://gist.github.com/4013377

[Winnie]

> I have written a small test script [3], which makes it look like only one of
> the segments gets passed to the C++ function - even though I declared
> the parameter to be a Segment_range.

So I made further investigations on this and found out that the segments
get correctly passed to C++ (I included a test_segment_range function) -
nevertheless do_curves_intersect() returns false, compute_subcurves()
returns only the first segment and compute_intersection_points() outputs
no intersection points (even though there should be one at (5,5) ).

What makes me wonder, is that the code looks exactly the same as in
Convex_hull_2 (at least to me).

> [3] https://gist.github.com/4013377

[Philipp Moeller]

I haven't looked at your code, so this is purely guess-work but the most
likely error: the normal intersection code is wrapped differently from
other global functions because it requires exact constructions.

This is done with:
SWIG_CGAL_FORWARD_AND_FILTER_CALL_GF_2

This might be necessary for functions from Sweep_line_2 as well.

HTH,
Philipp

[Sebastien Loriot (GeometryFactory)]

Phillip is right, you probably have an issue because this package
requires exact constructions and input are from a kernel with inexact
constructions. I have to come up with a general solution for this
problem but don't have time for now.

As long as you have no constructions, you can still make a conversion to
an exact kernel (like what is done in the intersection package) but
if you have constructions then it gets tricky. The easiest way to handle
this is to wrap the whole functionality in C++ and expose a simplified
API with SWIG.

Sebastien.

[Winnie]

> This is done with: SWIG_CGAL_FORWARD_AND_FILTER_CALL_GF_2

As I understand the macros, I rather need a
SWIG_CGAL_FORWARD_AND_FILTER_CALL_GF_1 for the do_curves_intersect(),
which currently does not exist (I added this to my
SWIG_CGAL/Common/global_function_macros.h).

I tried to copy the stuff to my code for the do_curves_intersect()
function, but now I get an undefined symbol for that. The problem is
that I don't really understand what I'm doing, so I don't know how to
come up with a solution myself...

> As long as you have no constructions, you can still make a conversion
> to an exact kernel (like what is done in the intersection package)
> but if you have constructions then it gets tricky.

I'm not sure how that would work. Actually the only thing I need at this
point, is to pass a set of segments to CGAL an get for each segment a
subset of intersecting segments. The reason why I'd like to use the
sweep line approach is that I want to stay in sub-quadratic running time
(with respect to the number of segments).

> The easiest way to handle this is to wrap the whole functionality in C++
> and expose a simplified API with SWIG.

Sounds like a good idea for now!

Thank you both for your quick help! I pushed my changes to my repository
[1] and would be glad if you find time to have a look at it at some
point or even implement working bindings for the Sweep_line_2 module. :-)

Winnie

[1] https://github.com/winniehell/cgal-bindings-sweep-line